경계선 설정 방법

의도

• 경기에서는 외벽, 실제 운항에서는 육지나 수심이 얕은 지역 등 배가 갈 수 없는 곳이 있음
• 이를 경계선으로 설정하여, 경로 추종 및 장애물 회피 시 경계선을 넘어가지 않도록 하고자 함
• 경계가 꼭 정사각형이나 직사각형이지 않더라도, 꼭짓점 위치만 찍어 유연하게 대처할 수 있도록 구현하고자 함

문제점

• 직선의 방정식을 일일히 설정하자니 연산이 복잡해질 것 같음
• 직선의 방정식을 기울기, y절편으로 설정한다고 해도 부등식을 판단하는 데 어려움이 있음. y값보다 크다/작다를 판단하는 기준이 도형마다 매번 바뀌어야 함
• 직선을 따라 점을 다 찍는다 해도 Map이 커질 경우 연산이 오래 걸릴 수 있거나, 점을 찍는 범위 설정에 따라 과하게 띄엄띄엄 찍힐 수도 있음
• 검색 결과 shapely 라이브러리가 있다고는 하나, 조금 더 간단한 구현 방법을 찾고 싶음
  • [python] 위도 경도 좌표 polygon 안/밖 유무 확인하기, shapely
  • python - 두 커브 사이에 점이 포함되어 있는지 확인
• 수식을 쉽게 표현하는 SymPy 라이브러리가 있으나, 역시 간단한 구현을 위해 택하지 않음(추후 다른 곳에 사용 가능성은 높아보임)
  • Doing Math with Python (파이썬으로 풀어보는 수학)
  • 파이썬 Sympy 기호수학 - 기초

해결 방법

• crossing polygon(다각형의 내/외부)이라는 알고리즘이 존재함
• 한 점에서 오른쪽(또는 왼쪽)으로 직선을 그렸을 때, 그 직선과 경계선이 만나는 점의 개수가 홀수 개면 점은 다각형의 안쪽에, 짝수 개면 바깥쪽에 존재함
• 참고 사이트
  • [기하] 다각형의 내부 외부 판별
  • Point in Polygon in Python

GPS 좌표를 상대좌표로 변환

의도

• 사용자가 프로그램 상에서 임의로 설정한 상대좌표와 실제 상황에는 큰 차이가 있음
• 실제 위치/크기를 바탕으로 시뮬레이션을 해보고 싶다면 GPS 좌표를 입력해 이를 변환하는 과정이 필요함

해결 방법

• Python 라이브러리 중 pymap3d가 있어 다양한 좌표계 간에 변환을 도와줌
  • pymap3d API documentation
• 소스코드는 하단 GitHub 링크 참조

보완

• 큰 범위의 GPS 좌표를 설정하면 화면 밖으로 시뮬레이터가 넘어가지 않도록 Scale 조정이 필요함

Heading 값의 처리

의도

• 기존의 길찾기 알고리즘에서 '배를 위한' 알고리즘을 구현하고자 했던 목적이 배의 특성을 고려하기 위함임
• 회전과 후진이 비교적 자유로운 자동차/로봇과는 달리, 배는 후진이 불가하거나 회전을 크게 하지 못하는 특성이 있음
• 배의 선수가 가리키는 방향인 heading을 고려하여, 크게 회전하는 경우 혹은 후진을 해야 하는 경우를 최소한으로 줄이는 알고리즘을 구현하고자 함

해결방법

• 8개 방향으로 갈 수 있는 점을 탐색하므로, 좌우 45도 이내 / 45~90도 이내 / 90도 초과로 범위를 나누어 g 값에 가중치를 곱해줌
• 배의 실제 위치를 이동시킬 때마다 회전각을 더해준 heading vector 변수를 선언 및 사용함
• 회전각 계산은 벡터곱을 이용해 구함
  • Numpy 행렬 계산 : Python Numpy 강좌 : 제 7강 - 연산
  • 회전각 구하기 : 두 직선, 벡터의 관계(사이각,회전각) 구하기
• Normalize한(크기가 1인) heading vector가 되도록 수시로 크기 변환해줌

Source Code

GitHub(실시간 업데이트) : AutonomousShipAlgorithm/A_star