基于局部可见点进行的凹多边形凸分解算法

A polygon convex decomposition algorithm based on partial visible point

在参考基于顶点可见性的凹多边形凸分解算法的基础上,提出了改进的方法.该方法先搜索当前凹点,并由该凹角所在边引射线,将多边形所在平面分为A、B、C、D四个区域,并求取当前凹点在区域A内的可见点串;然后,以区域A中是否有可见点为依据,利用凹点的局部几何特性,通过引入权函数从凹点的可见点串中选取适当的点引剖分线,或者利用凹点夹角平分线与多边形在区域A中的线段的交点引剖分线进行多边形分解.本算法旨在通过减少所要求取的可见点数目提高算法效率.

An improved algorithm is proposed based on the polygon convex decomposition algorithm based on point visibility. Firstly, it finds the current concave point and divides the flat into four parts: A, B, C and D by the radiation which is located on this concave angle, and then searches the visible points in the field A. Secondly, 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 if there are visible points in the field A, otherwise, the cutting-line is found from concave point to the intersection point which is located on the section of the polygon which is in the field A and the bisector of the concave angle associated with the concave point. The algorithm raises efficiency by decreasing the quantity of visible points which are to be obtained.