计算机工程 ›› 2013, Vol. 39 ›› Issue (1): 41-44.doi: 10.3969/j.issn.1000-3428.2013.01.008

• 软件技术与数据库 • 上一篇    下一篇

一种改进的多边形数据内点自动生成算法

卢 浩 1,2,钟耳顺 1,3,王天宝 1,2,王少华 1,2   

  1. (1. 中国科学院地理科学与资源研究所,北京 100101;2. 中国科学院研究生院,北京 100039; 3. 北京超图软件股份有限公司,北京 100015)
  • 收稿日期:2012-01-26 修回日期:2012-03-15 出版日期:2013-01-15 发布日期:2013-01-13
  • 作者简介:卢 浩(1984-),男,博士研究生,主研方向:地理信息系统,计算几何;钟耳顺,研究员、博士生导师;王天宝、王少华,博士研究生

An Improved Polygon Data Interior Point Automatic Generation Algorithm

LU Hao 1,2, ZHONG Er-shun 1,3, WANG Tian-bao 1,2, WANG Shao-hua 1,2   

  1. (1. Institute of Geographic Sciences and Natural Resources Research, Chinese Academy of Sciences, Beijing 100101, China; 2. Graduate University of Chinese Academy of Sciences, Beijing 100039, China; 3. SuperMap Software Co., Ltd., Beijing 100015, China)
  • Received:2012-01-26 Revised:2012-03-15 Online:2013-01-15 Published:2013-01-13

摘要: 基于最小外切矩形(MBR)的多边形内点生成算法在奇异情况下容易失效。针对该问题,引入矢量数据的不确定性区间,提出一种改进的多边形数据内点自动生成算法。采用不确定性区间和相交区间的处理方法对奇异情况进行统一修正,避免MBR算法对于切割线与节点相交情况的过多异常处理和分支结构。通过对比实验验证了该算法的健壮性和高效性。

关键词: 地理信息系统, 多边形, 内点生成, 不确定性, 相交区间, 健壮性

Abstract: The polygon data interior point automatic generation algorithm based on Minimum Bounding Rectangle(MBR) easily leads to failure in the singular case. In order to solve the problem, this paper proposes an improved polygon data interior point automatic generation algorithm which introduces the vector data uncertainty interval concept. The improved algorithm uses the approach of uncertainty interval and intersection interval to fix the singular case, which avoids too much exception handling and branch structure of the MBR algorithm when the cutting line intersects with the node. Comparative experimental results prove the robustness and efficiency of the improved algorithm.

Key words: Geographic Information System(GIS), polygon, interior point generation, uncertainty, intersection interval, robustness

中图分类号: