求解简单多边形和平面点集凸包的新算法

计算机科学 ›› 2007, Vol. 34 ›› Issue (12): 222-226.

求解简单多边形和平面点集凸包的新算法

刘光惠陈传波

华中科技大学计算机学院,武汉430074

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
国家863项目（2004AA420100）.

LIU Guang-Hui CHEN Chuan-Bo （Huazhong University of Science and Technology, Wuhan 430074）

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 沿一定方向遍历凸多边形的边，其内部在边的同一侧。本文依据凸多边形的这一特性，提出求解简单多边形凸包的新算法，进而扩展得到求解平面点集凸包的新算法。新点集凸包算法先找到点集的极值点，得到极值点间的候选点子集，再求得相邻极值点间的有序凸包点列，最后顺序连接极值点间的有序凸包点列，得到凸包。新算法达到目前平面点集凸包问题的渐进最好算法的时间复杂度O（n log h），其中，n为平面点集的点数，h为平面点集凸包的顶点数。相比相同复杂度的凸包算法，新算法简单、易于实现。又由于是顺序求得凸包上的点，新算法还具有更易于

关键词: 计算几何凸包极值点有序凸包点列有效空间

Abstract: Based on one of the characteristics of convex polygons, i.e. when the edges of a convex polygon are traversed along one direction, the interior of the convex polygon is always on the same side of these edges, a new algorithm for computing the convex hull

Key words: Computational geometry,Convex hull, Extreme points, Sorted convex hull point array, Space-efficlent

刘光惠陈传波. 求解简单多边形和平面点集凸包的新算法[J]. 计算机科学, 2007, 34(12): 222-226. https://doi.org/

LIU Guang-Hui CHEN Chuan-Bo （Huazhong University of Science and Technology, Wuhan 430074）. [J]. Computer Science, 2007, 34(12): 222-226. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed