다각형에서 가장 값 비싼 경로 찾기

Question

비용을 고려하여 다각형 내부의 경로를 찾으려고합니다.

내 경우에는 상대적으로 직선적이어야하는 문자가 있습니다. 북쪽, 동쪽, 남쪽 또는 서쪽으로 이동하는 데 몇도 이상 차이가 없어야합니다.

이상적으로는 편차가 커지면 비용이 증가합니다. 나는 이것이 그래프 이론과 관련된 문제라고 가정하고 싶지만, 다각형에서 어떻게 해야할지 잘 모르겠다. ...

붉은 점선 경로는 일반적인 알고리즘의 결과이다. 녹색은 내가 원하는 것에 관한 것이다. 편집 : 나는 그림을 조금 엉망진창했다. 명확히하기 : 빨간색 경로는 다각형 내부에서 가능한 가장 짧은 경로를 의미하며, 녹색 경로가 각도 제약 조건을 고려할 때 가능한 한 가장 짧기를 원합니다.

(내 다각형 (1), 같은 것을 보았다 경우 명확히하기 위해, 나는 경로가 (2) 같은, 단순히 지점 간의 직선되고 싶은 것)

(1) ,-------------------+  (2) ,-------------------+ 
    /    (B) |   /    (B) | 
    /     |  /   / | 
+--+      | -> +--+    / | 
|      +-+  |    / +-+ 
| (A)     |  | (A)-------------+  | 
+-----------------------+  +-----------------------+ 

Answer 1

이것은 실제로 더 많은 코멘트이지만 50 개의 평판이 필요하기 때문에 논평 할 수 없습니다 ... Otoh, 나는 만족스러운 대답이라고 생각하지 않습니다. 질문은 잘 정의되어 있지 않으므로 그러나 +1 흥미로운 질문 :-)

붉은 점선을주는 알고리즘은 경로의 시작과 끝 지점 사이의 직선에서부터 시작합니다 (완전히 다각형 안에 있지는 않습니다). 모서리를 치고 새로운 출발점으로 삼을 때까지 다각형의 가장자리. (그린 선은 실제로는 최단 경로가 아닙니다.) 이제 녹색 선은 싫어하는 부분 (잘못된 각도)을 대체하는 빨간색 선입니다. 경로가 더 길지만 웬만한 이유가 있습니다. 더 좋은 각도 (멋진 각도). 그러면 아래 예제에 "올바른"답변이 제공됩니다. (A)에서 (B)까지의 직선에서 시작하면 가장 짧은 경로이며 다각형 안에 있습니다. 이제이 선을보다 유리한 각도로 조각으로 바꿉니다. (이것은 당신이 일반적으로 많은 변화를 겪을 수도 있습니다 ...)

단지 몇 가지 생각.

Answer 2

Rapidly exploring random tree algorithm을 실행하고 축에 평행 한 몇도 방향 내에서 탐색 방향을 제한하고 선회 횟수를 줄이려면 큰 증분 거리를 선택하십시오. 기본적으로 원하는 방식으로 추론을 추가하십시오.

Rapidly-Exploring Random Trees: A New Tool for Path Planning은 임의의 나무를 신속하게 탐사하는 독창적 인 논문입니다.

Answer 3

나는 다른 답변과 크게 다른 답변을 추가 할 것입니다. 정규 경로 찾기 알고리즘의 결과에서 시작하여 확률 최적화를 실행하여 정점 추가, 정점 이동 및 정점 삭제를 통해 경로의 "비교적 직선성"(및 원할 경우 다른 지표)을 설명하는 적합성 함수를 최대화합니다. 경로를 유지하면서도 유효한 경로를 유지합니다.

일반적인 확률 적 최적화 방법에는 Simulated Annealing이 포함됩니다.