A Quick Hull-Building Algorithm for Planar Scattered Point Set
Linna Huang · Journal of Engineering Graphics · 2008
Convex hull is a basic topic in computational geometry and has been widely applied in practical engineering.Traditional convex hull generation algorithm generally requires two steps: ranking scattered points according to some properties and then generating convex hull.An algorithm named one-step for constructing convex hull from plane points is proposed based on the quick-sorting idea.This algorithm combines constructing convex hull from planar point set with the sorting process to quickly generate convex hull.The time complexity of the algorithm reaches minimum O(nlogn).The algorithm is applied to the Management Information System of Flood Area in Hebei Province with a good result.