基于顶点可见性的凹多边形快速凸分解算法  

A FAST POLYGON CONVEX DECOMPOSITION ALGORITHM BASED ON POINT VISIBILITY

作　　者：金文华[1] 饶上荣[1] 唐卫清[1] 刘慎权[1] 

机构地区：[1]中国科学院计算技术研究所CAD开放研究实验室,北京100080

出　　处：《计算机研究与发展》1999年第12期1455-1460,共6页Journal of Computer Research and Development

基　　金：国家自然科学基金

摘　　要：凹多边形的凸分解问题是计算几何的基本问题之一，在许多领域均有应用．现有算法大多为全局剖分算法，而局部剖分算法研究的很少．全局方法由于耗时太多，而不能满足所有工程应用的需要．目前局部剖分算法中最经典的是Ｒｏｇｅｒｓ算法，但由于其存在许多缺陷而在实际应用中受到限制．文中在多边形顶点可见性基础上，提出了新的局部剖分方法．利用凹点的局部几何特性，通过引入权函数从凹点的可见点串中选取适当的点引剖分线，或者利用凹点夹角平分线与某两可见顶点所在边的交点引剖分线进行多边形分解．文中算法已应用于工厂设计软件ＰＤＳＯＦＴＰｉｐｉｎｇ 中，实践证明效果很好．Polygon convex decomposition is one of the fundamental problems in computational geometry. It is used in many fields. Most of the algorithms now available are global searching ones. Local searching algorithms are rarely studied. The global searching algorithms waste so much time that they cannot meet the need of all the engineering problems. Presently the most classical local searching method is Rogers algorithm. But as it has many limitations, it is restricted in some actual use. In this paper, a new local searching algorithm is proposed based on the polygon point visibility. The local geometrical property is fully used in the algorithm. The cutting\|line is obtained from the concave point to the visible point which is carefully searched from the visible point list of this concave point by using weight function. Alternatively, the cutting\|line is found from concave point to the intersection point which is located on the visible point line and the bisector of the concave angle associated with the concave point. The presented algorithm has been applied in the plant design system of PDSOFT Piping, and the results obtained are remarkable.

关 键 词：顶点可见性 计算几何 算法 凹多边形 凸分解 

分 类 号：O24[理学—计算数学] TP391.72[理学—数学]