An Analysis and Investigation of Algorithms for Identifying Convexity-Concavity of a Simple Polygon

doi:10.6046/gtzyyg.2011.03.05

Download: PDF(772 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Algorithms for identifying convexity-concavity of a simple polygon has a very important application in many fields. The authors analyzed the present popular algorithms for identifying convexity-concavity of a simple polygon such as angling method, left-right-point method, vector-area method, vector-product method, raying method, slopping method and extremity-vertices-order method. A detailed derivation of these algorithms has revealed that these algorithms can all use the formula b=p*m as the expression, and are equivalent to each other in nature; nevertheless, the pole-order method still have some problems to be further studied. Based on an analysis of the computation, the authors hold that theoretically the vector-product method, the slopping method and the raying method could be used effectively in programming.

Keywords Gegraphic information system Dajinhu geopark World geopark

TP 750

Issue Date: 07 September 2011

	Service

	E-mail this article
	E-mail Alert
	RSS
	Articles by authors

Cite this article:

SONG Xiao-mei, CHENG Chang-xiu, ZHOU Cheng-hu. An Analysis and Investigation of Algorithms for Identifying Convexity-Concavity of a Simple Polygon[J]. REMOTE SENSING FOR LAND & RESOURCES,2011, 23(3): 25-31.

URL:

https://www.gtzyyg.com/EN/10.6046/gtzyyg.2011.03.05 OR https://www.gtzyyg.com/EN/Y2011/V23/I3/25

[1] 周培德.确定任意多边形凸凹顶点的算法
[J].软件学报,1995,6(5):276-279.

[2] 许如初,张智平.确定任意多边形顶点凸凹性的快速算法
[J].华中理工大学学报,1997,25(1):103-104.

[3] 万书亭,韩庆瑶.平面多边形凹凸性的顶角判别法
[J].水利电力机械,2000(4):6-8.

[4] 周培德.计算几何——算法设计与分析
[M].2版.北京:清华大学出版社,2006:135-136.

[5] Feito F,Torres J C,Ureña A.Orientation,Simplicity,and Inclusion Test for Planar Polygons
[J].Computers & Graphics,1995,19(4):595-600.

[6] 金文华,唐卫清,唐荣锡.简单多边形顶点凸凹性的快速确定算法
[J].工程图学学报,1998(1):66-70.

[7] 董洪伟,周儒荣.任意平面多边形顶点凸凹性的快速新算法
[J].计算机工程与设计,1999,20(3):56-58.

[8] 刘润涛.任意多边形顶点凸、凹性判别的简捷算法
[J].软件学报,2002,13(7):1309-1312.

[9] 马小虎,潘志庚,石教英.确定多边形凸凹顶点的快速算法及其应用
[J].计算机工程与设计,1998,19(3):45-49.

[10] 陈炳发,钱志峰,廖文和.简单多边形凸凹性自识别算法
[J].计算机辅助设计与图形学学报,2002,14(3):214-217.

[11] 吴春福,陆国栋,张树有.基于拓扑映射的多边形顶点凸凹判别算法
[J].计算机辅助设计与图形学学报,2002,14(9):810-814.

[12] 刘晓平,吴磊.简单多边形方向及顶点凹凸性的快速判定
[J].工程图学学报,2005(4):124-129.

[13] 庞明勇,卢章平.基于边向量斜率比较的简单多边形顶点凸凹性快速判别算法
[J].工程图学学报,2004,25(3):71-77.

[14] 赵军,张桂梅,曲仕茹.利用极点顺序的多边形顶点凹凸性判别算法
[J].工程图学学报,2007,28(1):55-59.