Efficient convex hull method for simple polygon set in plane
SanMin Wang · Computer Engineering and Applications Journal · 2011
An efficient algorithm for computing the convex hull of simple polygon set is proposed.Firstly,four vertex clusters are extracted from each polygon on the basis of extremity point,and are classified into four groups(right-top,left-top,left-bottom,right-bottom)by their locations in polygon.The convex hull can also be separated into four parts(right-top,left-top,left-bottom,right-bottom) and each part of the convex hull is associated with the same cluster group.Then,the cluster group is filtrated according to whether it is in the rectangle which is determined by the extremity point of polygon set.Finally,under the rule,four primary point clusters are gained,and they can constitute a polygon that has the same convex hull as the simple polygon set.The efficiency algorithm is easy to be realized and its time complexity is O(N).