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

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

作　　者：何立恒[1,2] 鲍其胜[3] 王志杰[2] 

机构地区：[1]南京大学地理与海洋科学学院,江苏南京210093 [2]南京林业大学土木工程学院,江苏南京210037 [3]南京市测绘勘察研究院有限公司,江苏南京210019

出　　处：《南京林业大学学报（自然科学版）》2013年第5期165-168,共4页Journal of Nanjing Forestry University：Natural Sciences Edition

基　　金：江苏高校优势学科建设工程资助项目(PAPD)

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

关 键 词：凹多边形 角平分线 凸分算法 土方计算 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]