Visibility Graph는 간단히 말해서 폴리곤의 볼록한 꼭지점을 잇는 선분들 중에서 폴리곤과 교차하지 않는 선분을 의미합니다. Visibility Grpah를 구하는 쉬운 방법으로 폴리곤의 모든 꼭지점을 연결하는 선분을 구한 다음(O(n^2)) 이 선분들이 폴리곤의 에지들과 교차하는지 판별(O(n^3))하면 됩니다. 이 방법은 간단하지만 복잡도가 O(n^3)으로 폴리곤을 구성하는 꼭지점이 많아지면 계산 시간이 3제곱에 비례하여 길어질 것입니다. 다른 방법으로 Howie Choset의 책 "Principles of Robot Motion - Theory, Algorithms, and Implementations"에서 소개된 Rotational Plane Sweep Algorithm (p.110 ~ p.116)을 사용하여 Visibility Graph를 만들 수도 있습니다. 이 때 복잡도는 O(n^2 log n)이 되어 그나마 퍼포먼스가 나아지게 됩니다.
다음 소스코드를 참고하시기 바랍니다.
visibility_graph_sweep.zip
0.07MB
아래는 상기 프로그램의 실행 결과입니다.
