一种改进的快速三维凸包生成算法及实现

doi:10.3969/j.issn.1007130X.2011.

J4 ›› 2011, Vol. 33 ›› Issue (2): 129-132.doi: 10.3969/j.issn.1007130X.2011.

一种改进的快速三维凸包生成算法及实现

李志,李儒琼

(上海师范大学信息与机电工程学院,上海 200234)(School of Information and Mechatronics Engineering,Shanghai Normal University,Shanghai 200234,China

收稿日期:2010-02-26 修回日期:2010-06-15 出版日期:2011-02-25 发布日期:2011-02-25
通讯作者: 李志
作者简介:李志(1985),男,湖南岳阳人，硕士生，研究方向为计算几何、CAD/CAM。李儒琼(1964),男,湖北黄石人，博士，副教授，研究方向为CAD/CAM、数控技术。
基金资助:
上海市自然科学基金资助项目（09ZR1423600）;上海市教委科技创新项目（09YZ165）

An Improved Algorithm and Implementation of ThreeDimensional Convex Hulls

LI Zhi,LI Ruqiong

(School of Information and Mechatronics Engineering,Shanghai Normal University,Shanghai 200234,China)

Received:2010-02-26 Revised:2010-06-15 Online:2011-02-25 Published:2011-02-25

摘要/Abstract

摘要：

本文阐述一种快速的三维凸包构造新算法，算法吸收了QuickHull方法中每次选用凸包的极值点(ExtremalPoint)来构造新凸包的思想，在此基础上改进为选用二次极值点的方法来构造新凸包，并结合“冲突图”(ConflictGraph)来更新凸包外的点和当前凸包的拓扑结构关系，从而取得了快速排除凸包的内部点、缩小问题规模、实现高效构建凸包的效果。本文算法的时间复杂度为O(nlgr)，通过实验证明本文算法与QuickHull算法相比平均执行消耗时间减少20%，因此本算法具有理论和实际应用价值。

关键词: 三维凸包, 二次极值, 增量算法

Abstract:

A novel and efficient approach to threedimensional convex hulls is presented in the paper, compared with the QuickHull method , the quadratic extremalpoint is employed to construct the convex hull in the method, combining with "conflict map" (ConflictGraph) of this bipartite graph structure to update the topological relations between the points outside the convex hull and the current convex hull. This algorithm's time complexity is O(nlgr)，and the experimental results shows that the algorithm is more efficient compared with the QuickHull method（the average execution timeconsuming is reduced by 20%) .

Key words: 3Dconvexhull;double extremal point;incremental algorithm

李志,李儒琼. 一种改进的快速三维凸包生成算法及实现[J]. J4, 2011, 33(2): 129-132.

LI Zhi,LI Ruqiong. An Improved Algorithm and Implementation of ThreeDimensional Convex Hulls[J]. J4, 2011, 33(2): 129-132.

编辑推荐

Metrics

阅读次数

全文

HTML			PDF

最新录用	在线预览	正式出版	最新录用	在线预览	正式出版
0	0	0	0	0	80

来源	本网站	其他网站

次数	74	6
比例	92%	8%

摘要

最新录用	在线预览	正式出版

0	0	78

	来源	本网站

	次数	78
	比例	100%

一种改进的快速三维凸包生成算法及实现

An Improved Algorithm and Implementation of ThreeDimensional Convex Hulls

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 0

编辑推荐

Metrics

本文评价