词条 | Quickhull |
释义 |
Quickhull is a method of computing the convex hull of a finite set of points in the plane. It uses a divide and conquer approach similar to that of quicksort, from which its name derives. Its average case complexity is considered to be , whereas in the worst case it takes (quadratic). However, unlike quicksort, there is no obvious way to convert quickhull into a randomized algorithm. Thus, its average time complexity cannot be easily calculated. AlgorithmUnder average circumstances the algorithm works quite well, but processing usually becomes slow in cases of high symmetry or points lying on the circumference of a circle. The algorithm can be broken down to the following steps:
Pseudocode for 2D set of pointsInput = a set S of n points Assume that there are at least 2 points in the input set S of pointsQuickHull (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 where S1 are points in S that are on the right side of the oriented line from A to B, and S2 are points in S that are on the right side of the oriented line from B to A FindHull (S1, A, B) FindHull (S2, B, A) }FindHull (Sk, P, Q) { // Find points on convex hull from the set Sk of points // that are on the right side of the oriented line from P to 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 where S0 are points inside triangle PCQ, S1 are points on the right side of the oriented line from P to C, and S2 are points on the right side of the oriented line from C to Q. FindHull(S1, P, C) FindHull(S2, C, Q) }Output = Convex Hull See also
References
External links
2 : Convex hull algorithms|Articles with example pseudocode |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。