本文選題：計算幾何　切入點：幾何物體序列　出處：《大連海事大學(xué)》2016年博士論文　論文類型：學(xué)位論文

【摘要】：平面上幾何物體序列遍歷問題是計算幾何學(xué)研究領(lǐng)域的核心問題,它不僅涉及可視性識別、最短路徑計算、算法設(shè)計與優(yōu)化等基礎(chǔ)理論問題,而且也是機(jī)器人運動規(guī)劃、無人機(jī)控制等一類實際應(yīng)用問題的抽象模型,研究這些問題的簡單、高效、實用的求解方法,不僅具有理論意義,而且也有很大的實際應(yīng)用價值。針對幾何物體序列遍歷問題的研究,雖然已經(jīng)取得了一些成果,但這些成果一般還存在著數(shù)據(jù)結(jié)構(gòu)復(fù)雜、迭代計算次數(shù)多,以及相交點處理時的算法退化等問題,圍繞這些問題,本文展開求解算法的優(yōu)化研究。首先針對不相交線段序列遍歷問題的算法優(yōu)化進(jìn)行了研究。針對Rubber-band算法在求解該遍歷問題時所存在的重復(fù)迭代計算等缺陷,采用凸鏈分解與組合優(yōu)化技術(shù)以及二分檢索樹存儲結(jié)構(gòu),提出了D(n3襼2n)時間復(fù)雜度的優(yōu)化算法,降低了現(xiàn)有求解算法的時間復(fù)雜度,并構(gòu)造測試數(shù)據(jù)對改進(jìn)前后的求解算法做了運行時間性能對比分析。其次,針對可相交線段序列遍歷問題,提出了跨線段處理技術(shù),有效地解決了Rubber-band算法不能處理線段相交點的問題,并通過交換相鄰線段訪問順序獲得了更為精確的最短遍歷路徑,設(shè)計出了D(n~2)時間復(fù)雜度的優(yōu)化算法。在此基礎(chǔ)上,針對直線序列遍歷問題,采用構(gòu)造擴(kuò)大凸多邊形的方法,將直線序列遍歷問題轉(zhuǎn)化為在凸多邊形中求解可相交線段的最短路徑遍歷問題,設(shè)計出了D(n~2)時間復(fù)雜度的最優(yōu)遍歷算法,并證明其為求解直線遍歷問題的算法時間復(fù)雜度下界。最后,針對不相交凸多邊形序列遍歷問題,分析了凸多邊形序列的幾何特征,提出了正向劃分多邊形與逆向定位訪問邊的組合技術(shù)以及最短路徑圖結(jié)構(gòu),設(shè)計出了O(kn)時間復(fù)雜度的最優(yōu)求解算法。本文深入地研究了平面上幾何物體序列的遍歷問題,有效地解決了該領(lǐng)域研究中存在的一些問題,所提出的求解算法是到目前為止的最優(yōu)解決方案,這些方法將有助于巡視員最短路徑問題、機(jī)器人運動規(guī)劃等實際應(yīng)用問題的求解。同時,本文也提出了該研究領(lǐng)域有待進(jìn)一步研究的問題。
[Abstract]:The ergodic problem of geometric object sequences on the plane is the core problem in the field of computational geometry. It not only involves the basic theoretical problems such as visibility recognition, shortest path calculation, algorithm design and optimization, but also the robot motion planning. Abstract model of UAV control and other practical application problems. It is not only of theoretical significance to study the simple, efficient and practical solving methods of these problems. The research on the ergodic problem of geometric object sequences has made some achievements, but these results generally still have complex data structure and many iterations. And the degradation of the algorithm when dealing with intersection points, and so on. In this paper, the optimization of the solution algorithm is studied. Firstly, the optimization of the traversal problem of disjoint segments is studied. The shortcomings of the Rubber-band algorithm in solving the traversal problem are discussed, such as repeated iterative computation, and so on. By using convex chain decomposition and combinatorial optimization techniques and binary retrieval tree storage structure, an optimization algorithm for time complexity is proposed, which reduces the time complexity of existing algorithms. The performance of the improved algorithm is compared and analyzed by constructing the test data. Secondly, for the traversal problem of intersectable line segments, a cross-segment processing technique is proposed. The problem that the Rubber-band algorithm can not deal with the intersection points of line segments is effectively solved, and the shortest traversal path is obtained by exchanging the access order of adjacent segments, and an optimized algorithm of time complexity is designed. In order to solve the problem of linear sequence traversal, the problem of linear sequence traversal is transformed into the shortest path traversal problem of intersectable line segments in convex polygons by using the method of constructing extended convex polygons. An optimal ergodic algorithm with DX 2) time complexity is designed and proved to be the lower bound of the time complexity of the algorithm for solving the linear traversal problem. Finally, the geometric characteristics of convex polygon sequences are analyzed for the traversal problem of disjoint convex polygon sequences. In this paper, the combination technique of forward partitioning polygon and converse location access edge and the structure of shortest path graph are proposed. An optimal algorithm for solving the time complexity of Oknn is designed. In this paper, the ergodic problem of geometric object sequences on the plane is studied in depth. Some problems in this field are solved effectively. The proposed algorithms are the optimal solutions up to now. These methods will be helpful to the shortest path problem of the inspector. The problem of robot motion planning and other practical applications is solved. At the same time, the problems that need to be further studied in this research field are also presented in this paper.
【學(xué)位授予單位】：大連海事大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：O182.1

【參考文獻(xiàn)】

相關(guān)期刊論文 前7條

1 張紀(jì)升;賈利民;牛樹云;李宏海;;基于K-短路徑的路網(wǎng)關(guān)鍵路段集合的辨識與分析[J];長安大學(xué)學(xué)報(自然科學(xué)版);2015年03期

2 司維超;齊玉東;韓維;;基于融合Dijkstra的凸殼算法的艦載機(jī)機(jī)庫調(diào)運規(guī)劃[J];系統(tǒng)工程與電子技術(shù);2015年03期

3 劉斌;王濤;;一種高效的平面點集凸包遞歸算法[J];自動化學(xué)報;2012年08期

4 鞏敦衛(wèi);耿娜;張勇;;密集障礙物環(huán)境下基于凸包和微粒群優(yōu)化的機(jī)器人路徑規(guī)劃[J];控制理論與應(yīng)用;2012年05期

5 吳文周;李利番;王結(jié)臣;;平面點集凸包Graham算法的改進(jìn)[J];測繪科學(xué);2010年06期

6 李發(fā)捷;KLETTE Reinhard;;多邊形序列的最短路徑算法[J];智能系統(tǒng)學(xué)報;2008年01期

7 ;A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram[J];Journal of Zhejiang University Science A(Science in Engineering);2006年09期

，

本文編號：1636284