论文部分内容阅读
本文讨论了二维平面下曲线的可见性问题。我们研究的两个主要内容是：曲线的弱可见多边形算法,沿曲线移动的点的实时可见多边形算法。曲线与直线不同,可能具有复杂的形状与性质。本文研究的对象是可解析曲线,即像多项式函数曲线、三角函数曲线等各种具有参数方程的曲线。由于利用了可解析曲线的性质及相关数值算法,我们的算法具有高精确度与高灵敏性。我们将一部分可解析曲线定义为CCTH,并提出了internal CCTH与non-internal CCTH的概念。我们给出了CCTH的弱可见多边形算法,此算法对于internal CCTH能够达到O(n)的时间与空间复杂度,与线段的弱可见多边形算法相同。对于non-internal CCTH,我们给出了将其分割为多段internal CCTH的算法,然后每段均可调用internal CCTH的弱可见多边形算法。在非极端情况下分段数一般远小于O(n)；在极端情况下,算法的时间复杂度为O(n2),并且我们证明了这个时间复杂度已无法再优化。对于曲线轨迹上移动点的可见多边形问题,我们给出了轨迹预处理和场景预处理两种方法。我们借鉴了文献[10]给出了CCTH轨迹预处理算法,其复杂度与直线轨迹预处理算法相同。而后我们以三角剖分为例,给出了CCTH场景预处理算法,算法的预处理过程耗费O(n2)的时间与空间,能够在轨迹穿过的每个分块上依次计算关键点,假设曲线轨迹在单个分块上的关键点规模数为O(m),则在每个分块上定位关键点所用的时空复杂度均为O(m),生成持久化数据结构的时间复杂度O(mlogm)。在非极端情况下O(m)<<O(n)。然后我们简单讨论了CCTH轨迹预处理算法和场景预处理算法的并发性。归纳的,本文工作与创新如下：1)为方便描述研究成果,对曲线进行了分类,提出了CCTH以及internal CCTH与non-internal CCTH的概念。2)给出了internal CCTH的弱可见多边形算法,这个算法能够在线性的时间与空间代价内完成,与直线的弱可见多边形算法效率相同。3)给出了non-internal CCTH的弱可见多边形算法。对于non-internal CCTH,我们给出了将其分割为多段internal CCTH的算法,然后每段均可调用internal CCTH的弱可见多边形算法。在非极端情况下分段数一般<<O(n)；在极端情况下,算法的时间复杂度为O(n2),并且我们证明了这个时间复杂度已无法再优化。4)给出了CCTH轨迹预处理算法。internal CCTH轨迹预处理算法其复杂度与直线轨迹预处理算法相同：计算关键点的时空复杂度均为线性,生成持久化数据结构的时间复杂度为O(nlogn),空间复杂度为O(n)。non-internal CCTH轨迹预处理算法计算关键点的时间复杂度在极端情况下为O(n2),但一般远小于这个规模。5)我们以三角剖分为例,给出了CCTH场景预处理算法,算法的预处理过程耗费O(n2)的时间与空间,能够在轨迹穿过的每个分块上依次计算关键点,假设曲线轨迹在单个分块上的关键点规模数为O(m),则在每个分块上定位关键点所用的时空复杂度均为O(m),生成持久化数据结构的时间复杂度O(mlogm)。在非极端情况下O(m)<<O(n)。6)我们讨论了CCTH轨迹预处理算法和场景预处理算法的并发性。本文属于计算几何与虚拟现实问题领域,在路径规划,虚拟博物馆之类实际应用中有一定价值。