我们的网站为什么显示成这样?

可能因为您的浏览器不支持样式,您可以更新您的浏览器到最新版本,以获取对此功能的支持,访问下面的网站,获取关于浏览器的信息:

|Table of Contents|

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

《南京林业大学学报(自然科学版)》[ISSN:1000-2006/CN:32-1161/S]

Issue:
2013年05期
Page:
165-168
Column:
研究简报
publishdate:
2013-09-30

Article Info:/Info

Title:
Research and application on algorithm for decomposing a concave polygon into convex polygons of adjacent angle bisector of concave point and vertex of polygon
Article ID:
1000-2006(2013)05-0165-04
Author(s):
HE Liheng12BAO Qisheng3WANG Zhijie2
1. School of Geographic and Oceangraphic Sciences, Nanjing University, Nanjing 210093, China;
2. School of Civil Engineering, Nanjing Forestry University, Nanjing 210037, China;
3. Nanjing Research Institute of Surveying, Mapping & Geotech
Keywords:
concave polygon angle bisector convex decomposition algorithm earthwork calculation
Classification number :
TP39172
DOI:
10.3969/j.issn.1000-2006.2013.05.032
Document Code:
A
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.

References

[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.

Last Update: 2013-09-30