利用初始包容壳求二维点集凸壳的自适应算法

二维点集凸壳应用广泛,算法较多,但实现较为复杂。虽然"利用正负划分性求平面点集凸包的最优算法"1]计算准确,计算过程中只用到加、减、乘和比较运算,时间复杂性低,但存在极值点分布情况不全面及分情况处理的局限。为弥补这些不足,首先从分析凸壳的3~8个基本极值点出发,将补全后的分布情况融入初始包容壳中;然后详细给出一种经过完善的追踪凸壳的新算法。该算法继承了文献1]算法的优点,不仅考虑全面,而且化繁于简,并可应用于三维点集。该算法是一种自适应算法。

Auto-adapted algorithm for constructing convex hull of 2D point set utilizing initial inclusion hull

The convex hull of 2D point set is applied widespreadly with abundant algorithms but complex implementation. The algorithm, "optimum algorithm for constructing convex hull of planar point set utilizing plus or minus characteristic of demarcation", is accurate and low complex only with operation of addition, subtraction, multiplication and comparision. But it has limitation of uncomprehensive distribution of extreme point. To make up for the shortage, an improved algorithm was proposed based on analyzing the 3 to 8 fundamental extreme points of convex hull and merging complementary distribution into initial inclusion hull. This comprehensive and simple auto-adapted algorithm can be used for 3D point set.