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 := {}
가장 왼쪽(A)과 오른쪽(B)에 있는 두 점을 찾아 convec hull에 추가;
선분 AB을 기준으로 나머지 (n-2)개 점들을 두 그룹 S1과 S2로 나눔;
S1 = 선분 AB의 오른쪽에 놓인 점;
S2 = 선분 BA의 오른쪽에 놓인 점;
FindHull (S1, A, B)
FindHull (S2, B, A)
};
FindHull (Sk, P, Q) {
If Sk has no point,
then return.
선분 PQ에서 가장 멀리 떨어진 점(C)을 찾아 convex hull에서 P와 Q의 사이에 추가;
세점 P, C, Q는 나머지 Sk의 나머지 점들을 세 그룹S0, S1, and S2
S0 = 삼각형 PCQ에 포함되는 점;
S1 = 선분 PC의 오른쪽에 놓인 점;
S2 = 선분 CQ의 오른쪽에 놓인 점;
FindHull(S1, P, C)
FindHull(S2, C, Q)
}
Output = convex hull참고: http://www.cse.yorku.ca/~aaw/Hang/quick_hull/Algorithm.html
// P가 line(A, B)의 완전히 왼쪽에 있는가?
static bool leftSide(CPoint P, CPoint A, CPoint B) ;
더보기
static bool leftSide(CPoint P, CPoint A, CPoint B) {
int ax = P.x - A.x, ay = P.y - A.y;
int bx = B.x - A.x, by = B.y - A.y;
return (ax * by - ay * bx) >= 0;
};double dist2ToLine(CPoint P, CPoint A, CPoint B);
더보기
double dist2ToLine(CPoint P, CPoint A, CPoint B) {
double dx = (B.x - A.x), dy = (B.y - A.y);
double den = (dx * dx + dy * dy);
if (den == 0.) return 0; //degenerate;
double du = (P.x - A.x), dv = (P.y - A.y);
double dist = (du * dy - dv * dx);
return dist * dist / den; //distance-square!
};#define SWAP_POINT(A, B)
static void findHull(CPoint *S, int n, CPoint A, CPoint B, std::vector <CPoint>& hull) ;
더보기
static void findHull(CPoint *S, int n, CPoint A, CPoint B, std::vector<CPoint>& hull) {
if (n < 1) return ;
//Find furtherst point
double maxdist = 0;
for (int i = 0; i < n; i++) {
double dist = dist2ToLine(S[i], A, B);
if (dist > maxdist) {
SWAP_POINT(S[0], S[i]);
maxdist = dist;
}
}
if (maxdist == 0.) return ; //collinear case;
hull.push_back(S[0]);
int j = 1;
for (int i = 1; i < n; i++) {
if (leftSide(S[i], A, S[0])) {
SWAP_POINT(S[i], S[j]);
j++;
};
};
int k = j;
for (int i = j; i < n; i++) {
if (leftSide(S[i], S[0], B)) {
SWAP_POINT(S[i], S[k]);
k++;
}
};
//1,...,j-1;
findHull(&S[1], j-1, A, S[0], hull);
//j,...,k-1;
findHull(&S[j], k-j, S[0], B, hull);
};void findMaxMin(std::vector<CPoint>& pts) ;
더보기
void findMaxMin(std::vector<CPoint>& pts) {
int minx = pts[0].x, maxx = minx;
int minid = 0, maxid = 0;
for (int i = pts.size(); i-->1;) {
if (pts[i].x > maxx) maxid = i, maxx = pts[i].x;
if (pts[i].x < minx) minid = i, minx = pts[i].x;
}
SWAP_POINT(pts[0], pts[minid]); if (maxid == 0) maxid = minid;
SWAP_POINT(pts[1], pts[maxid]);
};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의 에지를 구하고 싶으면 추가적인 수정이 필요함.
더보기
static int cmph(const void *a, const void *b) {
CPoint *A = (CPoint *)a , *B = (CPoint *)b ;
int v = (A->x - B->x) ;
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 cmpl(const void * a, const void *b) {
return cmph(b, a);
};
void hullToPolyline(std::vector<CPoint>& hull) {
CPoint A = hull[0];
CPoint B = hull[1];
// 가장 멀리 떨어진 두 점(hull[0], hull[1])을 연결하는 직선을 기준으로 프로젝션을 구하여서 순차적으로
int k = 2;
for (int i = 2; i < hull.size(); i++) {
if (leftSide(hull[i], A, B)) {
SWAP_POINT(hull[i], hull[k]); k++;
};
};
// k-1; last index of hull left side of line(A,B);
// upper part reordering:
qsort(&hull[0], k, sizeof(CPoint), cmph);
//lower part reordering;
if (k < hull.size())
qsort(&hull[k], hull.size()-k, sizeof(CPoint), cmpl);
}
};또한 입력점들의 순서를 그대로 유지하고 싶으면, double pointer를 이용하거나 복사복은 이용하여야 한다.
728x90
'Computational Geometry' 카테고리의 다른 글
| Incremental Delaunay Triangulation (1) | 2020.12.01 |
|---|---|
| Chain Hull (2) | 2012.09.16 |
| Monotone Cubic Interpolation (0) | 2012.09.09 |
| Brute Force Convex Hull Algorithm (0) | 2012.09.06 |
| Curvature of a Curve (0) | 2012.08.07 |
