简单多边形顶点凹凸性判断算法综述

doi:10.6046/gtzyyg.2011.03.05

摘要
参考文献
相关文章
Metrics

全文: PDF(772 KB)

HTML
输出: BibTeX | EndNote (RIS)

摘要

简单多边形顶点凹凸性判断算法种类繁多,在模式识别及计算机图形学等领域具有重要应用。为了研究不同种类算法的内在联系与区别,以便在实际应用中根据情况选择合适的算法,分析了目前较为流行的角度法、左右点法、矢量面积法、向量积法、射线法、斜率法和极点顺序法等算法。经过详细的推导论证发现,这些算法都可以使用公式b=p*m来表示,且各种算法在本质上是等价的。但通过对算法计算量的对比,推荐在程序设计中使用向量积法、射线法和斜率法。

	服务

	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章

关键词 ：地理信息系统, 大金湖国家地质公园, 世界地质公园

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.

Key words： Gegraphic information system Dajinhu geopark World geopark

收稿日期: 2010-11-29 出版日期: 2011-09-07

TP 750

基金资助:

国家863项目"地理空间数据库管理系统总体设计"项目(编号: 2007AA120401)、科技支撑计划"区域空间信息资源共享与服务关键技术研发与集成"项目(编号: 2007BAH16B03)及所创新项目"空间查询代价评估模型"(编号: O9V90220ZZ)。

通讯作者: 程昌秀(1973-),博士,副研究员,主要从事空间数据库等技术的研究。E-mail: chengcx@lreis.ac.cn

作者简介: 宋晓眉(1983-),男,博士研究生,主要从事空间聚类、空间数据库查询优化研究。

引用本文:

宋晓眉, 程昌秀, 周成虎. 简单多边形顶点凹凸性判断算法综述[J]. 国土资源遥感, 2011, 23(3): 25-31.
SONG Xiao-mei, CHENG Chang-xiu, ZHOU Cheng-hu. An Analysis and Investigation of Algorithms for Identifying Convexity-Concavity of a Simple Polygon. REMOTE SENSING FOR LAND & RESOURCES, 2011, 23(3): 25-31.

链接本文:

https://www.gtzyyg.com/CN/10.6046/gtzyyg.2011.03.05 或 https://www.gtzyyg.com/CN/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.

[1]	赵龙贤, 代晶晶, 赵元艺, 姜琪, 刘婷玥, 傅明海. 基于RS和GIS技术的西藏多龙矿集区矿山选址研究[J]. 国土资源遥感, 2021, 33(2): 182-191.
[2]	陈炫炽, 陈蓉, 吴愈锋, 王跃跃. 基于RS和GIS的都匀茶树种植地质背景调查[J]. 国土资源遥感, 2020, 32(1): 224-231.
[3]	李亚平, 卢小平, 张航, 路泽忠, 王舜瑶. 基于GIS和RUSLE的淮河流域土壤侵蚀研究——以信阳市商城县为例[J]. 国土资源遥感, 2019, 31(4): 243-249.
[4]	董茜, 李江风, 方世明, 方昆升. 基于GIS的地质公园保护区划分——以湖北神农架世界地质公园为例[J]. 国土资源遥感, 2016, 28(3): 154-159.
[5]	邵秋芳, 彭培好, 黄洁, 刘智, 孙小飞, 邵怀勇. 长江上游安宁河流域生态环境脆弱性遥感监测[J]. 国土资源遥感, 2016, 28(2): 175-181.
[6]	邢宇. 青藏高原32年湿地对气候变化的空间响应[J]. 国土资源遥感, 2015, 27(3): 99-107.
[7]	陈琪, 赵志芳, 何彬仙, 王頔, 习靖. 基于RS和GIS技术的矿山环境恢复与治理规划——以云南省元阳某金矿矿集区为例[J]. 国土资源遥感, 2015, 27(3): 167-171.
[8]	胡莹瑾, 崔海明. 基于RS和GIS的农作物估产方法研究进展[J]. 国土资源遥感, 2014, 26(4): 1-7.
[9]	李晓燕, 姜广辉, 胡磊, 李瑜. 基于GIS与虚拟现实的土地利用总体规划仿真展示平台设计[J]. 国土资源遥感, 2014, 26(4): 195-200.
[10]	张龙, 汪新庆. 基于数据字典的空间数据库通用建库技术[J]. 国土资源遥感, 2014, 26(1): 173-178.
[11]	苗李莉, 蒋卫国, 王世东, 朱琳. 基于遥感和GIS的北京湿地生态服务功能评价与分区[J]. 国土资源遥感, 2013, 25(3): 102-108.
[12]	李红超, 孙永军, 李晓琴, 毕二平. 黄河中游地区荒漠化变化特征及影响因素[J]. 国土资源遥感, 2013, 25(2): 143-148.
[13]	秦润君, 吴虹, 郭琪, 赵胜利. 基于遥感和GIS技术的漓江自然地貌破坏现状调查[J]. 国土资源遥感, 2013, 25(1): 160-164.
[14]	杨奇勇, 马祖陆, 蒋忠诚, 罗为群, 谢运球. 峰丛洼地遥感图像山体阴影缺失的克里格修复[J]. 国土资源遥感, 2012, 24(4): 112-116.
[15]	程洋, 陈建平, 皇甫江云, 童立强. 基于RS和GIS的岩溶石漠化恶化趋势定量预测——以广西都安瑶族自治县典型岩溶石漠化地区为例[J]. 国土资源遥感, 2012, 24(3): 135-139.

Viewed

Full text

Abstract

Cited

Shared

Discussed