Shortest Path Queries in a Simple Polygon for 3D Virtual Museum
Shortest Path Queries in a Simple Polygon for 3D Virtual Museum
复制标题
DOI：
10.1007/978-3-540-74472-6_9
复制
发表时间：
2007-08
期刊：
影响因子：
--
通讯作者：
Chenglei Yang;M. Qi;Jiaye Wang;Xiaoting Wang;Xiangxu Meng
中科院分区：
文献类型：
--
作者：
Chenglei Yang;M. Qi;Jiaye Wang;Xiaoting Wang;Xiangxu Meng
提出了一种基于Voronoi图（VD）的简单多边形中两点之间最短路径的查询算法。基于多边形的VD，首先从点stot找到Voronoi骨架路径（s,t），然后沿其同时通过可见性计算计算最短路径sp （s,t）。SP（s,t）可以在时间o (n)内得到报告。它可以应用于我们的三维虚拟博物馆系统中，其中多边形的VD被用作路径规划、可见性计算、碰撞检测等数据结构。
This paper proposes a new algorithm for querying the shortest path between two pointssandtin a simple polygonPbased on Voronoi diagram(VD). Based on the polygon’s VD, we first find the Voronoi skeleton pathS(s,t) from pointstot, and then along which we compute the shortest pathSP(s,t) by visibility computing simultaneously.SP(s,t) can be reported in timeO(n). It can be used in our 3D virtual museum system, in which the polygon’s VD is used as a data structure for path planning, visibility computing, collision detection, and so on.