다각형과 점이 2D에 있으면 점에 가장 가까운 다각형의 형상 (꼭짓점 또는 모서리)을 어떻게 찾을 수 있습니까?

순진한 방법은 다각형의 각 가장자리에 대해 가장 가까운 가장자리의 점을 찾은 다음 가장 가까운 점을 가져 오는 것입니다. 더 빠른 알고리즘이 있습니까? 내 목표는 2D 슈퍼 마리오 갤럭시 스타일의 플랫폼을 구현하는 것입니다.다각형과 점이 2D에 있으면 점에 가장 가까운 다각형의 형상 (꼭짓점 또는 모서리)을 어떻게 찾을 수 있습니까?

은 분명히이이 비디오에서와 같이 보로 노이 영역을 수행 할 수 있습니다 : http://www.youtube.com/watch?v=Ldh2YKobuWo

그러나, 나는 가장자리뿐만 아니라 포인트를 다루는 모든 보로 노이 알고리즘을 찾을 수 없습니다. 아이디어?

2011-10-04 Jake

다각형이 볼록면, 보로 노이 계산의 오버 헤드는 순진 접근법의 오버 헤드를 훨씬 초과합니다.

이 작업이 여러 번 실행되고 포인트가 약간 변경되면 3 세그먼트 만 확인하면됩니다 (생각해 보면 많은 체크를 가정하고 이동할 때 가장 가까운 에지는 인접한 가장자리)

2011-10-04 20:59:46

마지막 부분이 사실이 아닙니다. 예를 들어 중간 가까이에서 시작하면 폴리곤의 반대편에있는 세그먼트로 바뀔 수 있습니다. –

@ Jean-FrançoisCorbett 다각형의 내부에 있다면 사실입니다. –

다행히도 내 응용 프로그램의 경우 문제의 지점이 다각형 내부에 있지 않습니다. 만세. – Jake

각 모서리에 대해 point-line distance을 계산 한 다음 가장 짧은 것을 선택하십시오. 바로 가기가 없습니다. This site에는 좋은 설명이 있으며 다양한 언어로 된 구현도 있습니다.

그러나 "주어진 점에 가장 가까운 가장자리에있는 점"을 찾는 것은 계산 상 불필요한 중간 결과입니다.

2011-10-04 21:00:25

답변