728x90

단순 폴리곤을 사다리꼴로 분해하는 알고리즘이다(삼각형은 평행한 변 중에 하나의 길이가 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 에서 옮김.
*/

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

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

댓글을 달아 주세요