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로 해야한다.*/ 
/* 구현 코드(C++)의 일부이다.*/
struct endpoint {
int vid; /* polygon vertex id */
double* x; /* X coordinate of the endpoint */
double* y; /* Y coordinate of the endpoint */
} ;
//x-크기순서대로--> y-크기순 서대로; (ascending-order);
static
int point_compare(double* x1, double* y1, double* x2, double* y2) {
if (*x1 > *x2) return 1;
if (*x1 < *x2) return -1;
if (*y1 > *y2) return 1;
if (*y1 < *y2) return -1;
return 0;
}
//qsort에서 사용;
static
int endpoint_compare(const void* p1, const void* p2) {
endpoint* e1 = *(endpoint**) p1;
endpoint* e2 = *(endpoint**) p2;
return point_compare(e1->x, e1->y, e2->x, e2->y);
}
//
class endpointqueue {
int n; /* total number of endpoints */
int next; /* index of next endpoint on queue */
endpoint* data; /* array of all endpoints */
endpoint** sorted; /* sorted list of endpoint pointers */
bool create(int npoly, double polyx[], double polyy[]);
public:
~endpointqueue() {
if(data) delete[] data ;
if(sorted) delete[] sorted;
}
endpointqueue() : data(NULL), sorted(NULL), n(0), next(0) {}
endpointqueue(int npoly, double polyx[], double polyy[]) {
create(npoly, polyx, polyy);
} ;
endpoint * getnext() { return (next >= n) ? NULL : sorted[next++];}
} ;
bool endpointqueue::create(int n, double polyx[], double polyy[]) {
data = new endpoint [n] ;
this->n = n ;
this->next = 0;
for (int i = 0; i < n; i++) {
data[i].x = &polyx[i] ;
data[i].y = &polyy[i] ;
data[i].vid = i;
};
sorted = new endpoint* [n] ;
for (i = 0; i < n; i++) {
sorted[i] = &data[i];
};
//non-optimal sorting; use monotonicity of input;
qsort(sorted, n, sizeof(endpoint*), endpoint_compare);
return true ;
}
//deque의 행동을 재정의할 필요가 있음.
struct sweepline {
int n; /* number of vertices in polygon */
endpoint* deque;
int bot, top;
sweepline() : n(0), deque(NULL) {}
sweepline(int n_) {
n = n_; bot = -1; top = -1;
deque = new endpoint [n] ;
}
~sweepline(){ if(deque) delete [] deque;}
endpoint* add(endpoint* e) ;
void removefirst() { if (bot < top) bot++;} //safe::size()>1
void removelast() { if (top > bot) top--;} //safe::size()>1;
int size() { if (top >= 0 && bot >= 0 && top >= bot) return top - bot + 1; else return 0;}
endpoint* getlast() { ASSERT(size() > 0); return &deque[top];}
endpoint* getprelast() { ASSERT(size() > 1); return &deque[top - 1];}
endpoint* getfirst() { ASSERT(size() > 0); return &deque[bot ];}
endpoint* getsecond() { ASSERT(size() > 1); return &deque[bot + 1];}
bool opposite(endpoint* e) ;
void draw(CDC *pDC, DWORD color = RGB(0xFF, 0, 0)) ;
};
endpoint* sweepline::add(endpoint* e) {
if (bot == -1 && top == -1) //first adding;
bot = 0;
top++;
deque[top].x = e->x ;
deque[top].y = e->y ;
deque[top].vid = e->vid ;
return &deque[top];
}
bool sweepline::opposite(endpoint* e) {
if (e->vid == ((deque[top].vid + 1) % this->n))
return false;
else
return true ;
}
void monotone_triangulate(CPoint P[], int n,
void (*print_triangle)(int a, int b, int c)) {
double *polyx = new double [n] ;
double *polyy = new double [n] ;
for (int i = 0; i < n; i++) {
polyx[i] = P[i].x;
polyy[i] = P[i].y;
};
//
endpointqueue eq(n, polyx, polyy);
sweepline sl(n);
endpoint *e ;
sl.add(eq.getnext());
sl.add(eq.getnext());
while ((e = eq.getnext())) {
TRACE("event=%d(x=%5.0f, y=%5.0f)\n", e->vid, *e->x, *e->y);
if (sl.opposite(e)) {
while (sl.size() > 1) {
//(first, second, p);
print_triangle(sl.getfirst()->vid, sl.getsecond()->vid, e->vid);
sl.removefirst();
}
sl.add(e);
} else {
while (sl.size() > 1 && isccw(sl.getlast(), sl.getprelast(), e)) {
//triangle(last, previous(last), p);
print_triangle(sl.getlast()->vid, sl.getprelast()->vid, e->vid);
sl.removelast();
}
sl.add(e);
}
}
//
delete [] polyx;
delete [] polyy;
};/*
** http://blog.naver.com/helloktk/80051120809 에서 옮김.
*/
728x90
'Computational Geometry' 카테고리의 다른 글
| Polygon Fill (0) | 2008.05.22 |
|---|---|
| Fortune's Sweep Algorithm (0) | 2008.05.22 |
| Trapezoidalization (0) | 2008.05.22 |
| Optimizing Polygon Triangulation (0) | 2008.05.22 |
| Sweep Line Algorithm (0) | 2008.05.22 |
