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

程 丹; 杨 钦; 蔡 强; 金茂忠

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

1.
北京航空航天大学计算机学院, 北京 100191
2. 北京工商大学计算机学院, 北京 100037
3. 北京航空航天大学计算机学院, 北京 100191

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

详细信息

作者简介:
程丹(1979-),女,辽宁沈阳人,博士生,chengdan@cse.buaa.edu.cn.

中图分类号: TP 391.4
计量
- 文章访问数: 3456
- HTML全文浏览量: 32
- PDF下载量: 1398
- 被引次数: 0
出版历程
- 收稿日期: 2008-12-22
- 网络出版日期: 2009-08-31

Delaunay triangulation and Voronoi diagrams for Riemannian manifolds

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

摘要

摘要: 主要研究黎曼空间中Delaunay三角化和Voronoi图.首先,分析和讨论了黎曼流形的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.
- Riemannian manifolds /
- Delaunay triangulation /
- Voronoi diagrams /
- existence /
- generation algorithm

HTML全文

参考文献(1)

[1] Dirichlet G L. Vber die reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen[J]. Journal of fur die Reine und Angewandte Mathematik, 1850, 40(3):209-227 [2] Voronoi G F. Nouvelles applications des parameters continues la th orie des formes quadratiques[J]. J Reine Angew Math, 1908, 134:198-287 [3] Leibon G, Letscher D. Delaunay triangulations and Voronoi diagrams for Riemannian manifolds Proceedings of the Annual Symposium on Computational Geometry. New York:Association for Computing Machinery,2000:341-349 [4] Leibon G. Random Delaunay triangulations, the Thurston-Andreev theorem, and metric uniformization . California: Department of Mathematics, University of California San Diego, 1999 [5] Dyer R, Zhang H, Moller T. Voronoi-Delaunay duality and Delaunay meshes ACM Symposium on Solid and Physical Modeling. New York: Association for Computing Machinery, 2007:415-420 [6] Onishi K, Takayama N. Construction of Voronoi diagram on the upper half-plane[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 1996, E79-A (4):533-539 [7] Labelle F, Shewchuk J R. Anisotropic Voronoi diagrams and guaranteed-quality anisotropic mesh generation Proceedings of the Annual Symposium on Computational Geometry. New York: ACM, 2003:191-200 [8] 陈维恒,李兴校.黎曼几何引论[M].北京:北京大学出版社, 2002 Cheng Weiheng, Li Xingxiao. An introduction to Riemannian Geometry[M]. Beijing:Peking University Press, 2002 (in Chinese) [9] Borouchaki H, George P L, Hecht F, et al. Delaunay mesh generation governed by metric specifications.Part I.Algorithms[J].Finite Elements in Analysis and Design,1997,25(1):61-83 [10] Jurczyk T, Glut B. Metric 3D surface mesh generation using Delaunay criteria Lecture Notes in Computer Science. Heidelberg, Germany:Springer Verlag,2006:302-309 [11] Borouchaki H, Laug P, George P L. Parametric surface meshing using a combined advancing-front generalized Delaunay approach[J]. International Journal for Numerical Methods in Engineering,2000,49(1):233-259 [12] Du Q, Wang D S. Anisotropic centroidal voronoi tessellations and their applications[J]. SIAM Journal of Scientific Computing,2005,26(3):737-761 [13] Kunze R, Wolter F E, Thomas R. Geodesic Voronoi diagrams on parametric surfaces Proceedings of Computer Graphics International Conference, CGI. Los Alamitos, CA:IEEE,1997:230-237 [14] 关振群,单菊林,顾元宪. 基于黎曼度量的复杂参数曲面有限元网格生成方法[J]. 计算机学报,2006,29(10):1828-1833 Guan Zhenqun,Shan Julin,Gu Yuanxian. Surface mesh generation based on Riemannian metric[J].Chinese Journal of Computers,2006,29(10):1828-1833(in Chinese) [15] Shimada K, Yamada A, Itoh T. Anisotropic triangulation of parametric surfaces via close packing of ellipsoids[J]. Int-l J Computational Geometry and Applications,2000,10(4):417-440 [16] Wu Mingha, Mo Guolang, Yu Yiye. Numerical solution of geodesic through two given points on a simple surface[J]. Journal of Zhejiang University: Science, 2006, 7(S2):187-192 [17] Grimm C M,Hughes J F.Modeling surfaces of arbitrary topology using manifolds Proceedings of the ACM SIGGRAPH Conference on Computer Graphics. New York:ACM,1995:359-368 [18] Grimm C M, Zorin D. Surface modeling and parameterization with manifolds Siggraph 2006 Course Notes. New York:ACM,2006:1-81

施引文献

资源附件(0)

访问统计