首页 | 本学科首页   官方微博 | 高级检索  
     


Computing generalized higher-order Voronoi diagrams on triangulated surfaces
Authors:Marta Fort,J. Antoni Sellarè  s
Affiliation:Institut d’Informàtica i Aplicacions, Universitat de Girona, Spain
Abstract:We present an algorithm for computing exact shortest paths, and consequently distance functions, from a generalized source (point, segment, polygonal chain or polygonal region) on a possibly non-convex triangulated polyhedral surface. The algorithm is generalized to the case when a set of generalized sites is considered, providing their distance field that implicitly represents the Voronoi diagram of the sites. Next, we present an algorithm to compute a discrete representation of the distance function and the distance field. Then, by using the discrete distance field, we obtain the Voronoi diagram of a set of generalized sites (points, segments, polygonal chains or polygons) and visualize it on the triangulated surface. We also provide algorithms that, by using the discrete distance functions, provide the closest, furthest and k-order Voronoi diagrams and an approximate 1-Center and 1-Median.
Keywords:Computational geometry   Triangulated surface   Shortest path   Voronoi diagram   Hardware graphics
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号