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

何立恒; 鲍其胜; 王志杰

doi:10.3969/j.issn.1000-2006.2013.05.032

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

何立恒,，鲍其胜，王志杰

南京林业大学学报（自然科学版） ›› 2013, Vol. 37 ›› Issue (05) : 165-168.

PDF(1347794 KB)

国家林草科技领军期刊
中国精品科技期刊
中国高校百佳科技期刊
江苏省新闻出版政府奖期刊奖
RCCSE林学权威期刊（A+）
CSCD核心期刊
Scopus数据库收录期刊
中文核心期刊
SCD核心期刊

作者加群：102861116

微信公众号：南京林业大学学报

高级检索

PDF(1347794 KB)

南京林业大学学报（自然科学版） ›› 2013, Vol. 37 ›› Issue (05) : 165-168. DOI: 10.3969/j.issn.1000-2006.2013.05.032

研究简报

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

何立恒¹,²，鲍其胜³，王志杰²

作者信息 +

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

HE Liheng¹,²,BAO Qisheng³,WANG Zhijie²

Author information +

文章历史 +

摘要

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

Abstract

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 algorithms analyzed and induced. The fast algorithm of convex decomposition is based on adjacent angle bisector of concave point and vertex of polygon. The algorithm does not increase new vertex, and the number of convex polygons decomposed 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 decomposition 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.

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用

何立恒,，鲍其胜，王志杰. 邻近凹点角平分线的多边形顶点快速凸分算法研究及应用[J]. 南京林业大学学报（自然科学版）. 2013, 37(05): 165-168 https://doi.org/10.3969/j.issn.1000-2006.2013.05.032

HE Liheng,,BAO Qisheng,WANG Zhijie. Research and application on algorithm for decomposing a concave polygon into convex polygons of adjacent angle bisector of concave point and vertex of polygon[J]. JOURNAL OF NANJING FORESTRY UNIVERSITY. 2013, 37(05): 165-168 https://doi.org/10.3969/j.issn.1000-2006.2013.05.032

中图分类号： TP39172

参考文献

［1］柳庆武,吴冲龙,翁正平.凹多边形的矢量—三角形法自动识别与剖分[J].计算机应用,2003,23(2):77-79. Liu Q W, Wu C L, Weng Z P. Vectortriangle for automatic recognition and triangulation of concave polygon[J]. Computer Application, 2003, 23(2)：77-79.
［2］朱传敏,唐军,许田贵.凹多边形凸分解算法在快速原型中的应用[J].现代制造工程,2010(2):53-56. Zhu C M, Tang J, Xu T G. The application of concave polygon convex decomposition algorithm to rapid prototyping[J]. Modern Manufacturing Engineering, 2010(2)：53-56.
［3］巩丹超,戴晨光,张永生.三维模型重建中的凹多边形三角剖分[J].解放军测绘学院学报,1999,16(3):194-196. Gong D T, Dai C G, Zhang Y S. Triangulation of concave polygon used in reconstruction of 3D models[J].Journal of the PLA Institute of Surveying and Mapping,1999,16(3):194-196.
［4］卞宏友,刘伟军,王天然,等.面向快速制造扫描分区的凹多边形凸分解算法[J].计算机应用,2005，25(9):2143-2145. Bian H Y, Liu W J, Wang T R, et al. Concave polygon convex decomposition algorithm for rapid prototyping subarea scanning[J]. Computer Applications, 2005, 25(9)：2143-2145.
［5］Schachter B. Decomposition of polygons into convex sets[J]. IEEE Trans on Computers, 1978,（27911)：1078-1082.
［6］Chazelle B, Dobkin D. Optimal convex decompositions[C]//Toussaint G T. Computational Geometry, Amsterdam：North-Holland, 1985.
［7］Keil J M. Decomposing a polygon into simple components[J]. SIAM J COMPUT, 1985, 14(4)：799-817.
［8］肖忠晖,卢振荣,张谦.简单多边形凸单元剖分的编码算法[J].计算机学报,1996,19 (6) ：477-481. Xiao Z H, Lu Z R, Zhang Q. Coding algorithm for decomposing a simple polygon into convex parts[J]. Chinese Journal of Computers, 1996, 19 (6)：477-481.
［9］王钲旋,李文辉,庞云阶.一个加权剖分简单多边形为凸多边形的算法[J].计算机学报, 1998, 21(3)：229-233. Wang Z X, Li W H, Pang Y J. A weighing algorithm for decomposing a simple polygon into convex polygons[J]. Chinese Journal of Computers, 1998, 2l(3)：229-233.
［10]金文华,饶上荣,唐卫清,等.基于顶点可见性的凹多边形快速凸分解算法[J].计算机研究与发展, 1999, 36(12)：1455-1460. Jin W H, Rao S R, Tang W Q, et al. A fast polygon convex decomposition algorithm based on point visibility[J]. Journal of Computer Research & Development, 1999, 36(12)：1455-1460.
［11]贺怀清,杨鹏.一种凹多边形凸分解的全局剖分算法[J].中国民航大学学报,2011,29(3):52-55. He H Q, Yang P. Global subdivision algorithm on convex decomposition of concave polygon[J]. Journal of Civil Aviation University of China, 2011, 29(3)：52-55.
［12]周雅洁,刘英,张晶伟.基于局部可见点进行的凹多边形凸分解算法[J].武汉大学学报：工学版, 2004, 37(2)：85-87. Zhou Y J, Liu Y, Zhang J W. A polygon convex decomposition algorithm based on partial visible point [J]. Engineering Journal of Wuhan University, 2004, 37(2)：85-87.
［13]董金辉,朱永芬.基于简单多边形相邻凹点关系的凸剖分算法[J].黄冈师范学院学报, 2007, 27(3)：7-10, 21. Dong J H, Zhu Y F. A convex decomposition algorithm of simple polygon based on its adjacent concave point connection [J].Journal of Huanggnag Normal University, 2007, 27(3)：7-10, 21.
［14]程琳,孟志军,梁明,等.基于Mapx组件的凹多边形快速分解算法的实现[J].农机化研究, 2010(7)：26-29. Chen L, Meng Z J, Liang M, et al. Concave polygon fast decomposition algorithm based on Mapx components[J]. Journal of Agricultural Mechanization Research, 2010(7)：26-29.
［15]庞明勇,卢章平.基于边向量斜率比较的简单多边形顶点凸凹性快速判别算法 [J].工程图学学报, 2004(3)：71-77. Pang M Y, Lu Z P. An algorithm for rapidly identifying convexoconcave vertices of simple polygon based on comparing the slopes of two adjacent edge vectors[J]. Journal of Engineering Graphics, 2004(3)：71-77.
［16]赵军,张桂梅,曲仕茹. 利用极点顺序的多边形顶点凹凸性判别算法[J].工程图学学报,2007(1):55-59. Zhao J, Zhang G M, Qu S R. Orientation and convexity-concavity identification for polygons using extremity vertices sequence[J]. Journal of Engineering Graphics, 2007(1)：55-59.
［17]汪学明.多边形顶点凸凹性识别算法的研究与实现[J ].计算机应用,2005(8):1786-1788. Wang X M. Study and implement of determining convexconcave features for vertices of polygon[J]. Computer Applications, 2005(8)：1786-1788.
［18]刘润涛.任意多边形顶点凸、凹性判别的简捷算法[J].软件学报,2002,13(7):1309-1311. Liu R T. A simple and fast algorithm for detecting the convexity and concavity of vertices for an arbitrary polygon[J].Journal of Software, 2002, 13(7)：1309-1311.
［19]金文华,唐卫清,唐荣锡.简单多边形顶点凸凹性的快速确定算法[J].工程图学学报,1998(1):66-70. Jin W H, Tang W Q, Tang R X. A fast algorithm for determining the convexityconcavity of vertices of simple polygon[J]. Journal of Engineering Graphics, 1998(1)：66 -70.
［20]吴春福,陆国栋,张树有.基于拓扑映射的多边形顶点凸凹判别算法[J].计算机辅助设计与图形学学报,2002,14(9):810 -814. Wu C F, Lu G D, Zhang S Y. Determining convexoconcave vertices of polygon by topological mapping[J]. Journal of ComputerAided Design & Computer Graphics, 2002, 14(9)：810-814.

基金

收稿日期：2012-10-28修回日期：2012-12-20 基金项目：江苏高校优势学科建设工程资助项目（PAPD）第一作者：何立恒，副教授，博士。 Email： hlh8046@njfu.com.cn。引文格式：何立恒，鲍其胜，王志杰. 邻近凹点角平分线的多边形顶点快速凸分算法研究及应用[J]. 南京林业大学学报：自然科学版，2013，37（5）：165-168.