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

凹多边形的凸分解问题是计算几何的基本问题之一，在许多领域均有应用。现有算法大多为全局部分算法，而局部分自救研究的很少。全局方法由于耗时太多，而不能满足所有工程应用的需要。目前局部剖分算法中最经典的是Ｒｏｇｅｒｓ算法，但由于其存在许多缺陷而在实际应用中受到限制。文中在多边形顶点可见性基础上，提出了新的局部剖分方法。凹点的局部几何特性，通过引入权函数从凹点的可见点串中选取适当的点引剖分线，或者利用凹点

A FAST POLYGON CONVEX DECOMPOSITION ALGORITHM BASED ON POINT VISIBILITY

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.