'convex hull'에 해당되는 글 4건

  1. 2012.09.16 Chain Hull
  2. 2012.09.16 Quick Hull
  3. 2012.09.06 Brute Force Convex Hull Algorithm
  4. 2010.07.03 Finding the Convex Hull of Simple Polygon (2)

참고: 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


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

더보기

void BruteForceConvexHull(std::vector<CPoint>& points, std::vector<CPoint>& hull) {

    // O(n^3) ;

    hull.clear() ;

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

    std::vector<int> head; //hull을 구성하는 에지의 head index;

    std::vector<int> tail; //hull을 구성하는 에지의 tail index;

    for (int i = 0; i < points.size(); i++) {

        for (int j = 0; j < points.size(); j++) {

            if (i == j ) continue ;

            bool onHull = true;

            for (int k = 0; k < points.size(); k++) {

                if (i == k || j == k) continue;

                if (!ccw(points[i], points[j], points[k])) {

                    onHull = false;

                    break ;

                }

            }

            if (onHull) { //(i->j) edge is on the hull;

                head.push_back(j);

                tail.push_back(i);

            }

        }

    }

    if (head.size() < 1) return ;

    // hull을 구성하는 에지정보에서 단순폴리곤 만들기;

    int currIdx = 0;

    hull.push_back(points[tail[currIdx]]);

    hull.push_back(points[head[currIdx]]);

    for (int count = 1; count < head.size() - 1; count++) {//마지막은 다시 처음과 같아지므로 필요없다.

        for (int j = 0; j < head.size(); j++) {

            if (tail[j] == head[currIdx]) {

                currIdx = j;

                hull.push_back(points[head[currIdx]]);

                break;

            }

        }

    }

}

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

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

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
Inside Quadrilateral, Inside Triangle  (0) 2012.01.18
Posted by helloktk
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
저작자 표시 비영리 변경 금지
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
Posted by helloktk


티스토리 툴바