단순 폴리곤을 사다리꼴로 분해하는 알고리즘이다(삼각형은 평행한 변 중에 하나의 길이가 0인 것으로 취급한다). 이 알고리즘은 복잡한 폴리곤을 한 방향으로 정렬된 보다 단순한 형태로 바꾸어, 효율적인 알고리즘의 디자인과 적용이 가능하게 한다. 이 역시 sweep-line 알고리즘을 이용한다.

(1) 폴리곤의 꼭짓점들을 y-값(or x) 값으로 크기순 서로 정렬한다.

(2) sweep-line L이 정렬된 각각의 꼭짓점을 스캔한다.

(3) 각각의 꼭짓점에서 폴리곤 내부에 들어가는 최대의 평행 세그먼트를 계산한다.
    (녹색과 붉은색(붉은 색은 꼭짓점이 세그먼트 중간에 있는 것을 표시함))

** 알고리즘 복잡도 : O(n log n)

사용자 삽입 이미지

붉은색 세그먼트에 포함된 꼭지점에서 위/아래의 세그먼트의 꼭짓점으로 대각선을 그을 수가 있는데, 이 대각선을 이용하면 폴리곤을 monotonic(y방향)한 분리가 가능하다.
**관련 자료: www.cs.jhu.edu/~misha/Spring16/04.pdf
/**
** http://blog.naver.com/helloktk/80051167220 에서 옮김.
*/

728x90

'Computational Geometry' 카테고리의 다른 글

Polygon Fill  (0) 2008.05.22
Fortune's Sweep Algorithm  (0) 2008.05.22
Triangulating Monotone Polygon  (0) 2008.05.22
Optimizing Polygon Triangulation  (0) 2008.05.22
Sweep Line Algorithm  (0) 2008.05.22
Posted by helloktk
,