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

【摘要】：平面上幾何物體序列遍歷問(wèn)題是計(jì)算幾何學(xué)研究領(lǐng)域的核心問(wèn)題,它不僅涉及可視性識(shí)別、最短路徑計(jì)算、算法設(shè)計(jì)與優(yōu)化等基礎(chǔ)理論問(wèn)題,而且也是機(jī)器人運(yùn)動(dòng)規(guī)劃、無(wú)人機(jī)控制等一類實(shí)際應(yīng)用問(wèn)題的抽象模型,研究這些問(wèn)題的簡(jiǎn)單、高效、實(shí)用的求解方法,不僅具有理論意義,而且也有很大的實(shí)際應(yīng)用價(jià)值。針對(duì)幾何物體序列遍歷問(wèn)題的研究,雖然已經(jīng)取得了一些成果,但這些成果一般還存在著數(shù)據(jù)結(jié)構(gòu)復(fù)雜、迭代計(jì)算次數(shù)多,以及相交點(diǎn)處理時(shí)的算法退化等問(wèn)題,圍繞這些問(wèn)題,本文展開(kāi)求解算法的優(yōu)化研究。首先針對(duì)不相交線段序列遍歷問(wèn)題的算法優(yōu)化進(jìn)行了研究。針對(duì)Rubber-band算法在求解該遍歷問(wèn)題時(shí)所存在的重復(fù)迭代計(jì)算等缺陷,采用凸鏈分解與組合優(yōu)化技術(shù)以及二分檢索樹(shù)存儲(chǔ)結(jié)構(gòu),提出了D(n3襼2n)時(shí)間復(fù)雜度的優(yōu)化算法,降低了現(xiàn)有求解算法的時(shí)間復(fù)雜度,并構(gòu)造測(cè)試數(shù)據(jù)對(duì)改進(jìn)前后的求解算法做了運(yùn)行時(shí)間性能對(duì)比分析。其次,針對(duì)可相交線段序列遍歷問(wèn)題,提出了跨線段處理技術(shù),有效地解決了Rubber-band算法不能處理線段相交點(diǎn)的問(wèn)題,并通過(guò)交換相鄰線段訪問(wèn)順序獲得了更為精確的最短遍歷路徑,設(shè)計(jì)出了D(n~2)時(shí)間復(fù)雜度的優(yōu)化算法。在此基礎(chǔ)上,針對(duì)直線序列遍歷問(wèn)題,采用構(gòu)造擴(kuò)大凸多邊形的方法,將直線序列遍歷問(wèn)題轉(zhuǎn)化為在凸多邊形中求解可相交線段的最短路徑遍歷問(wèn)題,設(shè)計(jì)出了D(n~2)時(shí)間復(fù)雜度的最優(yōu)遍歷算法,并證明其為求解直線遍歷問(wèn)題的算法時(shí)間復(fù)雜度下界。最后,針對(duì)不相交凸多邊形序列遍歷問(wèn)題,分析了凸多邊形序列的幾何特征,提出了正向劃分多邊形與逆向定位訪問(wèn)邊的組合技術(shù)以及最短路徑圖結(jié)構(gòu),設(shè)計(jì)出了O(kn)時(shí)間復(fù)雜度的最優(yōu)求解算法。本文深入地研究了平面上幾何物體序列的遍歷問(wèn)題,有效地解決了該領(lǐng)域研究中存在的一些問(wèn)題,所提出的求解算法是到目前為止的最優(yōu)解決方案,這些方法將有助于巡視員最短路徑問(wèn)題、機(jī)器人運(yùn)動(dòng)規(guī)劃等實(shí)際應(yīng)用問(wèn)題的求解。同時(shí),本文也提出了該研究領(lǐng)域有待進(jìn)一步研究的問(wè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é)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：O182.1

【參考文獻(xiàn)】

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

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

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

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

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

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

6 李發(fā)捷;KLETTE Reinhard;;多邊形序列的最短路徑算法[J];智能系統(tǒng)學(xué)報(bào);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期

，

本文編號(hào)：1636284