可解析曲线的可见性相关问题研究

摘要

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