邻近凹点角平分线的多边形顶点快速凸分算法研究及应用

Research and application on algorithm for decomposing a concave polygon into convex polygons of adjacent angle bisector of concave point and vertex of polygon

在分析和归纳已有凸分算法的基础上,提出邻近凹点角平分线的多边形顶点快速凸分算法。该算法不增加新顶点,且剖分得到的凸多边形数量少,大小、形状等质量较好。算法应用在方格网土方计算中,能快速找出填挖分界点并划定填挖方区域。该算法与凸分成三角形的土方计算精度相当,但其抗粗差能力强,计算速度快;与增加顶点的凸分方式比较,土方计算精度和速度均优于后者。

The algorithm for decomposing a concave polygon into convex polygons is widely used in processing computer graphics geometry. A new fast algorithm of convex decomposition is proposed after the existing convex decomposition al- gorithms analyzed and induced. The fast algorithm of convex decomposition is based on adjacent angle bisector of con- cave point and vertex of polygon. The algorithm does not increase new vertex, and the number of convex polygons de- composed is small, size and shape is excellent. The algorithm is used in earthwork calculation of grid. The algorithm can quickly find out demarcation points of fill and dig, confirm the areas of fill and dig. Compared with other convex decom- position algorithm, the conclusions are as follows ： With the decomposition way of dividing into triangles, the precision of earthwork calculation equivalents to the triangulate, but the ability of resistance gross error is stronger, computing speed is faster than the latter. With the decomposition way of increasing vertex, the precision of earthwork calculation and the computing speed is better than the latter.