728x90

기하 알고리즘을 특히 폴리곤 관련 알고리즘을 테스트하기 위해서는 폴리곤 데이터를 만들어야 한다. 여기서 2차원의 점들을 이용하여 간단히 simple polygon을 만드는 방법을 소개한다.

 

단순 폴리곤을 만들기 위해서는 점들을 정렬을 해야 한다. 각각의 점들을 x 축에 프로젝션을 시키면 x 축에 대해서 정렬이 된다(같은 x 값인 경우에는 y의 크기대로 정렬). 따라서 x 값으로 정렬된 점들을 쭉 이어나가면 하나의 poly-line을 만들 수 있다. poly-line의 끝을 잇는다고 해서 단순 폴리곤이 항상 만들어지지는 않는다. 이를 해결하기 위해서는 점들을  한 직선을 기준으로 위-아래로 분리하고, 직선의 윗부분은 x 값이 큰 순서대로 정렬을 하고, 아래 부분은 x 값이 작은 순서대로 정열을 하면 폴리 라인이 아닌 단순 폴리곤을 얻을 수 있다. 직선은 어떻게 잡을까? 이것은 가장 작은 x 값을 갖는 점과 가장 큰 x 값을 같은 점을 잇는 직선을 생각하면 편리하다.

// cross(BC, BA)
// A->B-C: 반시계(C가 AB 왼편: > 0), 시계(C가 AB오른편: < 0), 일직선(0);
int CCW(CPoint A, CPoint B, CPoint C) {
    C.x -= B.x; C.y -= B.y; 
    A.x -= B.x; A.y -= B.y;
    return C.x * A.y - C.y * A.x;
}
int comp(const void *A, const void *B) { //x->y의 크기 순서대로 정렬;
    int ax = ((CPoint *)A)->x - ((POINT *)B)->x ;
    if (ax > 0) return  1;
    if (ax < 0) return -1;
    int ay = ((CPoint *)A)->y - ((CPoint *)B)->y ;
    if (ay > 0) return  1;
    if (ay < 0) return -1;
    return 0;
}
void MakeSimplePolygon(std::vector<CPoint>& pts, std::vector<CPoint>& spoly) {
    if (pts.size() < 1) return;
    int maxid = 0, minid = 0;
    for (int i = 1; i < pts.size(); i++) {
        if (pts[i].x > pts[maxid].x) maxid = i;
        if (pts[i].x < pts[minid].x) minid = i;
    }
    std::vector<CPoint> LP, RP;
    for (int i = 0; i < pts.size(); i++) {
        if (i == maxid || i == minid) continue;
        // 기준선의 왼편(LP)/오른편(RP)에 놓인 점 분리;
        if (CCW(pts[minid], pts[maxid], pts[i]) >= 0) LP.push_back(pts[i]); 
        else RP.push_back(pts[i]);
    }
    if (LP.size() > 0) 
        qsort(&LP[0], LP.size(), sizeof(CPoint), comp);
    if (RP.size() > 0)    
        qsort(&RP[0], RP.size(), sizeof(CPoint), comp);
	
    spoly.clear();
    spoly.push_back(pts[minid]);
    for (int i = 0; i < LP.size(); i++) spoly.push_back(LP[i]);
    spoly.push_back(pts[maxid]);
    for (int i = RP.size() - 1; i >= 0; i--) spoly.push_back(RP[i]);
    // spoly = clockwise simple polygon;
};

다른 방법으로는 위와 같은 직선을 만들고, 아랫부분의 점들의 convex hull을 구성하고, 나머지 점들을 마찬가지의 방법으로 정렬을 하여 폴리곤을 만들거나, 아니면 한 점을 잡아서(맨 아래 오른쪽) 그 점을 기준으로 해서 나머지 점들을 각도에 대해서 정렬을 한 다음 그 정렬된 순서대로 폴리곤을 구성하면 된다.

기준점에 대한 각도를 정렬하여서 만든 예(동일한 각도가 생기는 경우에는 기준점에서의 거리로 비교)

**네이버 블로그에서 이전;

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

Minimum Bounding Rectangle  (0) 2021.03.15
Minimum Enclosing Circle  (0) 2021.03.01
단순 다각형 만들기  (0) 2021.01.25
단순 다각형의 Convex hull  (0) 2021.01.24
단순 다각형의 무게중심  (0) 2021.01.24
단순 다각형의 면적(2D)  (0) 2021.01.23
Posted by helloktk

댓글을 달아 주세요

728x90

평면 상에 주어진 점들의 convex hull을 구하는 알고리즘 중의 하나인 Graham scan에서는 먼저 주어진 점들을 한 점을 기준으로 각도로 정렬하는 과정이 필요했다. 그러면 점들이 순차적으로 연결된 단순 다각형에서는 sorting과정이 없이 Graham scan 알고리즘을 바로 적용이 가능한 것일까? 이에 대한 counter example은 쉽게  찾을 수 있다. 단순 폴리곤에 대해서도 항상 각도에 대한 정렬 과정이 필요한 것인가? 답은 아니다. 정렬 과정이 없이도 단순 폴리곤에 대해서는 쉽게 convex hull을 구할 수 있는 알고리즘이 존재한다. 정렬 과정이 없이 단순 폴리곤의 convex hull을 찾는 알고리즘에 대해서 알아보자.

Melkman Algorithm;

우선 폴리곤의 이웃하는 세 꼭짓점을 잡아서, 반시계 방향의 삼각형을 구성한다. 이 삼각형을 deque에 넣는다 (bottom = top). 폴리곤을 순환하면서 새 점이 들어올 때 이미 만들어진 convex hull의 내부점이 아니면 이 점이 포함되도록 convex hull을 업데이트한다: Graham scan 알고리즘의 scanning 과정을 bottom을 기준으로 반시계 방향으로 convexity를 만족시킬 때까지 bottom을 제거하고, top을 기준으로는 시계방향으로 convexity를 만족시킬 때까지 top을 제거한다. 이 과정이 끝나면 새 점을 deque에 추가한다. 이 과정을 나머지 모든 점들에 대해서도 진행한다.

int LEFTSIDE(CPoint A, CPoint B, CPoint C){ // cross(AB, AC) > 0: C가 AB 대해서 왼쪽
	return ((B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x)) > 0;
}
int convexhull_spolygon(std::vector<CPoint>& pts, std::vector<CPoint>& hull) {
    int N = pts.size();
    if (N < 3) return 0;
    std::vector<CPoint> Q(2 * N + 1);  // deque;
    int bot = N - 2, top = bot + 3;
    // |0|1|......|N-2|N-1|N+0|N+1|N+2|..............|2N|;
    //              bot    top    
    Q[bot] = Q[top] = pts[2];
    if (LEFTSIDE(pts[0], pts[1], pts[2])) { //2->0->1->2; Q에 ccw로 입력;
        Q[bot + 1] = pts[0]; Q[bot + 2] = pts[1];
    } else {
        Q[bot + 1] = pts[1]; Q[bot + 2] = pts[0];
    }
    int i = 2; // last touched index;
    while (++i < N) {
        // 기존의 convex_hull에 들어있으면 제외.
        if (LEFTSIDE(Q[bot + 0], Q[bot + 1], pts[i]) && 
            LEFTSIDE(Q[top - 1], Q[top + 0], pts[i]))
            continue;
        // bottom에 대해서 ccw 방향으로 체크(bot 증가 방향)
        // pts[i]가 (bot)->(bot+1)라인의 오른쪽에 있으면, 기존의 bottom을 제외;
        while (!LEFTSIDE(Q[bot], Q[bot + 1], pts[i]) && (bot < top)) bot++;
        Q[--bot] = pts[i];
        // 추가점에서 top->top-1의 ccw 방향으로 convexity 체크하여 만족하지 않은 경우
        // top을 감소
        while (!LEFTSIDE(Q[top - 1], Q[top], pts[i]) && (top > bot)) top-- ;
        Q[++top] = pts[i];
    }
    hull.resize(top - bot);
    for (int i = hull.size() - 1; i >= 0; --i) hull[i] = Q[i + bot];
    return hull.size();
};

**네이버 블로그 이전;

 

 

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

Minimum Enclosing Circle  (0) 2021.03.01
단순 다각형 만들기  (0) 2021.01.25
단순 다각형의 Convex hull  (0) 2021.01.24
단순 다각형의 무게중심  (0) 2021.01.24
단순 다각형의 면적(2D)  (0) 2021.01.23
삼각형 외접원의 Inclusion Test  (0) 2020.12.30
Posted by helloktk

댓글을 달아 주세요

728x90

단순 다각형의 무게중심(center of gravity or center of mass)은 다각형을 균일한 밀도의 판으로 생각했을 때 판의 무게중심과 같다. 가장 단순한 다각형인 삼각형의 무게중심은 세 꼭짓점의 산술평균으로 표현된다.

$$ \text{CoG} = \frac{1}{3} ({{\bf P} + {\bf Q} + {\bf R}}).$$

다각형은 삼각형으로 분할되므로 이 분할된 삼각형의 무게중심을 이용하면 쉽게 계산할 수 있다. 분할된  삼각형의 무게중심을 면적으로 가중치를 준 평균값이 다각형의 무게중심이 된다. 

 

실제 계산에서는 다각형을 삼각 분할하지 않고도 간단한 방법에 의해서 무게중심을 구할 수 있다. 원점과 다각형의 각 변의 꼭짓점을 이용해서 삼각형들을 구성하면 원래의 다각형을 겹치게(원점이 내부에 있으면 겹침이 없다) 분할할 수 있다. 분할된 삼각형으로 무게중심을 구할 때 겹치는 영역의 기여를 제거해야 한다. 그런데 다각형 밖의 영역을 분할하는 삼각형은 다각형 내부를 분할하는 삼각형과는 다른 orientation을 가지게 된다. 삼각형의 면적은 한 꼭짓점을 공유하는 두 변의 외적에 비례하므로, 반대의 orientation을 갖는 삼각형은 자동으로 반대 부호의 면적을 가지게 된다. 따라서 분할된 삼각형 면적 가중치를 외적으로 주어서 무게중심을 구하면 겹치는 영역이 자동으로 상쇄되는 효과를 얻을 수 있다.

노란색 영역에 있는 분할 삼각형은 음의 면적

$$\begin{align} \text{CoG} &= \frac{1}{\text{다각형 면적}} \sum (\text{삼각형 CoG})  (\text{면적})  \\ &= \frac{1}{\text{다각형 면적}} \sum \frac{1}{3} \left( {\bf V}_i + {\bf V}_{i+1} + {\bf O}\right ) \frac{ {\bf V}_{i} \times {\bf V}_{i+1} }{2} \\ &= \frac{1}{3}\frac{1}{   \text{다각형 면적} }\sum ( {\bf V}_{i} + {\bf V}_{i+1}) \frac{{\bf V}_{i} \times {\bf V}_{i+1}}{2} \end{align}$$ 

다각형의 면적($=\sum \frac{1}{2}({\bf V}_i \times {\bf V}_{i+1})$)을 구할 때 삼각형과 동일하게 orientation에 따라 부호를 포함하도록 설정하면 다각형의 면적 부호가 삼각형의 면적 부호로 상쇄되므로 다각형의 orientation에 무관하게 성립하는 공식이 된다.

POINT polygon_centroid(POINT V[], int N) {
    double cx = 0, cy = 0, area2 = 0;
    for(int i = 0, j = N - 1; i < N; j = i++) {
        double tri_area2 = V[i].x * V[j].y - V[i].y * V[j].x;
        cx += (V[i].x + V[j].x) * tri_area2;
        cy += (V[i].x + V[j].x) * tri_area2;
        area2 += tri_area2;
    }
    cx /= 3 * area2;
    cy /= 3 * area2;
    return POINT(cx, cy)
};

** 네이버 블로그에서 수정 이전;

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

단순 다각형 만들기  (0) 2021.01.25
단순 다각형의 Convex hull  (0) 2021.01.24
단순 다각형의 무게중심  (0) 2021.01.24
단순 다각형의 면적(2D)  (0) 2021.01.23
삼각형 외접원의 Inclusion Test  (0) 2020.12.30
Point in Polygon  (2) 2020.12.14
Posted by helloktk

댓글을 달아 주세요

728x90

평면상의 다각형(모서리의 교차가 없는 단순 다각형)의 면적을 구하는 것은 단순하지 않을 것처럼 보이지만 계산식은 무척이나 간단하게 주어진다. 기본적인 아이디어는 다각형에 임의의 점을 찍으면 이 점과 이웃한 두 개의 꼭짓점으로 형성이 되는 삼각형의 합으로 다각형을 분할할 수 있다. 분할된 삼각형의 면적을 구하여 합산하면 다각형의 면적을 구할 수 있다.

 

세 점 ${\bf P, Q, R}$(이 순서대로 반시계방향으로 배열)이 만드는 삼각형의 면적은

$$\text {삼각형의 면적}=  \frac{1}{2} ({\bf R} - {\bf  Q})  \times ( {\bf P} - {\bf Q}); \quad  (\Rightarrow \text {시계 방향이면 면적이 음수})$$

로 주어지므로, 꼭짓점이 ${\bf P}_0(x_0, y_0), {\bf P}_1(x_1, y_1),....$(반시계 방향)으로 주어지는 $N$각형의 면적은 아래와 같이 주어진다. 

$$\begin{align} \text{다각형 면적} &= \sum \text{각 삼각형의 면적} \\ &= \frac{1}{2}\sum ({\bf P}_{i+1}-{\bf Q})\times ({\bf P}_{i}-{\bf Q})\quad \quad ({\bf Q}\text{는  임의의 점})\\ &= \frac{1}{2} \sum\left(  {\bf P}_{i+1} \times {\bf P}_{i} - {\bf P}_{i+1}\times {\bf Q} + {\bf P}_{i} \times {\bf Q}\right) \\ &=\frac{1}{2} \sum {\bf P}_{i+1} \times {\bf P}_{i} \\ &= \frac{1}{2}\sum \left( x_{i+1} y_{i} -x_{i}y_{i+1} \right) \end{align}$$

이 결과는 $\bf Q$에 무관하다. 다각형의 꼭짓점이 시계 방향으로 정렬이 된 경우는 면적이 음수로 나온다(윈도우 DC는 위-아래가 역전되어 있으므로 orientation이 반대로 보인다). 그리고 이 공식은 단순 다각형에만 적용이 되고 모서리의 교차가 있는 경우에는 적용이 되지 않는다.

double simple_polygon_area2D(POINT point[], int N) {
    double area = 0;
    for (int i = 0, j = N - 1; i < N; j = i++) 
        area += (point[i].x * point[j].y) - (point[i].y * point[j].x);
    area /= 2;
    // return area;  // signed area;
    return area < 0 ? -area: area;
}

**네이버 블로그 수정 이전;

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

단순 다각형의 Convex hull  (0) 2021.01.24
단순 다각형의 무게중심  (0) 2021.01.24
단순 다각형의 면적(2D)  (0) 2021.01.23
삼각형 외접원의 Inclusion Test  (0) 2020.12.30
Point in Polygon  (2) 2020.12.14
Incremental Delaunay Triangulation  (1) 2020.12.01
Posted by helloktk

댓글을 달아 주세요

728x90

It is well known that the convex hull of a set of n points in the (Euclidean) plane can be found by an algorithm having worst-case complexity O(n log n). In this note we give a short linear algorithm for finding the convex hull in the, case that the (ordered) set of points from the vertices of a simple (i.e., non-self-intersecting) polygon.

ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/81/887/CS-TR-81-887.pdf

http://deepblue.lib.umich.edu/bitstream/2027.42/7588/5/bam3301.0001.001.pdf
We present space-efficient algorithms for computing the convex hull of a simple polygonal line in-place, in linear time. It turns out that the problem is as hard as stable partition, i.e., if there were a truly simple solution then stable partition would also have a truly simple solution, and vice versa. Nevertheless, we present a simple self-contained solution that uses O(log n) space, and indicate how to improve it to O(1) space with the same techniques used for stable partition. If the points inside the convex hull can be discarded, then there is a truly simple solution that uses a single call to stable partition, and even that call can be spared if only extreme points are desired (and not their order). If the polygonal line is closed, then the problem admits a very simple solution which does not call for stable partitioning at all.

http://springerlink.metapress.com/content/5clwpcjenldf5a78/fulltext.pdf

Posted by helloktk

댓글을 달아 주세요

728x90

단순 다각형(simple polygon)의 삼각화 알고리즘의 다른 구현이다. 이전 구현과 같은 Ear-Clipping 알고리즘을 써서 구현한 것이다. 폴리곤의 각 꼭짓점을 돌면서 현재 꼭짓점의 직전과 직후의 꼭짓점들로 구성한 삼각형이 Ear인가를 체크해서 맞으면 이 삼각형을 추가하고, 현 꼭짓점은 주어진 폴리곤에서 제거를 한 후 나머지에 대해 테스트를 계속한다. $N$ 개의 꼭짓점을 가지는 단순 폴리곤의 경우에 $N-2$ 개의 삼각형으로 분해가 된다.

주어진 폴리곤이 시계방향으로 정렬된 경우는 반시계 방향으로 바꾸어서 정렬시킨 후 작업을 한다. 구현된 알고리즘의 복잡도는 ${\cal O}(N^2)$이다. 

last update: 2012.10.03;

static bool leftSide(CPoint *P, CPoint *A, CPoint *B) ;
더보기
static bool leftSide(CPoint *P, CPoint *A, CPoint *B) {
    // P가 선분(A,B)의 왼쪽 또는 위에 있는가?
    return ((B->x - A->x) * (P->y - A->y) - ( B->y - A->y) * (P->x - A->x)) >=0;
}
static bool insideTriangle (CPoint *P, CPoint *A, CPoint *B, CPoint *C) ;
더보기
static bool insideTriangle (CPoint *P, CPoint *A, CPoint *B, CPoint *C) {    
    // 반시계방향으로 정렬된 삼각형(A,B,C)의 안에 점 P가 있는가?(경계포함);
    if (!leftSide(P, A, B)) return false;
    if (!leftSide(P, B, C)) return false;
    if (!leftSide(P, C, A)) return false;
    return true;
};​
static bool earTest(int a, int b, int c, int nv, int *V, CPoint *points) ;
더보기
static bool earTest(int a, int b, int c, int nv, int *V, CPoint *points) {
    // Check the triangle {V[a], V[b], V[c]} is an Ear; 
    CPoint *A  = &points[V[a]]; 
    CPoint *B  = &points[V[b]]; 
    CPoint *C  = &points[V[c]]; 
    // colinear(A->B->C) or concave인가를 체크; 반시계 방향으로 정렬된 입력점이므로 왼편에
    // 있으면 concave이므로 ear가 안된다;
    if (leftSide(B, A, C)) return false; 
    // 이미 만들어진 삼각형의 꼭지점이 포함되는지 체크한다;
    for (int k = 0; k < nv; ++k) {
        if ((k == a) || (k == b) || (k == c)) continue;
        if (insideTriangle(&points[V[k]], A, B, C)) return false;
    }
    return true;
};
static double polygonArea2(std::vector<CPoint>& pts) ;
더보기
static double polygonArea2(std::vector<CPoint>& pts) {
    double area2 = 0.;
    for (int p = pts.size() - 1, q = 0; q < pts.size(); p = q++)
        area2 += pts[p].x * pts[q].y - pts[p].y * pts[q].x;
    return (area2);
}
/* 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);  // contains vertex indices;
    // 주어진 단순폴리곤을 반시계방향으로 정렬;
    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");
            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' 카테고리의 다른 글

Wu's Line Algorithm  (1) 2008.06.02
Brute Force Triangulation  (1) 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
Posted by helloktk

댓글을 달아 주세요

728x90

단순 폴리곤을 사다리꼴로 분해하는 알고리즘이다(삼각형은 평행한 변 중에 하나의 길이가 0인 것으로 취급한다). 이 알고리즘은 복잡한 폴리곤을 한 방향으로 정렬된 보다 단순한 형태로 바꾸어, 효율적인 알고리즘의 디자인과 적용이 가능하게 한다. 이 역시 sweep-line 알고리즘을 이용한다.

(1) 폴리곤의 꼭짓점들을 y-값(or x) 값으로 크기순 서로 정렬한다.

(2) sweep-line L이 정렬된 각각의 꼭짓점을 스캔한다.

(3) 각각의 꼭지점에서 폴리곤 내부에 들어가는 최대의 평행 세그먼트를 계산한다.
    (녹색과 붉은색(붉은 색은 꼭짓점이 세그먼트 중간에 있는 것을 표시함))

** 알고리즘 복잡도 : O(n log n)

사용자 삽입 이미지

붉은색 세그먼트에 포함된 꼭지점에서 위/아래의 세그먼트의 꼭짓점으로 대각선을 그을 수가 있는데, 이 대각선을 이용하면 폴리곤을 monotonic(y방향)한 분리가 가능하다.
**관련 자료: www.cs.jhu.edu/~misha/Spring16/04.pdf
/**
** http://blog.naver.com/helloktk/80051167220 에서 옮김.
*/

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

Polygon Fill  (0) 2008.05.22
Fortune's Sweep Algorithm  (0) 2008.05.22
Triangulating Monotone Polygon  (0) 2008.05.22
Trapezoidalization  (0) 2008.05.22
Optimizing Polygon Triangulation  (0) 2008.05.22
Sweep Line Algorithm  (0) 2008.05.22
Posted by helloktk

댓글을 달아 주세요

728x90

(1) closest pair in the planar point set
     * brute force : O(n^2) --> O(n log n), see also divide and conquer algorithm.
     * ref : http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairPS.html 

사용자 삽입 이미지

(2) simplicity of polygon :

Shamos-Hoey Algorithm

 

 

 

사용자 삽입 이미지

(3) voronoi diagram :Fortune algorithm


 

 

사용자 삽입 이미지

(4) segment intersection : Bentley-Ottmann Algorithm

      * 파란색 점 : sweep-line과 교차하는 세그먼트들 간의(붉은색으로 표시)의 교차점으로(before sweep-line)로 point 이벤트 큐에 들어간다.
      * 청록색 점 : sweep-line이 지나간 후의 교차점.

사용자 삽입 이미지

sweep-line알고리즘을 구현하는데서 스텝별로 쪼개서 구현하려고 하니 조금 귀찮은 작업들이 많아진다 (DC에 그려지는 것을 자동으로 저장하는 부분을 만들어서 매 스텝마다 캡처하는 작업은 줄였다). 그러나 근본적인 문제는 입력되는 데이터에 degeneracy가 있는 경우다. 이것 때문에 가장 기본적인 세그먼트 intersection 부분부터 다시 살펴보아야 했다.

/**
** http://blog.naver.com/helloktk/80051980882 에서 옮긴 글.
*/

 

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

Polygon Fill  (0) 2008.05.22
Fortune's Sweep Algorithm  (0) 2008.05.22
Triangulating Monotone Polygon  (0) 2008.05.22
Trapezoidalization  (0) 2008.05.22
Optimizing Polygon Triangulation  (0) 2008.05.22
Sweep Line Algorithm  (0) 2008.05.22
Posted by helloktk

댓글을 달아 주세요