手机自适应网站建设维护,中国公路建设行业协会网站,佳木斯市网站建设,阿里巴巴做特卖的网站#x1f98c;#x1f98c;#x1f98c;读论文
#x1f428;#x1f428;摘要
针对点的可见性计算这一计算几何中的基础问题#xff0c;提出一种支持任意查询点的可见多边形快速计算的基于多边形Voronoi图的点可见性算法。以与Voronoi骨架路径对应的Voronoi通道概念读论文
摘要
针对点的可见性计算这一计算几何中的基础问题提出一种支持任意查询点的可见多边形快速计算的基于多边形Voronoi图的点可见性算法。以与Voronoi骨架路径对应的Voronoi通道概念以及相应的局部最短路径概念为基础按照深度优先策略对Voronoi图进行遍历在计算Voronoi骨架路径的同时计算局部最短路径并基于局部最短路径计算所遍历的多边形边的可见部分。该算法可以处理“带洞”多边形而且只对多边形进行局部访问对于“带洞”多边形由于该算法的数据结构比较简单、剖分空间合理且易于实现因此仅需O(n)空间和O(n log n)预处理时间最后给出了在三维室内虚拟场景设计与漫游系统中的应用实例结果表明文中算法是实际可行且运行时间与点的可见多边形的边数和多边形的边数均呈线性关系。
相关工作
点的可见性计算
对于点可见多边形计算问题计算几何领域有很多相关的工作。点的可见性计算是最基础的问题其典型应用包括艺术画廊中的警卫间问题、机械模型浇注、无线传感网络中的覆盖问题等。在计算机图形学、计算机游戏和虚拟现实等领域其作为实时绘制中的一种关键技术根据视点的位置计算可见区域并将可见区域中的对象加入图形绘制流水线提高绘制效率。
简单多边形的可见性算法
对于简单多边形文献[16]提出了一种基于三角化的点的可见多边形算法它首先对简单多边形进行三角化并基于三角化的结果构造查询点的最短路径树然后基于该最短路径树计算多边形的每条边相对于查询点的可见部分最后得到点的可见多边形算法时间复杂度为O(n)。
“带洞”多边形的可见性算法
近年来又出现了一些基于可见区域分割或可见图计算“带洞”多边形中点的可见多边形的算法。这些算法的数据结构一般比较复杂且构造方法较困难消耗较多的预处理时间和空间。
相关概念
多边形Voronoi图
一种将平面划分为多个区域的方式其中每个区域对应于一个特定的点集合称为“种子”或“站点”。在Voronoi图中平面上的每一点都被分配到离它最近的种子所在的区域。
- 每个Voronoi单元区域包含所有距离该种子点最近的点。 - Voronoi边界是种子点之间的垂直平分线。
简单多边形的Voronoi图是一棵树其叶节点是多边形的顶点“带洞”多边形的Voronoi图是一个图其中度数为1的节点为多边形的顶点。
简单多边形vs带洞多边形
简单只有一条边界的多边形
带洞多条边界外边界顺时针内边界逆时针
站点o
多边形中的凹顶点或边
站点的voronoi区域VR
多边形P中到o的距离比到其他任意站点距离都近的点的集合
多边形P的voronoi图VD
P中所有站点的VR的并集
voronoi的骨架路径VSP(q,pi)
多边形P中的一个点q到P的一个顶点p的Voronoi骨架路径(Voronoi Skeleton Path, VSP)是一条由系列Voronoi边首尾依次连接而成的路径用VSP(q, p)表示如图中粗虚线所示。 边的关联VR
如果边e被两个VRp1、p2所共有则这俩VR就是边e的关联VRp1和p2是e的关联边设点a为e的起点b为e的终点那么定义有向边ab若p1在ab左侧则称p1为ab的左侧关联边否则是右侧关联边
VSP对应的voronoi通道C
骨架路径的每条边所关联的两边的voronoi区域形成的通道如上图阴影区域所示。
局部最短路径SP
将VSP看作绳子将其用力拉紧变成直线可以得到在该通道中的一条最短路径称之为局部最短路径如上图中拉紧后的虚线所示。
在带洞多边形中q到pi存在多个voronoi通道因此存在多个局部最短路径。
算法描述
任意两点间的最短路径算法基本思想
在简单多边形中任意两点间只存在一条voronoi骨架路径最短路径上的点能够通过顺序遍历其voronoi骨架路径关联的多边形顶点求得。
确定最短路径的算法步骤
1. 确定两点所在的voronoi区域 2. 确定voronoi骨架路径 3. 顺序遍历voronoi骨架路径确定最短路径
算法概述
本节首先讨论多边形内计算一条边相对于给定查询点的可见部分的计算算法。充分性由引理1知SP(q, p)上的点为VSP(q, p)所关联的凹顶点如果只用VSP(q, p)的左侧关联凹顶点计算SP(q, p)则SP(q, p)为VSP(q, p)的左侧关联凹顶点的凸多边形链L_CP。
引理与定理
引理1和引理2为算法提供了理论基础定理1给出了边的可见部分的计算方法定理2给出了沿VD(P)进行深度遍历的终止条件。
算法步骤
算法1详细描述了计算点的可见多边形的过程包括判断q所在的Voronoi区域、计算VSP和SP、计算对于q的可见部分等步骤。
存在可见部分
q到pi的局部最短路径SP是一条在P内的多边形链且在qpi的右侧且q到pi1的局部最短路径SP也是一条在P内的凸多边形链且在qpi1的左侧
定理1
对于一个多边形P及其内部一点q在q到P的边pipi1的一个voronoi通道中有两个SPpipi1相对于q存在可见部分当且仅当ql1在qr1的左侧且当前voronoi通道中pipi1相对于q的可见部分可通过计算射线ql1和qr1与pipi1的交点得到。 由图所示qp3在qp6左侧根据定理p4p5相对于q存在可见部分。通过计算射线qp3、qp6与p4p5的交点可以计算出p4p5相对于q的可见部分qlqr。射线ql1和qr1直接的区域成锥体状称为可见锥体VC
停止条件 1如图所示当遍历到q2和q3时都没必要再深度搜索圈出的两个区域了因为它们后边的voronoi边关联的多边形的边肯定相对于q不可见 2带动多边形如果不设终止条件会陷入死循环。当遍历到某个voronoi顶点如q1、q2和q3后后面的voronoi边对应的边都相对于q不可见所以可以停止该方向的遍历了。
终止条件设置算法 计算VSP和SP
初始VSP和SP的计算
算法1的Step1首先确定给定点q所在的Voronoi区域VR(o)算法1的Step2用于计算初始的Voronoi最短路径和SP。 确定Voronoi骨架路径的过程通常包括以下几个步骤
1. 构造Voronoi图首先需要为给定的多边形构造Voronoi图。这个图表达了多边形内部每个点到最近站点多边形的顶点或边的距离。
2. 确定Voronoi区域对于给定的查询点q确定其所在的Voronoi区域。这个区域表示所有比到任何其他站点更接近查询点q的点的集合。
3. 计算Voronoi骨架路径通过深度优先搜索Voronoi图计算从查询点q到多边形顶点的Voronoi骨架路径。这个路径是由连接查询点q和多边形顶点的Voronoi边组成的。
4. 更新VSP在DFS过程中每当访问到一个新的Voronoi顶点时根据需要更新当前的VSP。这涉及到添加或删除Voronoi边以反映从查询点到当前顶点的路径。
5.计算SP在Voronoi通道内SP(q, p)可以通过连接VSP(q, p)上的点和多边形顶点p来计算。这通常涉及到找到VSP(q, p)上与多边形顶点p最近的点。
6.局部最短路径更新在DFS过程中随着VSP的更新相应的SP也需要更新。这涉及到在VSP上添加或删除点以确保SP始终保持为局部最短路径。
7. 确定可见性通过分析Voronoi骨架路径和局部最短路径确定多边形边相对于查询点的可见部分。
深度优先搜索DFS
访问和标记从q开始访问与其直接相连的Voronoi边并标记这些边为已访问。递归遍历对于每条已访问的Voronoi边找到与之相邻的未访问的Voronoi区域并递归地访问这些区域。这通常涉及到移动到相邻Voronoi区域的顶点或边并继续探索。回溯当一个区域的所有相邻区域都被访问后回溯到上一个顶点并继续探索其他未访问的区域。
后续VSP和SP的计算
在已计算的VSP(q, p1)和SP(q, p1)的基础上考虑如何快速确定下条边对应的2条VSP和SP这取决于TC(q-)的值。
算法分析与实例
算法效率
本文算法在预处理阶段需要构造多边形的Voronoi图一旦构造完成其可用于任意点的可见多边形查询。对于简单多边形其Voronoi图可在O(n)时间内构造出来对于“带洞”多边形的Voronoi图的构造则需要O(n log n)时间。
算法实例 给出了算法在虚拟博物馆中的应用实例展示了算法的实际效果。 做笔记
该文章的研究目的
研究背景
本文针对点的可见性计算问题提出了一种基于多边形Voronoi图的点可见性算法。该算法支持任意查询点的可见多边形快速计算对于“带洞”多边形也适用并且只对多边形进行局部访问。
研究目标
旨在提高多边形中点可见性计算的效率特别是在三维室内虚拟场景设计与漫游系统中的应用。
该文章的研究方法
Voronoi图的应用
文章提出了Voronoi通道和局部最短路径的概念通过深度优先策略对Voronoi图进行遍历在计算Voronoi骨架路径的同时计算局部最短路径并基于局部最短路径计算所遍历的多边形边的可见部分。
算法实现
算法基于Voronoi图的几何特性通过深度优先搜索遍历Voronoi图计算Voronoi骨架路径和局部最短路径从而确定点的可见多边形。
该文章的研究内容
相关概念
定义了多边形Voronoi图中的Voronoi通道和局部最短路径并提出了计算这些路径的算法。
算法描述
详细描述了算法的步骤包括如何确定点所在的Voronoi区域计算Voronoi骨架路径和局部最短路径以及如何基于这些路径计算点的可见多边形。
算法分析
分析了算法的时间复杂度和空间复杂度并讨论了算法在“带洞”多边形中的应用。
该文章的创新点
提出了Voronoi通道和局部最短路径的概念为点的可见性计算提供了新的视角。算法可以处理“带洞”多边形并且只对多边形进行局部访问提高了计算效率。算法的数据结构简单、空间合理且易于实现预处理时间复杂度为O(n log n)空间复杂度为O(n)。
该文章给我们的启发
Voronoi图可以作为解决可见性计算问题的有效工具特别是在复杂场景中。通过局部访问和深度优先搜索策略可以显著提高算法的效率。算法的简单性和实用性使其适用于实际的三维虚拟场景设计与漫游系统。 反思
从中学到了什么
1. Voronoi图在可见性计算中的应用
- 学会了如何利用Voronoi图来解决多边形中的点可见性问题特别是在复杂或“带洞”的多边形中。
2. 深度优先搜索DFS的策略
- 了解了如何通过深度优先搜索策略在Voronoi图中遍历以计算Voronoi骨架路径和局部最短路径。
3. 算法的时间和空间复杂度
- 掌握了评估算法效率的方法特别是如何分析算法的时间和空间复杂度并理解了近似线性算法和近似输出敏感算法的概念。
4. 算法的实际应用
- 认识到了这种算法在三维虚拟场景设计与漫游系统中的应用价值特别是在提高渲染效率和优化用户体验方面。
5. 计算几何中的基本概念
- 学习了Voronoi图、Voronoi骨架路径、Voronoi通道和局部最短路径等计算几何中的基本概念并理解了它们在算法中的作用。
有什么问题
1. 算法的扩展性
- 该算法是否可以扩展到非多边形如曲线边界的几何形状以及如何适应更复杂的三维场景
2. 算法的优化
- 在大规模数据集或高密度点集中算法的性能如何是否存在进一步优化空间以提高算法的效率
3. 算法的鲁棒性
- 算法对于噪声数据或不精确的输入有多鲁棒如何处理输入数据的误差
4. 实际应用中的挑战
- 在实际的三维虚拟场景中算法如何处理动态变化的场景例如移动的物体或变化的视角
5. 算法的并行化
- 考虑到现代计算硬件的发展该算法是否可以并行化以利用多核处理器的优势
