|
(詳細はconvex hull of a finite set of points in the plane. It uses a divide and conquer approach similar to that of quicksort, which its name derives from. Its average case complexity is considered to be O(n * log(n)), whereas in the worst case it takes O(n2) (quadratic). ==Algorithm== Under 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: # Find the points with minimum and maximum x coordinates, those are bound to be part of the convex hull. # Use the line formed by the two points to divide the set in two subsets of points, which will be processed recursively. # Determine the point, on one side of the line, with the maximum distance from the line. The two points found before along with this one form a triangle. # The points lying inside of that triangle cannot be part of the convex hull and can therefore be ignored in the next steps. # Repeat the previous two steps on the two lines formed by the triangle (not the initial line). # Keep on doing so on until no more points are left, the recursion has come to an end and the points selected constitute the convex hull. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Quickhull」の詳細全文を読む スポンサード リンク
|