728x90

monotone 폴리곤은 한 축 방향으로 꼭짓점의 좌표값이 단조 증가하는 형태를 갖는 단순 폴리곤이다. 단순 폴리곤을 monotone 폴리곤으로 분할하는 방법은 잘 알려져 있고 O(n log n)의 복잡도를 갖는다(나중에 이 부분을 자세히 리뷰할 예정이다). monotone 폴리곤은 한 방향에 대해서 이미 정렬이 되어 있기 때문이 그 방향으로 sweep-line 기법을 쓰면 선형 시간 내에 triangulation이 가능하다. 이러한 알고리즘은 이미지 처리에 적용하면 매우 효율적으로 이용이 가능하다. raster 상의 데이터는 scanline 방향으로 항상 정렬이 되어 있기 때문이다.


참고 : http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/PolyPart/polyPartition.htm

Algorithm Monotone_Triangulation
Input: Monotone polygon P (ccw-ness needed!)
Output: Set of triangles
(1) 주어진 폴리곤의 꼭지점을 x-좌표를 기준으로 정렬하여 V에 저장 (O(n) due to monotonicity).
(2) sweep-line 리스트(L)을 초기화 :: V의 처음 두 포인트(이벤트)를 넣음.
(3) while(V is not empty) do
       get next vertex (p) from V ;
       if (p is opposite to points in L) then
            while(size(L)>1) do
                out triangle { first(L), second(L), p }
                remove(first(L))
            end while
            add p to L;
       else 
            while ( size(L)>1 && ccw(last(L), previous(last(L)), p)) do
                 out triangle { last(L), previous(last(L)), p }
                 remove(last(L))
            end while
            add p to L
       end if
     end while/*입력이 ccw이면 ccw-test도 ccw로, cw면 test도 cw로 해야한다.*/ 

/**
**  http://blog.naver.com/helloktk/80051120809 에서 옮김.
*/

'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

댓글을 달아 주세요