단순폴리곤의 삼각화 알고리즘의 다른 구현이다. 이전 구현과 같은 Ear-Clipping 알고리즘을 써서 구현한 것이다. 폴리곤의 각 꼭지점을 돌면서 현재 꼭지점의 직전과 직후의 꼭지점들로 만들어지는 삼각형이 Ear인가를 체크해서 Ear이면 삼각형을 하나를 얻고, 현재의 꼭지점은 주어진 폴리곤에서 제거를 한 후에 테스트를 계속 진행한다. nv 개의 꼭지점을 가지는 단순폴리곤의 경우에 nv-2 개의 삼각형으로 분해가 된다.
알고리즘은 주어진 폴리곤이 시계방향인 경우에는 반시계방향으로 수정하여서 작업을 한다. 구현된 알고리즘의 복잡도는 O(N^2)이다.
last update: 2012.10.03;
static bool leftSide(CPoint *P, CPoint *A, CPoint *B) {
static bool insideTriangle (CPoint *P, CPoint *A, CPoint *B, CPoint *C) {
static bool earTest(int a, int b, int c, int nv, int *V, CPoint *points) {
static double polygonArea2(std::vector<CPoint>& pts) {
/* Polygon should be simple(ccw or cw);*;
int polygonTriangulation(std::vector<CPoint>& points, std::vector<Triangle>& triplets) {
int nv = points.size();
if (nv < 3) return 0;
triplets.clear();
triplets.reserve(nv - 2);
std::vector<int> V(nv) ;
// 주어진 단순폴리곤을 반시계방향으로 정렬한다;
if (polygonArea2(points) > 0)
for (int v = 0; v < nv; ++v) V[v] = v;
else
for (int v = 0; v < nv; ++v) V[v] = nv - 1 - v;
// nv-2개의 꼭지점을 차례로 제거한다. 한개의 꼭지점이 제거될때마다 삼각형이 하나씩
// 생긴다;
int err_detect = 2*nv; /* error detection */
for (int v = nv - 1; nv > 2; ) {
// 단순폴리곤이 아닌 경우에 무한루프를 도는 것을 방지;
if (0 >= (err_detect--)) {
TRACE("triangulate::ERROR\n");
triplets.clear();
return 0;
}
// <u,v,w>는 연속하는 세꼭지점의 인덱스임;
int u = v % nv;
v = (u + 1) % nv;
int w = (v + 1) % nv;
if (earTest(u, v, w, nv, &V[0], &points[0])) {
triplets.push_back(Triangle(points[V[u]], points[V[v]], points[V[w]]));
// 꼭지점 V[v]를 제거함;
for (int k = v; k < nv - 1; ++k)
V[k] = V[k + 1];
--nv;
/* resest error detection counter */
err_detect = 2*nv;
}
}
return triplets.size();
//number of triangle = (nv-2);
}
최적화 후:
'Computational Geometry' 카테고리의 다른 글
| 삼각형 외접원의 Inclusion Test (0) | 2008.05.29 |
|---|---|
| Brute Force Triangulation (0) | 2008.05.28 |
| Polygon Triangulation (II) (0) | 2008.05.26 |
| Polygon Triangulation (4) | 2008.05.25 |
| Polygon Fill (0) | 2008.05.22 |
| Fortune's Sweep Algorithm (0) | 2008.05.22 |
