支持空間分析的并行算法的研究與實現(xiàn).pdf

1、空間數(shù)據的復雜性會導致空間數(shù)據處理的延遲，這對實時性要求比較高的應用問題如軍事作戰(zhàn)等問題產生了巨大的挑戰(zhàn)。設計支持空間分析的并行算法是解決此類問題的有效方法，然而，目前國內外對并行空間分析的算法研究卻很少。 本文的工作主要包括以下幾個方面： 1、采用平面掃描樹技術將平面掃描算法并行化。平面掃描樹技術可應用于梯形分解，點定位等空間分析中，本文利用平面掃描樹技術進行空間分析前先對一般的平面掃描樹進行預處理，在樹的各結點中增

2、加一些指針和結構，使得點定位的時間復雜度從O(log2n)降低到O(logn)。 2、采用分解歸并技術將平面掃描算法并行化?？臻g拓撲分析是許多復雜空間分析算法的基礎，本文利用分解歸并的方法設計并實現(xiàn)了并行空間拓撲分析算法。 3、許多空間分析算法都可歸結為凸包問題的求解，本文改進并實現(xiàn)了求取平面散亂點集凸包的并行算法，和已有并行算法相比，該算法設計更加簡單，計算量更小。 4、本文的空間拓撲分析算法是以Real