可解析曲線的可見性相關問題研究.pdf

1、本文討論了二維平面下曲線的可見性問題。我們研究的兩個主要內(nèi)容是：曲線的弱可見多邊形算法，沿曲線移動的點的實時可見多邊形算法。
　　 曲線與直線不同，可能具有復雜的形狀與性質(zhì)。本文研究的對象是可解析曲線，即像多項式函數(shù)曲線、三角函數(shù)曲線等各種具有參數(shù)方程的曲線。由于利用了可解析曲線的性質(zhì)及相關數(shù)值算法，我們的算法具有高精確度與高靈敏性。我們將一部分可解析曲線定義為CCTH，并提出了internal CCTH與non-interna

2、lCCTH的概念。
　　 我們給出了CCTH的弱可見多邊形算法，此算法對于internal CCTH能夠達到O(n)的時間與空間復雜度，與線段的弱可見多邊形算法相同。對于non-internalCCTH，我們給出了將其分割為多段internal CCTH的算法，然后每段均可調(diào)用internal CCTH的弱可見多邊形算法。在非極端情況下分段數(shù)一般遠小于O(n)；在極端情況下，算法的時間復雜度為O(n2)，并且我們證明了這個時間復

3、雜度已無法再優(yōu)化。
　　 對于曲線軌跡上移動點的可見多邊形問題，我們給出了軌跡預處理和場景預處理兩種方法。我們借鑒了文獻[10]給出了CCTH軌跡預處理算法，其復雜度與直線軌跡預處理算法相同。而后我們以三角剖分為例，給出了CCTH場景預處理算法，算法的預處理過程耗費O(n2)的時間與空間，能夠在軌跡穿過的每個分塊上依次計算關鍵點，假設曲線軌跡在單個分塊上的關鍵點規(guī)模數(shù)為O(m)，則在每個分塊上定位關鍵點所用的時空復雜度均為O(m

4、)，生成持久化數(shù)據(jù)結構的時間復雜度O(mlogm)。在非極端情況下O(m)<　　 歸納的，本文工作與創(chuàng)新如下：
　　 1)為方便描述研究成果，對曲線進行了分類，提出了CCTH以及internal CCTH與non-internal CCTH的概念。
　　 2)給出了internal CCTH的弱可見多邊形算法，這個算法能夠在線性的時間

5、與空間代價內(nèi)完成，與直線的弱可見多邊形算法效率相同。
　　 3)給出了non-internal CCTH的弱可見多邊形算法。對于non-internal CCTH，我們給出了將其分割為多段internal CCTH的算法，然后每段均可調(diào)用internalCCTH的弱可見多邊形算法。在非極端情況下分段數(shù)一般<<0(n)；在極端情況下，算法的時間復雜度為O(n2)，并且我們證明了這個時間復雜度已無法再優(yōu)化。
　　 4)給出了

6、CCTH軌跡預處理算法。internal CCTH軌跡預處理算法其復雜度與直線軌跡預處理算法相同：計算關鍵點的時空復雜度均為線性，生成持久化數(shù)據(jù)結構的時間復雜度為O(nlogn)，空間復雜度為O(n)。non-internal CCTH軌跡預處理算法計算關鍵點的時間復雜度在極端情況下為O(n2)，但一般遠小于這個規(guī)模。
　　 5)我們以三角剖分為例，給出了CCTH場景預處理算法，算法的預處理過程耗費O(n2)的時間與空間，能夠在