互联网 qkzz.net
全刊杂志网:首页 > 女性 > 文章正文
刊社推荐

快速多边形区域三角化算法与实现毕 林 王李管 陈建宏 冯兴隆


  收稿日期:2007-11-26;修回日期:2008-03-04

  基金项目:国家自然科学基金资助项目(50774092)

  作者简介:毕林(1975-),男,博士研究生,主要研究方向为GIS、数字矿山软件([email protected]);王李管(1964-),男,博导,主要研究方向为数字矿山;陈建宏(1963-),男,博导,主要研究方向为矿山GIS;冯兴隆(1980-),男,博士研究生,主要研究方向为数字矿山*

  (1.中南大学 资源与安全工程学院,长沙 410083; 2.长沙迪迈信息科技有限公司, 长沙 410083)

  摘 要:多边形区域三角化的基本思想是:首先将简单多边形分解为多个单调多边形,然后对每个单调多边形进行三角化。快速多边形区域三角化算法先由多边形顶点的位置特征分为不同的类型,并沿指定方向对顶点进行排序,然后顺序取出各顶点,根据顶点类型,确定准单调多边形的产生、增长或结束,最后对所产生的多个单调多边形进行三角化。该算法充分利用多边形的顶点、边的拓扑关系,计算量少、实现简单,适用于带有洞、岛的任意简单多边形,速度较快。

  关键词:多边形;单调多边形;拓扑关系;线性时间复杂度;三角化

  中图分类号:TP391. 72

  文献标志码:A

  文章编号:1001-3695(2008)10-3030-04

  Fast triangulation algorithm for polygon regions and implementation

  BI Lin1,2, WANG Li-guan1,2, CHEN Jian-hong1, FENG Xing-long1

  (1.School of Resources & Safety Engineering,Central South University,Changsha 410083,China; 2.Digital Mine Co.Ltd,Changsha 410083,China)

  Abstract:The basic idea of triangulation for simple triangle was described as follows: the polygon was subdivided into mono-tonous polygons and then triangulated. The algorithm classified all the vertexes by its location characteristics, and sorted them along the appointed axis, and then selected the vertexes orderly to decide the creation, expansion or formation of a monotonous polygon by its type, at last triangulated the formative monotonous polygon. In the algorithm, the topology of the vertexes and edges made full use of so as to reduce calculation task, simplify implementation and made it suitable for any simple triangle with holes and islands , speediness and nearly linear time complexity.

......
很抱歉,暂无全文,若需要阅读全文或喜欢本刊物请联系《计算机应用研究》杂志社购买。
欢迎作者提供全文,请点击编辑
分享:
 

了解更多资讯,请关注“木兰百花园”
分享:
 
精彩图文


关键字
支持中国杂志产业发展,请购买、订阅纸质杂志,欢迎杂志社提供过刊、样刊及电子版。
关于我们 | 网站声明 | 刊社管理 | 网站地图 | 联系方式 | 中图分类法 | RSS 2.0订阅 | IP查询
全刊杂志赏析网 2017