空间点集卷包裹算法的优化实现  

An Optimized Implementation of the Gift-Wrapping Algorithm for Three-Dimensional Convex Hull

作　　者：吴克勤[1] 杨冠杰[1] 

机构地区：[1]中国海洋大学计算机科学系,青岛266003

出　　处：《青岛海洋大学学报（自然科学版）》2003年第4期627-633,共7页Journal of Ocean University of Qingdao

基　　金：山东省自然科学基金项目 (Y2 0 0 2 G12 )资助

摘　　要：凸包计算是计算几何研究中的基本问题之一 ,在许多领域均有应用。本文对求解空间点集凸包的卷包裹算法的实现问题进行了讨论。提出了 2点优化措施 ,并解决了实现中可能出现的共面点及由此带来的退化问题。Convex hull computation is one of the fundamental problems in computational geometry , and is of wide application in many fields. In this paper the efficient implementation of the gift-wrapping method for computing the convex hull of 3D point sets is discussed. Two optimization methods to improve the efficiency are presented, and also proposed is a solution to the coplanar points and derived degeneracy problems, which might occur during the algorithm running.

关 键 词：计算几何 空间点集 卷包裹算法 凸包计算 优化 几何退化 计算机图形学 科学计算可视化 

分 类 号：O18[理学—数学] TP391.41[理学—基础数学]