本文選題：計算幾何　切入點：簡單多邊形　出處：《大連海事大學(xué)》2017年碩士論文

【摘要】：本文針對簡單多邊形中l(wèi)ink-kLR可視多邊形的判別問題進行研究。由于LR可視多邊形的判別是求解巡視員最短路徑等問題的基礎(chǔ)問題,因此本課題的研究不僅具有理論意義,而且具有很大的實際應(yīng)用價值。本文在論述簡單多邊形的可視性等概念的基礎(chǔ)上,分析了link-k LR可視多邊形的幾何特征,給出了link-k反射點、link-k射點、link-k組件以及非冗余l(xiāng)ink-k組件的求解方法,詳細(xì)論述了非冗余l(xiāng)ink-k組件的求解過程。分析了非冗余l(xiāng)ink-k組件影響簡單多邊形的link-kLR可視性的相關(guān)因素,依據(jù)計算出的非冗余l(xiāng)ink-k組件,提出了判別簡單多邊形是否為link-k LR可視多邊形的充分必要條件,并采用將非冗余組件映射為圓上的有向弦,對所提出的判別條件進行了嚴(yán)格的證明。根據(jù)所提出的判別條件,以k2為例,設(shè)計出了時間復(fù)雜度為O(nlogn)的判別給定簡單多邊形是否為link-2LR可視多邊形的求解算法,并指出該算法可拓展應(yīng)用于求解一般link-kLR可視多邊形的判別問題,同時對link-k LR可視多邊形判別算法的時間性能做較為詳細(xì)的分析。本文利用非冗余組件的相關(guān)特性,首次給出了時間復(fù)雜度為O(nlogn),對于給定簡單多邊形是否為link-kLR可視多邊形的判別算法。
[Abstract]:Aiming at the problem of link-kLR in visual discrimination of simple polygon polygon are studied. The discriminant LR visibility polygons is a basic problem solving inspector shortest path problem, so this research has not only theoretical significance, but also has great practical value. This paper discussed the visibility on the concept of simple polygon analysis of the geometric features of link-k, the LR visibility polygons, given the link-k reflex point, link-k radio, link-k components and the method of solving non redundant link-k components, discusses in detail the process of solving non redundant link-k components. Analysis of the non redundant link-k component factors affecting link-kLR visibility of a simple polygon, based on the non redundant link-k the calculated component, proposed the necessary and sufficient conditions for simple polygon is link-k LR visibility polygons, and the non redundant The components are mapped to the circle to the string, the criteria proposed are proved strictly. According to the criteria proposed by K2, for example, designed the time complexity of O (nlogn) criterion is given a simple polygon algorithm for solving the link-2LR visibility polygons, and points out that the algorithm can discrimination is extended to solve general link-kLR visibility polygons, and do a more detailed analysis on the link-k LR visual discrimination polygon and the time performance of the algorithm. This paper uses the related characteristics of non redundant components are given for the first time, the time complexity is O (nlogn), for a given simple polygon is a polygon. Visual discrimination algorithm link-kLR

【學(xué)位授予單位】：大連海事大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O18

【相似文獻】

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

1 羌亮;孫志揮;;一種基于免疫控制圖的改進判別算法及其應(yīng)用[J];科技信息;2006年02期

2 田永林，，高顯連，李應(yīng)國;WINGIS的多邊形內(nèi)點判別算法[J];林業(yè)資源管理;1994年06期

3 王海江,王波;遙感影像混合象元的色調(diào)合成概率判別算法研究[J];安徽師范大學(xué)學(xué)報(自然科學(xué)版);2000年04期

4 ;[J];;年期

相關(guān)會議論文 前1條

1 張立東;王英龍;潘景山;段青;;基于FANN理論的城市道路交通狀態(tài)判別算法[A];2007中國控制與決策學(xué)術(shù)年會論文集[C];2007年

相關(guān)碩士學(xué)位論文 前2條

1 張琪;Link-k LR可視多邊形的判別算法研究[D];大連海事大學(xué);2017年

2 張文青;基于車載視頻的車輛判別算法研究[D];大連海事大學(xué);2013年

本文編號：1676042