首页> 外文OA文献 >An algorithm for the generation of Voronoi diagrams on the sphere based on QTM
【2h】

An algorithm for the generation of Voronoi diagrams on the sphere based on QTM

机译:基于QTM的球面Voronoi图生成算法。

摘要

In order to efficiently store and analyze spatial data on a global scale, the digital expression of Earth data in a data model must be global, continuous, and conjugate, i.e., a spherical dynamic data model is needed. The Voronoi data structure is the only published attempt (Wright and Goodchild, 1997) and the only possible solution currently available (Li et al., 1999) for a dynamic GIS. However, the complexity of the Voronoi algorithm for line sets and area sets in vector mode limits its application in a dynamic GIS. So far, there is no raster-based Voronoi algorithm for objects (including points, arcs, and regions) on a spherical surface. To overcome this serious deficiency, an algorithm for generating a spherical Voronoi diagram is presented, based on the O-QTM (Octahedral Quaternary Triangular Mesh). The principle of the dilation operation in mathematical morphology is extended to the spherical surface. A method is developed for a spherical distance transformation based on the QTM. A detailed algorithm is also presented. This algorithm can handle points, arcs, and area features on a spherical surface. Tests have shown that the computational time consumption of this algorithm with points, arcs, and areas is equal and proportionate to the levels of the spherical surface tessellation; and the difference (distortion) between the great circle distance and the QTM cells distance is slightly related to spherical distance (not as the raster dilation on a planar surface), and is mainly related to the locations of the generating points.
机译:为了有效地在全球范围内存储和分析空间数据,数据模型中地球数据的数字表达必须是全局,连续和共轭的,即需要一个球形动态数据模型。 Voronoi数据结构是唯一公开发表的尝试(Wright和Goodchild,1997年),也是当前针对动态GIS可用的唯一可行解决方案(Li等,1999年)。但是,矢量模式下线集和面集的Voronoi算法的复杂性限制了它在动态GIS中的应用。到目前为止,还没有针对球面上的对象(包括点,弧和区域)的基于栅格的Voronoi算法。为了克服这一严重缺陷,提出了一种基于O-QTM(八面体第四纪三角网格)的生成球形Voronoi图的算法。数学形态学中的扩张运算原理被扩展到球面。开发了一种基于QTM的球距变换方法。还提供了详细的算法。该算法可以处理球面上的点,弧和面积特征。测试表明,该算法在点,弧和面积上的计算时间消耗是相等的,并且与球面细分的水平成比例;大圆距离与QTM像元距离之间的差异(失真)与球面距离(而不是在平面上的栅格膨胀)略相关,而主要与生成点的位置有关。

著录项

  • 作者

    Chen J; Zhao X; Li Z;

  • 作者单位
  • 年度 2003
  • 总页数
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类

相似文献

  • 外文文献
  • 中文文献
  • 专利

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号