Sweep Line Algorithm

(1) closest pair in the planar point set
     * brute force : O(n^2) --> O(n log n), see also divide and conquer algorithm.
     * ref : http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairPS.html 

(2) simplicity of polygon :

Shamos-Hoey Algorithm

 

 

 

(3) voronoi diagram :Fortune algorithm

 

 

(4) segment intersection : Bentley-Ottmann Algorithm

      * 파란색 점 : sweep-line과 교차하는 세그먼트들 간의(붉은색으로 표시)의 교차점으로(before sweep-line)로 point 이벤트 큐에 들어간다.
      * 청록색 점 : sweep-line이 지나간 후의 교차점.

sweep-line알고리즘을 구현하는데서 스텝별로 쪼개서 구현하려고 하니 조금 귀찮은 작업들이 많아진다 (DC에 그려지는 것을 자동으로 저장하는 부분을 만들어서 매 스텝마다 캡처하는 작업은 줄였다). 그러나 근본적인 문제는 입력되는 데이터에 degeneracy가 있는 경우다. 이것 때문에 가장 기본적인 세그먼트 intersection 부분부터 다시 살펴보아야 했다.

/**
** http://blog.naver.com/helloktk/80051980882 에서 옮긴 글.
*/