// 수퍼 삼각형은 입력 점집합을 모두 포함하도록 충분히 큰 삼각형을 선택한다;
// 삼각화한 후 최외각이 convex가 아니면 수퍼 삼각형을 더 크게 다시 잡아야 함.
// 마지막 수정: 2021.4.7, 코드 간결화;
#define REMOVE_FLAG    (-1)
//
// max num of triangles = 2 * (N - 2) - 1;
// max num of edegs     = 3 * (N - 2);
int inc_delaunay_triangulation(POINT P[], int N, TRIANGLE *V) {
    // 메모리는 입력 점집합의 크기가 (N+3)인 경우를 기준으로 할당되어야 한다;
    int emax = 3 * (N + 1) ;
    EDGE *E = (EDGE *)malloc(sizeof(EDGE) * emax) ;
    set_supertriangle(P, N) ;
    // First element of triangle index is supertriangle vertex;
    push_tri(&V[0], N, N + 1, N + 2);
    int nt = 1;
    for (int i = 0; i < N; i++) {
        int ne = 0;
        /* 추가점(P[i])를 외접원에 포함시키는 삼각형을 모두 찾아 제거한다.
        ** 이들 삼각형의 공유되는 내부 edge를 제외한 나머지 외부 edge와
        ** 추가점으로 새로운 삼각형을 만들어 리스트에 추가한다.
        */ 
        for (int j = 0; j < nt; j++) {
            TRIANGLE *t = &V[j];
            if (incircle(P[t->a], P[t->b], P[t->c], P[i])) {
                // 제거되는 삼각형의 edge는 백업한다; 내부 edge는 중복된다.
                push_edge(&E[ne++], t->a, t->b);
                push_edge(&E[ne++], t->b, t->c);
                push_edge(&E[ne++], t->c, t->a);
                // P[i]를 포함하는 외접원 삼각형은 제거;
                // swap(j, nt-1) to remove triangle at j
                V[j--] = V[--nt];  
            }
        }
        // 중복되어 있는 내부 edge를 제거;
        remove_double_edges(E, ne);
        
        // 외부 edge와 P[i]가 만드는 새 삼각형을 리스트에 추가;
        for (int j = 0; j < ne; j++) {
            if (is_removed_edge(&E[j])) continue;
            push_tri(&V[nt++], E[j].a, E[j].b, i);
        }
    }
    //done with super_triangle;
    free(E);
    return remove_supertriangle_relics(N, V, nt) ;
}
void remove_double_edges(EDGE *E, int ne) {
    for (int j = 0; j < ne - 1; j++)
    	for (int k = j + 1; k < ne; k++)
            if (is_double_edge(&E[j], &E[k])) {
            	pop_edge(&E[j]); pop_edge(&E[k]);
            }
}
void push_tri(TRIANGLE *V, int a, int b, int c) {
    V->a = a; V->b = b; V->c = c;
}
int is_removed_edge(const EDGE *E) {
    return (E->a == REMOVE_FLAG || E->b == REMOVE_FLAG);
};
int is_double_edge(const EDGE* E1, const EDGE* E2) {
    return ((E1->a == E2->a && E1->b == E2->b) ||
            (E1->a == E2->b && E1->b == E2->a)) ;
}
void push_edge(EDGE *E, int a, int b) {
    E->a = a; E->b = b;
}
void pop_edge(EDGE* E) {
    E->a = E->b = REMOVE_FLAG;
}

// 삼각형 중에서 수퍼 삼각형의 꼭지점(N,N+1,N+2)을 가지고 있는 것을 제거;
int remove_supertriangle_relics(int N, TRIANGLE *V, int nt) {
    for (int i = 0; i < nt; i++)
        if (V[i].a >= N || V[i].b >= N || V[i].c >= N)
            // swap(i, nt - 1) to remove triangle at j
            V[i--] = V[--nt];
    return nt;
}

// A,B,C가 만드는 외접원에 D가 들어가는가?;
int incircle(POINT A, POINT B, POINT C, POINT D) {
	POINT AD = A - D, BD = B - D, CD = C - D;
    double ccw = CCW(A, B, C);
    double det = norm2(AD) * cross(BD, CD)
               + norm2(BD) * cross(CD, AD)
               + norm2(CD) * cross(AD, BD)
    if (ccw > 0) return det > 0; //CCW인 경우에..
    else         return det < 0; //CW인  경우에..    
}
728x90

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

Point in Polygon  (2) 2020.12.14
Catmull-Rom Spline  (0) 2020.12.07
Chain Hull  (2) 2012.09.16
Quick Hull  (2) 2012.09.16
Monotone Cubic Interpolation  (0) 2012.09.09
Posted by helloktk
,