'Computational Geometry'에 해당되는 글 8건

  1. 2012.10.13 삼각형의 외접원 : 외접원의 반지름
  2. 2012.09.16 Chain Hull
  3. 2012.09.16 Quick Hull
  4. 2008.05.26 Rasterizing Voronoi Diagram
  5. 2008.05.26 Polygon Triangulation (II)
  6. 2008.05.25 Polygon Triangulation (4)
  7. 2008.05.22 Fortune's Sweep Algorithm
  8. 2008.05.22 Sweep Line Algorithm

세 개의 점 A, B, C가 만드는 삼각형의 외접원의 반지름을 구해보자. 


우선 세점이 일직선상에 놓이지 않기 위해서는 


이어야 한다. 

그림의 삼각형에서 각(BOC)가 각(BAC)의 두배이므로,


이 각도를 이용하면 삼각형의 면적은 세 변의 길이(a, b, c)와 외접원의 반지름(R)로 표현된다:


또한, 삼각형의 면적이 세 점이 직선상에 있는가를 테스트 하는 값으로 아래 식처럼 쓰여지므로,


외접원의 반지름은 다음과 같이 구할 수 있다:


#define SQR(x) ((x)*(x))

double circumradius(CPoint A, CPoint B, CPoint C) {

double ax = C.x - B.x; 

double ay = C.y - B.y;

double bx = A.x - C.x; 

double by = A.y - C.y;

double crossab = ax * by - ay * bx;

if (crossab != 0.) { 

double a = sqrt(SQR(ax) + SQR(ay));

double b = sqrt(SQR(bx) + SQR(by)); 

double cx = B.x - A.x; 

double cy = B.y - A.y;       

double c = sqrt(SQR(cx) + SQR(cy));

return (0.5 * a * b * c/fabs(crossab));

else

return ( -1.0 ); 

}


저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Posted by helloktk

참고: http://cm.bell-labs.com/who/clarkson/2dch.c 에 구현된 알고리즘을 수정함:

  1. 점들을 x-좌표의 크기(같으면, y좌표의 크기)순으로 정렬한다. 시작점은 hull의 꼭지점이 된다.
  2. x-좌표 순서대로 현재 점이 hull의 꼭지점인가를 검사한다: hull의 꼭지점이 되기 위해서는 직전까지 구성된 hull의 에지 왼편에 놓여야 한다. 오른편에 놓이면 직전까지 구성된 hull에서 현재 점이 왼편에 놓일때까지 꼭지점을 제거한다.
  3. 남는 점들을 1과정의 역순으로 정렬한다. 최대 x-좌표, 최소 y-좌표점이 다시 윗 hull의 시작점이 된다.
  4. x-좌표가 작아지는 순서대로 2번 과정을 수행한다.

/* A->B->C가 반시계방향으로 정렬되거나(< 0), 일직선상에 있으면(=) 참이다*/

static int ccw(POINT A, POINT B, POINT C) {

    double a = A.x - B.x, b = A.y - B.y, c = C.x - B.x, d = C.y - B.y;

    return (a * d - b * c) <= 0; /* true if points A,B,C counterclockwise */

}

static int cmpl(const void *a, const void *b) {

    POINT *A = (POINT* )a, *B = (POINT* )b;

    int v = (A)->x - (B)->x ;       //lower-hull은 x 증가: y감소 순으로 정렬;

    if (v > 0) return 1; 

    if (v < 0) return -1;

    v = (B)->y - (A)->y ;

    if (v > 0) return 1; 

    if (v < 0) return -1;

    return 0;

}

static int cmph(const void *a, const void *b) {

    return cmpl(b, a);      // upper-hull은 x감소, y-증가 순으로 정렬;

}

static int makeChain(POINT *V, int n, int (*cmp)(const void*, const void*)) {

    qsort(V, n, sizeof(POINT), cmp);

    // 꼭지점(i (>j))이 현재까지 만들어진 hull(s까지)의 에지보다도 더 오른쪽에 있으면(ccw(i,j,j-1)), 

    // 왼쪽에 위치할 때까지 기존 hull을 줄인다. 이 점을 hull에 추가.

    int s = 1;

    for (int i = 2; i < n; i++) {

        int j = s;

        while (j >= 1 && ccw(V[i], V[j], V[j-1])) j--; // ccw의 = 때문에 일직선상의 마지막점만 들어감;

        s = j + 1; // j = last index of hull;

        // (j + 1)에 새 hull-point을 추가;

        POINT t = V[i]; V[i] = V[s]; V[s] = t;

    }

    return s;

}

int chainHull(std::vector<POINT>& P, std::vector<POINT>& chull) {

    int n = P.size();

    if (n < 3) return 0;

    // copy to working array;

    chull.resize(n + 1);

    for (int i = 0; i < n; i++) chull[i] = P[i];

    /* make lower hull */

    int u = makeChain(&chull[0], n, cmpl);      

    lowhull.clear();

    /* make upper hull */   

    chull[n] = chull[0];

    u += makeChain(&chull[u], n - u + 1, cmph); 

    chull.resize(u);

    return u;

};


저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License

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

Chain Hull  (0) 2012.09.16
Quick Hull  (0) 2012.09.16
Monotone Cubic Interpolation  (0) 2012.09.09
Brute Force Convex Hull Algorithm  (0) 2012.09.06
Douglas-Peucker Algorithm  (0) 2012.05.03
Monotonic Cubic Spline Interpolation  (0) 2012.03.05
Posted by helloktk


Input = a set S of n points 
    Assume that there are at least 2 points in the input set S of points

QuickHull (S) { 
    // Find convex hull from the set S of n points

    Convex Hull := {} 
    Find left and right most points, say A & B, and add A & B to convex hull 
    Segment AB divides the remaining (n-2) points into 2 groups S1 and S2 
        S1 = {right side of line(A, B)}; 
        S2 = {right side of line(B, A)};
    FindHull (S1, A, B) 
    FindHull (S2, B, A) 
}

FindHull (Sk, P, Q) { 
   If Sk has no point, 

        then  return. 
    From the given set of points in Sk, find farthest point, say C, from segment PQ 
    Add point C to convex hull at the location between P and Q 
    Three points P, Q, and C partition the remaining points of Sk into 3 subsets: S0, S1, and S2 
        S1 = {right side of line(P,C)};

        S2 = {right side of line(C,Q)};

        S0 = {inside of triangle(P,C,Q)}; 
    FindHull(S1, P, C) 
    FindHull(S2, C, Q) 
}

Output = convex hull

참고: http://www.cse.yorku.ca/~aaw/Hang/quick_hull/Algorithm.html


#include "stdafx.h"

#include <vector>

// P가 line(A,B)의 완전히 왼쪽에 있는가?

static bool leftSide(CPoint P, CPoint A, CPoint B) {

더보기

double dist2ToLine(CPoint P, CPoint A, CPoint B) {

더보기

#define SWAP_POINT(A, B) {CPoint t = A; A = B; B = t;}

static void findHull(CPoint *S, int n, CPoint A, CPoint B, std::vector<CPoint>& hull) {

더보기

void findMaxMin(std::vector<CPoint>& pts) {

더보기

void hullToPolyline(std::vector<CPoint>& hull);

void quickHull(std::vector<CPoint>& pts, std::vector<CPoint>& hull) {

if (pts.size() < 3) return;

hull.clear();

//Find left and right most points, say A & B, and add A & B to convex hull ;

findMaxMin(pts);

hull.push_back(pts[0]);

hull.push_back(pts[1]);

int j = 2;

for (int i = 2; i < pts.size(); i++) {

if (leftSide(pts[i], pts[0], pts[1])) {

SWAP_POINT(pts[i], pts[j]);

j++;

}

}

//2,3,...,j-1;

findHull(&pts[2], j-2, pts[0], pts[1], hull);

//j,j+1,...,pts.size()-1;

if (j < pts.size()) // in order to avoid dereferencing &pts[pts.size()];

findHull(&pts[j], pts.size()-j, pts[1], pts[0], hull);

  hullToPolyline(hull);

};

출력 hull은 단순히 convex hull을 구성하는 정렬이 안된 점들만 주므로, hull의 에지를 구하고 싶으면 추가적인 수정이 필요함.

코드보기==========>

또한 입력점들의 순서를 그대로 유지하고 싶으면, double pointer를 이용하거나 복사복은 이용하여야 한다.

저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License

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

Chain Hull  (0) 2012.09.16
Quick Hull  (0) 2012.09.16
Monotone Cubic Interpolation  (0) 2012.09.09
Brute Force Convex Hull Algorithm  (0) 2012.09.06
Douglas-Peucker Algorithm  (0) 2012.05.03
Monotonic Cubic Spline Interpolation  (0) 2012.03.05
Posted by helloktk

이미지처리에서 보로노이 다이어그램으로 분할이 된 영역을 이용하여서 해당픽셀이 어느 보로노이 셀에 들어가 있는가를  알아야 하는 경우가 있다. 이 경우에 보로노이 다이어그램을 구하고, 각각의 셀을 폴리곤으로 만든 후 해당 픽셀점이 어느 폴리곤에 들어가는 가는 체크해야 한다. 그러나, 이 과정은 복잡하고, 해당점의 포함 여부를 판별하는 과정에서 계산이 많이 발생한다. 픽셀을 다루기 때문에 보다 간편하게 하는 것은 이미지 마스크를 이용하면, 해당픽셀의 어느 보로노이 셀에 들어있는지를 바로 알 수 있다. 특히 셀의 갯수가 적은 경우에는 마스크를 그레이이미지로 처리할 수 있어서 메모리사용도 줄일 수 있다.

보로노이 다이어그램의 이미지화 과정은 보로노이 알고리즘을 이용할 필요는 없고 단지 각각의 셀을 형성하는 픽셀들은 그 셀의 중심까지의 거리가 다른 중심까지의 거리보다 가깝다는 사실만 이용한다.

void rasterize_voronoi(BYTE *image, int width, int height, POINT vorocenter[], int N) {
       //RGB 컬러이미지이므로 image는 적어도 (3 * width * height) 크기의 버퍼를 가져야 한다.
       //make color lookup table;
       DWORD *color = new DWORD [N] ; //RGBQUAD;
       // 랜덤 컬러 LUT를 만듬;
       for(int i=0; i<N; i++) {
            color[i]=(rand()%256)<<16|(rand()%256)<<8|(rand()%256);
       }
       for(int y=0; y<height; y++){
          for(int x=0; x<width; x++){
               int min_id=0;
               int dist2_min=1000000000;//caution overflow;
               for(int k=0; k<N; k++){
                    int dx=x-vorocenter[k].x;
                    int dy=y-vorocenter[k].y;
                    int ds2=dx*dx+dy*dy;
                    if(ds2<dist2_min) {
                        dist2_min=ds2;
                        min_id=k;
                    }
              }
              //set pixel value(here,we use RGB-color) wih verocenter[i]'s id
              *image++ = (color[min_id]>>16) & 0xFF;  //B;
              *image++ = (color[min_id]>>8) &xFF;      //G;
              *image++ = (color[min_id]) & 0xFF;         //R;
         }
     }
     // draw cell center;
     delete[] color ;
}

사용자 삽입 이미지

신고
크리에이티브 커먼즈 라이선스
Creative Commons License

'Image Recognition' 카테고리의 다른 글

Bayesian Decision Theory  (1) 2008.06.17
Gaussian Mixture Model  (2) 2008.06.07
Rasterizing Voronoi Diagram  (0) 2008.05.26
RANSAC Algorithm  (0) 2008.05.24
Contour Tracing  (0) 2008.05.22
Gausssian Scale Space  (0) 2008.05.22
Posted by helloktk

단순폴리곤의 삼각화 알고리즘의 다른 구현이다. 이전 구현과 같은 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);
}


최적화 후:





신고
크리에이티브 커먼즈 라이선스
Creative Commons License

'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
Posted by helloktk

코드제거: 2012년 9월4일;  코드구현: http://kipl.tistory.com/13

폴리곤의 내부를 겹치지 않게 분할하는 것을 폴리곤의 삼각화라고 한다. N개의 꼭지점이 있는 폴리곤의 경우에 N-2개의 서로 겹치지 않은 삼각형을 내부에 가지게 되며, 폴리곤의 경계와 겹치지 않는  N-3개의 내부 경계라인을(diagonal)을 가지게 된다. 

사용자 삽입 이미지


많은 경우에 만들어진 삼각형의 외접원의 크기의 차이가 심하게 나타나서 면적하게 균일한 모양으로 형성되지 않는다. 이 경우에 인접하는 두개의 삼각형으로 형성된 사변형에서 현재의 대각변에 교차되는 대각변으로 재 분할을 하여서 만든 삼각형을 검사하여서 다시 구성할 수 있다. 물론 삼각형의 외접원의 반경이 작은 경우가 균일하게 삼각화된다. Polygon Optimizing을 참고하기 바란다.

*simple 폴리곤이 아닌 경우는 아래의 링크를 참조하기 바란다.

1).O(n log(n)) 복잡도를 갖는 polygon triangulation algorithm;
==>'Fast Polygon Triangulation based on Seidel's Algorithm'.
==>http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html
2).Poly2Tri 홈페이지:
==>Fast and Robust Simple Polygon Triangulation With/Without Holes by Sweep Line Algorithm
==>http://www.mema.ucl.ac.be/~wu/Poly2Tri/poly2tri.html

triangulation notes : (몇개의 사이트는 없어졌다).
Nice lecture notes:
http://arachne.ics.uci.edu/~eppstein/junkyard/godfried.toussaint.html
▶ Narkhede & Manocha's description/code of Seidel's alg:
http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html
▶ Some school project notes w/ triangulation overview & diagrams:
http://www.mema.ucl.ac.be/~wu/FSA2716-2002/project.html
▶ Toussaint paper about sleeve-following, including interesting
description & opinion on various other algorithms:
http://citeseer.ist.psu.edu/toussaint91efficient.html
▶ Toussaint outline & links:
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html
http://geometryalgorithms.com/algorithms.htm
▶ History Of Triangulation Algorithms
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Thierry/thierry507webprj/complexity.html
▶ Ear Cutting For Simple Polygons
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian//cutting_ears.html
▶ Intersections for a set of 2D segments
http://geometryalgorithms.com/Archive/algorithm_0108/algorithm_0108.htm
▶ Simple Polygon Triangulation
http://cgafaq.info/wiki/Simple_Polygon_Triangulation
▶ KKT O(n log log n) algo
http://portal.acm.org/citation.cfm?id=150693&dl=ACM&coll=portal&CFID=11111111&CFTOKEN=2222222
▶ Poly2Tri implemenation, good notes and looks like good code, sadly the
license is non-commercial only:(최근에 사이트가 존재하지 않음)
http://www.mema.ucl.ac.be/~wu/Poly2Tri/poly2tri.html
▶ FIST
http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html
▶ Nice slides on monotone subdivision & triangulation:
http://www.cs.ucsb.edu/~suri/cs235/Triangulation.pdf
▶ Interesting forum post re monotone subdivision in Amanith:
http://www.amanith.org/forum/viewtopic.php?pid=43
 

신고
크리에이티브 커먼즈 라이선스
Creative Commons License

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

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
Triangulating Monotone Polygon  (0) 2008.05.22
Posted by helloktk


Fortune2.zip

사용자 삽입 이미지



사용자 삽입 이미지

평면에서 보로노이 다이어그램을 계산하는 알고리즘중에 1980년대에 Fortune에 의해서 발견이 된 Sweep line 알고리즘에 대해서 살펴보겠다. 이 알고리즘은 보로노이 다이어그램 계산문제의 optimal한 답 중에 하나이다(~O(n * log(n)). Fortune이 자신의 알고리즘을 직접 C로 구현한 것이 있는데 이것은 웹상에서 쉽게 구할 수 있다. 그러나 알고리즘의 얼개는 간단하나 구현에 들어간 자료구조등을 간단히 않아서 코드를 이해하는 것이 쉽지 않았다(이에 비하면 incremental delaunay triangulation은 매우 단순하다). 몇번을 간단한 자료구조를 이용해서 재 작성을 해보려고 했는데 잘 되지 않았다. 인터넷에서 구할 수 있는 다양한 구현소스를 분석해 보았으나 쉬운 것을 찾기가 힘들었다(triangle.c에서도 구현되어 있고, 자바로도 구현이 된것을 찾을 수 있다.) 원래의 목적은 Fortune의 코드가 메모리 처리를 잘못하여 메모리 leak이 발생하여서 이 문제를 해결하려고 시도한 것인데, 메모리 문제는 자바의 경우에 처럼 가비지 콜렉터를 만들어서 처리할 수는 있다. 이 알고리즘의 구현에 들어가는 기본적인 자료구조는 priority queue와 balanced binary tree이다. 이들의 기본적인 구현은 이미 잘 알려져 있으므로 이것들을 직접적으로 알고리즘에 적용하는 문제만 남는다. balanced binary tree로 만들어진 자료구조를 쓰면 자료를 찾는 시간이 O(log(n))의 시간 복잡도를 주지만, 이것이 알고리즘을 직관적으로 보는 것을 방해하므로 여기서는 이중연결리스트을 이용하도록한다. 전체적으로 알고리즘은 O(n^2) 의 복잡도를 가진다.


1. priority queue 구성:
주어진 입력점들을 가지고 구성한다. 알고리즘중간에 세점으로 원이 구성이 되는 circle event가 생성이 되는데 이것은 따로 event 큐를 구성한다. event의 우선순위는  x 좌표의 순서에 의해서 구성하고 동일한 x 좌표값에 대해서는 y값이 작은 순서대로 구성한다(compare 구조체에서 point와 event에 대한 비교연산자를 정의한다).

std::priority_queue<point, std::vector<point>, compare> points ; // 입력점(point-구조체)들로
                                                                                           // 만들어지는 priority_queue ;
std::priority_queue<event*, std::vector<event*>, compare> events; //circle events(event-구조체);

2. site event 처리;
sweep line(x=const)은 전체 평면을 반으로 나누는 역할을 한다. 알고리즘은 sweep 라인이 쓸고 지나간 영역에서만 관심영역이다. sweep라인과 주어진 점은 하나의 포물선을 정의할 수 있다(주어짐 점이 포물선의 초점을 구성함). 따라서 sweep 라인이 진행하면 sweep line의 왼편의 입력점들은 각각 하나의 포물선을 형성하고, 이 포물선들의 구간중에서 sweep라인에 가장 가까운 부분은 포물선 arc로 연결인 되는 하나의 beach line을 형성한다.  sweep라인이 새로운 입력점을 지나면 여기서 새로운 포물선arc가 생기는데, 이것은 이미 만들어진 beach라인을 구성하는 포물선arc 중 하나를 둘로 가르고, 그 자신이 새로운 beach 라인의 일부를 구성하게 된다; sweep라인이 전진하면서 비치라인을 구성하는 arc가 다른 arc에 파 묻혀서 없어지는 경우가 생긴다. 이 경우가 circle event가 만들어지는 시점이다.

.......................

*           BEFORE                                  AFTER
*
*           new point                               new arc
*               |                                       |
*     __        |       _____                   __      |       _____
*       \      \|/        |                       \    \|/       arc a
*        \      `         |                        \    `       __|__
*         \     X         |                         p------X    __|__<-- arc c
*      a   |             arc a                  a    |            |
*         /               |                         /            arc a
*        /                |                        /              |
*      /__              __|__                     /__           __|__
*   __/    \              |                    __/   \            |
*           \             |                           \           |
*            \            |                            \          |
*       b     |          arc b                  b       |        arc b
*            /            |                            /          |
*           /             |                           /           |
*        __/            __|__                      __/          __|__


3. circle event 처리;
sweep라인이 각각의 site에 도달하면 새로운 포물선의 arc가 비치라인에 추가가 되는데 sweep 라인으로 부터 멀어진 arc들은 어느 시점에서 없어져야 한다. 이것은 인접하는 세개의 arc들의 교점이 현재의 sweepline 위치에서 하나로 만들어져서 중앙의 arc가 없어지는 경우로 이것을 circle event라고 한다. 이때 만들어지는 교점은 보로노이에지의 꼭지점을 구성하게 된다. circle event에서는 나머지 두개의 남은 arc의 교점이 trace하는 새로운 에지가 생기게 된다.

*    __
*       \
*   a    \
*         \
*   __     |
*     `   /
*      \ /
*   b   X           <-- Arc b is overtaken at point X (this is a circle center)
*     / \
*   __,   \
*          \
*           \
*   c        |
*           /
*          /
*         /

*
*       BEFORE                                              AFTER
*
*      \        arc a                                   \
*        \                                               \              a.s0
*         \   <-- a.s0                                    \               |
*          \                                               \             \|/
*           \                                               \             `
*            \                                               \
*    arc b   X     <-- termination point                      .--------------------     <-- new segment
*           /                                                /          
*          /                                                /            .
*         /   <-- c.s1                                     /            /|\ 
*        /                                                /              |
*       /    arc c                                       /              c.s1
*      /      

                                 

//포물선 arc를 정의하기 위한 클래스;

struct arc {
    point p;                //focus of parabola;
    arc *prev, *next;       //double linked-list;
    event *e;
    ////////////////////////////////////////////////////
    seg *s0 ;               //edge of voronoi starting from break point;
    seg *s1;                //edge of voronoi starting from break point;
    arc(point _p, arc *_a=0, arc *_b=0)
        : p(_p), prev(_a), next(_b), e(0), s0(0), s1(0) {}
};

// voronoi edge를 정의하는 segment class;
struct seg {
    point start, end;                                             //defines segment;
    bool done;
    int ref ;                                                          //referece count in order to distingush the double edges;
    seg(point _p, int _ref=0)
        : start(_p), end(0,0), done(false), ref(_ref)
    { output.push_back(this); }                             //garbage collector;
    void finish(point p) { if (done) return; end = p; done = true; }
};

//메인 wrapper;

int fortune_main(std::vector<POINT>& pts,          //voronoi points;
                       std::vector<EDGE>& edges)     //voronoi edges;

{
      //point priority_queue구성;
      std::vector<POINT>::iterator iter=pts.begin();
      for(; iter !=pts.end(); iter++) {
          point P(iter->x, iter->y) ;
          points.push_back(P);
      }
      //body of algorithm ;
      while(!points.empty()) {
           if(!events.empty() && events.top()->x <= points.top().x)
                 process_event() ; //circle event ;
           else
                 process_site() ;   //site event;
      }
      //for remaining circle events if any;
      while(!events.empty())
           process_event() ;
                                                                     
      //2. prepare output edges and clean memory;
}

arc * root=NULL;                              //global variable;
void process_site() {
    point P= points.top(); points.pop(); //because popping return void in STL;
    if(!root) { // root of double linked list for arcs(global);
        root = new arc(P) ; return  ;
    }
    //
    for(arc* a = root; a; a=a->next) {
         point Q;
         if(intersect(P, a, &Q)) { //arc a와 점P에서의 포물선(degenerate 된)이 만나는 점 Q;
              duplicate_arc(P, a) ; //교차하는 arc를 둘로 만든다
                                            //(다음 arc가 있고, 만약에 이것과도 교차하면 circle event 임으로 제외)
              insert_new_arc(P, a, a->next) ;//새 arc를 중간에 삽입한다;
              //새 arc의 에지 세팅 ::교차점을 출발점으로 하는 두개의 반직선을 만든다:
              //도착점은 circle event에 대부분 결정되고, 나머지는 후처리 과정에서 결정됨)
              a = a->next ;
              a->prev->s1 =a->s0 = new seg(Q, ref_count) ;
              a->next->s0 =a->s1 = new seg(Q, ref_count++) ; //쌍으로 생성되는 반직선을 identify하기
                                                                                    //위해서 동일번호를 부여함.
              //새 site 추가로 비치라인을 구성하는 arc의 초점들과 circle event를 만들 수 있는가 체크함;
              check_circle_event(a, P.x) ;
              check_circle_event(a->prev, P.x) ;
              check_circle_event(a->next, P.x) ;
         }
    }//for-;
};
//
void process_event(){
    event *e = events.top(); events.pop();
    if (e->valid) {
        // start a new edge.(single edges)
        seg *s = new seg(e->p, ref_count++);
        // remove the associated arc from the front. and attach a new segment;
        arc *a = e->a;
        remove_arc(a, s);
        // finish the edges before and after a==>new voronoi vertex;
        if (a->s0) a->s0->finish(e->p);
        if (a->s1) a->s1->finish(e->p);        
        // recheck circle events on either side of p:
        if (a->prev) check_circle_event(a->prev, e->x);
        if (a->next) check_circle_event(a->next, e->x);
        delete a;
    }
    delete e;
};
// Look for a new circle event for arc a.
void check_circle_event(arc *a, double x0/*=current sweep-line*/) {
    // Invalidate any old event.
    if (a->e && a->e->x != x0)  a->e->valid = false;
    a->e = NULL;
    if (!a->prev || !a->next) return;
    double maxx;
    point O;
    point& A = a->prev->p ;
    point& B = a->p ;
    point& C = a->next->p ;
    //collinear가 아니고, 최대값이 현재의 site event위치보다도 큰 경우에;
    if (circle(A, B, C, &maxx, &O) && maxx > x0) { //점 A,B,C에 의해서 형성이 되는 원의 중심(O)과 최우측x(maxx) 좌표를 얻음;
        // create new event.
        a->e = new event(maxx, O, a);
        events.push(a->e);
    }
};

나머지 함수들은 모두 단순한 구현이므로 생략한다;

보로노이 에지는 seg collector에서 각각의 segment를 끄집어내어서 그리면 된다. 그러나 각각의 segment는 보로노이 에지를 전체를 커버하는 것이 아니다. site event인 경우에는 항상 듀얼로 반직선을 생성하는데. 이 두개의 반직선이 하나의 보로노이 에지를 정의한다(따라서 ref를 참조하면 온전한 하나의 에지를 찾을 수 있다). circle event 의 경우에는 에지가 듀얼로 생성하지 않았으므로 이 경우에는 하나의 segment가 그 에지를 표현한다. 에지 억세스를 쉽게 하기 위해서는 모든 에지를 듀얼구조로 만들어서 사용할 수 있다.

n 개의 점들의 보로노이 다이어그램은 얼마나 많은 꼭지점과 에지를 가질까?

이것은 오일러 공식 V-E+F=2를 사용하면 된다. 보로노이 다이어그램은 경우 바깥족으 에지들은 무한대로 연결이 되어 있다. 이것을 무한대에서 가상의 꼭지점을 가정하고 그것에 연결이 되어 있다고 생각하면 된다. 따라서 V --> V+1 로 계산을 하여야한다.

오일러 공식 : V+1-E + F= 2; 여기서 F=n임을 알 수 있다. (n개의 점들이 하나의 face상에 노여 있음)
그리고 하나의 에지가 두개의 꼭지점을 연결하므로 각각의 꼭지점에서 나간 에지의 합(=deg(v))을 계산하면 2*E개임을 알 수 있다.
             sum deg(v) = 2 * E ;
그런데 각각의 꼭지점에서는 적어도 3개이상의 에지와 연결이 되어 있으므로 위식의 좌변은
             (V+1) * 3 <= 2 * E;
를 준다. 따라서 오일러 공식과 이 부등식을 연관시키면
             V<=  2*n - 5 ;
             E<=  3*n - 6;
임을 알 수 있다. 즉 필요한 메모리의 양은 입력점의 수의 선형적으로 비례한다.

따라서 전체 이벤트의 갯수는 site 이벤트와 꼭지점에 해당하는 circle event만큼이 있으므로 O(3*n)정도이다. 각각의 event에 대해서 arc노드를 검색해야하므로 O(n) 번 탐색을 해야한다(balanced binary tree의 경우에는 log(n)). 따라서 알고리즘의 복잡도는 O(n^2 ( n*log(n))이다.
/**
** http://blog.naver.com/helloktk/80041603288
*/

** 첨부된 실행파일으로 알고리즘을 테스트해 볼 수 있다(중복된 입력점은 제거하였고, 세점이 일직선상에 놓인 것을 방지하기 위해서 작은 랜덤값을 첨가하였다)


신고
크리에이티브 커먼즈 라이선스
Creative Commons License

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

Polygon Triangulation  (4) 2008.05.25
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
Posted by helloktk

(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이 지나간 후의 교차점.

사용자 삽입 이미지


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

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


신고
크리에이티브 커먼즈 라이선스
Creative Commons License

'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


티스토리 툴바