北京航空航天大学学报 ›› 2009, Vol. 35 ›› Issue (8): 962-967.

• 论文 • 上一篇    下一篇

黎曼流形的Delaunay三角化和Voronoi图

程 丹1, 杨 钦2, 蔡 强2, 金茂忠3   

  1. 1. 北京航空航天大学 计算机学院, 北京 100191;
    2. 北京工商大学 计算机学院, 北京 100037;
    3. 北京航空航天大学 计算机学院, 北京 100191
  • 收稿日期:2008-12-22 出版日期:2009-08-31 发布日期:2010-09-16
  • 作者简介:程 丹(1979-),女,辽宁沈阳人,博士生,chengdan@cse.buaa.edu.cn.
  • 基金资助:

    北京市自然科学基金资助项目(4062010)

Delaunay triangulation and Voronoi diagrams for Riemannian manifolds

Cheng Dan1, Yang Qin2, Cai Qiang2, Jin Maozhong3   

  1. 1. School of Computer Science and Technology, Beijing University of Aeronautics and Astronautics, Beijing 100191, China;
    2. College of Computer Science and Engineering, Beijing Technology & Business University, Beijing 100037, China;
    3. School of Computer Science and Technology, Beijing University of Aeronautics and Astronautics, Beijing 100191, China
  • Received:2008-12-22 Online:2009-08-31 Published:2010-09-16

摘要: 主要研究黎曼空间中Delaunay三角化和Voronoi图.首先,分析和讨论了黎曼流形的Delaunay三角化和Voronoi图的存在性和生成算法.然后,在分析已有研究成果基础上,给出了黎曼流形Delaunay三角化和Voronoi图的一些性质和证明,并提出了采用黎曼流形描述问题的必要性和使用坐标卡研究黎曼流形的优势和意义.最后,以二维流形为例,介绍了将模型初始数据解释为黎曼流形的算法,包括建立坐标卡,定义流形函数等.在黎曼流形定义的基础上,详细描述了基于坐标卡生成模型的Delaunay三角化和Voronoi图的算法,并给出具体实例.

Abstract: Delaunay triangulation and Voronoi diagrams in Riemannian space were studied. Firstly, the existence and generation algorithm of Delaunay triangulation and Voronoi diagrams were discussed. Then on the basis of analysing the existed research achievements, some properties of Delaunay triangulation and Voronoi diagrams for Riemannian were given and proved. The necessities of describing object by Riemannian manifolds and advantages of researching Riemannian manifolds by charts were presented. Finally, taking 2-manifold as an example, the algorithm of getting Riemannian manifolds according to initial data of models was described, which included creating charts, defining functions of manifolds, and so on. The algorithm of creating Delaunay triangulation and Voronoi diagrams of models based on charts was presented, and some examples were provided.

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发