单域单向水平倾角最小化圈绕凸壳新算法

本文作者实现了对二维点集卷包裹凸壳算法的同构化改进与创新,并依据同构化凸壳构造基本定理,提出效率更高的单域单向水平倾角最小化圈绕凸壳新算法。本新算法的同构化特点是：1）找出给定二维点集的最低点,即Y轴座标值最小点（若有多个最小点,则只取最左的最小点）,并作为凸壳初始顶点（即最低顶点）;2）过最近新顶点,作平行X轴正方向的同向顶点射线,并找出当前点集内对该顶点射线倾角最小的点,以作为逐边圈绕的最新顶点;3）在当前点集分布域中,删除由初始顶点、次新顶点、最新顶点构成三角形所覆盖的全部点。并当所剩当前点集非空时才从“2）”继续作逐边圈绕。

New Algorithm for Finding Convex Hull Based on Coiling with a Minimum Lever Pitch in Single Domain and Single Direction

In this paper,an isomorphic improving and creating for the algorithm of finding convex hull of a 2D point set with gift wrapping is realized;and according to the isomorphic fundamental theorem of the convex hull construction,a more efficient new algorithm to find a convex hull based on coiling with a minimum lever pitch in single domain and single direction is advanced.The isomorphic characters of the new algorithm are: 1) find out the bottommost point on the convex hull as the initial vertex of the convex hull,which has the minimum coordinate value of the Y axis among all the points in given 2D point set(if the bottommost point is not only one,the bottommost and leftmost point should be selected);2) passing the last new vertex,make the vertex's half line paralleled by X axis along positive direction,and find out a current vertex with a minimum pitch to its vertex's half line to be the newest vertex in coiling side by side;3) delete all points in the current distributed domain of points set covered by the triangle(which is constructed by the initial vertex,the second-newest vertex and the newest vertex),and loop from "2)" to coil side by side continuingly while the reminded point set is not empty.