空间数据中几何拓扑关系的一种快速检查算法

减小字体 增大字体 作者:吴宇豪  来源:www.zhonghualunwen.com  发布时间:2009-11-04 02:11:33

  一、简介
  
  近几年来,随着信息技术发展,人们通过不同的方式采集地理数据,用于科学研究和社会应用,数据的爆炸性增长带来的问题开始受到了广泛的关注,如何在海量数据中提取隐藏的复杂的信息,也就成为人们思考的问题。几何拓扑关系检查一直都是空间分析中的重要组成部分之一,并随着原始数据几何级数增长,对其在几何关系检查算法的运算效率方面提出了更快的要求。
  在地理空间数据中,所有元素都可以由三种元素组成:点,线和面。最简单的拓扑关系就是点和点,点和线,线和线。他们都可以通过计算距离和解几何解析方程组来确定。因为面是由线组成的,而线是由点组成的,所以其他较为复杂的拓扑关系都可以转化为点和面的拓扑关系来对待。因此,本文主要讲述如何快速地检测几何拓扑中点和面的关系。
  
  二、现有几何拓扑算法
  
  目前,判断一个点是否在多边形中有两个常用的算法:
  1.射线法。
  2.转角法。(Zhang Hong,Wen Yongning&Liu Aili,2006)。
  (一)射线法
  当射线出入多边形的边的时候,它的出入特性改变了。也就是说,如果点在多边形的内部的话,那么穿越边界的次序是“out-in-…-out”,而当点在多边形外部的话,次序应该是“in-out-…-out”(Zhang Hong,Wen Yongning&Liu Aili,2006)。因为这条射线最终都要穿出多边形,所以当穿越次数为偶数次的时候,该点就可判断在多边形内部。当穿越次数为奇数的时候,该点则在外部。(如图2.1)
  (二)转角法
  假设某平面上有点P和多边形k,k中有顶点P1 P2 P3 P4 P5,以点P为中心,从多边形K任一顶点开始顺次走过多边形所有顶点,如最后回到起点时的转角之和为360度,则该点在多边形内;如转角之和为0度,则该点在多边形外;若P正好在多边形某条边上或与某个顶点重合,则可认为在多边形外。
  如图2.2中,(i=8),那么点就在多边形里面。否则,该点在多边形之外。事实上,这个转角算法和射线算法都有相同的效率。而且,它更精确,因此,转角算法是目前经常采用的检测点和多边形关系的算法(Wu Lixin,Shi Wenzhong,2003)。
  
  三、行扫描快速检测算法
  
  行扫描,顾名思义,就是利用点所在的行,判断其与多边形的边是否相交,再比较交点和点的X轴大小,最后确定,点是否在多边形之内。如果点的X坐标在交点中间,则说明点在多边形内;如果点的X坐标在两两交点之外,则说明点在多边形之外;如果点和交点重合,则点在多边形之上。(图3.1)
  与射线法相似,行扫描算法同样也要建立相应的规则来处理特殊情况,例如:行与多边形的点相交或者行与多边形的边重合。但是,和射线法和转角法不同的是,行扫描只需要计算可能与点所在的行相交的多边形的边即可。因此,在进行行扫描的之前,我们首先根据多边形所有的边的Y值进行排序。利用一定大小的数组来存储多边形边的Y值范围,然后记录边的信息。当确定点的Y值的时候,根据数据记载的相关范围边的信息,找出可能与其相交的多边形的边。
  如图3.2所示,Array是一个类型为String的数组,A和B是多边形中的两条边。Y1和Y2分别代表A中的Y坐标值的起点和终点。同理,Y3和Y4也分别代表B中的最小值和最大值。在进行行扫描之前,将多边形的边的属性按照边的Y坐标范围存进数组里面,例如,在【y1,y3】的范围中只有一条属性为“A”的边,而在【y3,y2】的范围中有两条属性分别为“A”和“B”的边。这样,只需要知道点的Y值,就可以在数组中找到点所在的行可能与多边形中的哪些边相交。
  
  四、实验
  
  在这里,我们尝试用一些现实中的数据来证明三种算法在效率上面的不同。实验中的程序运行的环境是基于Windows xp Sp3的VC.net的环境中。实验数据是来自于某城市一个区的房屋管理局。数据中,点元素一共有5734个,而多边形一共有1115个。
  
  实验运行所需的时间由秒表来计算,误差在【-0.5,0.5】之间。实验结果如下(表4.1):
  从实验数据可知,行扫描的效率约是射线法和转角法的五倍左右。因为在该组数据中,多边形的平均边数为二十五条,而多边形与扫描行的最多交点的平均数为六个。所以,行扫描的效率与数据中多边形的边数,形态有关。当形态越复杂,扫描行与多边形的边交点就越多,所需的时间也会增加。
  
  五、总结
  
  从上面的分析介绍可知,射线法和转角法的时间复杂度是t1=O(n*m)(n是点的数量,m是多边形边的数量),而行扫描快速检测算法的时间复杂度是t2=O(n*k)(k是多边形的边中与扫描行相交的最多相交点数)。因此有:
  由此可见,当原始数据量很大的时候,特别是多边形边数较多,形态较简单的时候,k是比m小很多的,行扫描快速检测能够比现行的算法更加高效地检测出点和面之间的拓扑关系,进而检测更高层次元素之间的几何拓扑关系,例如:线和面,面和面。
  
  参考文献:
  [1]Wu Lixin,Shi Wenzhong(2003).Di li xin xi xi tong yuan li yu suan fa.Beijing:Ke xue chu ban she.
  [2]Zhang Hong,Wen Yongning & Liu Aili(2006).Di li xin xi xi tong suan fa ji chu.Beijing: Ke xue chu ban she.
  
 

Tags:

作者:吴宇豪
  • 好的评价 如果您觉得此文章好,就请您
      0%(0)
  • 差的评价 如果您觉得此文章差,就请您
      0%(0)

文章评论评论内容只代表网友观点,与本站立场无关!

   评论摘要(共 0 条,得分 0 分,平均 0 分) 查看完整评论