Triangulating Monotone Polygon

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 에서 옮김.
*/