// 수퍼 삼각형은 입력 점집합을 모두 포함하도록 충분히 큰 삼각형을 선택한다;
// 삼각화한 후 최외각이 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 |