可掃描簡單多邊形中兩守衛(wèi)間min-max距離求解研究.pdf

1、可掃描簡單多邊形中兩守衛(wèi)問題是一些實際應(yīng)用問題的抽象模型，在掃描過程中兩個守衛(wèi)保持相互可見的約束條件下，研究最優(yōu)掃描方案，不僅具有理論意義，而且具有重要的實際應(yīng)用價值。一般而言，可掃描簡單多邊形中兩守衛(wèi)的掃描過程包括直掃描和反掃描兩個過程，本文著重研究反掃描的情形。
　　 本文對可掃描簡單多邊形中兩守衛(wèi)間最大可視距離達到最小的問題進行了研究。首先，分析和研究了兩個守衛(wèi)問題中相關(guān)資料，對計算幾何的基本概念與經(jīng)典的藝術(shù)畫廊問題、Fr

2、échet距離問題，以及兩個守衛(wèi)問題等做了較為詳細的論述，以此為基礎(chǔ)，深入分析了可掃描簡單多邊形的特性，著重研究反掃描特性，分析構(gòu)成原子反掃描的可能情形，以及最優(yōu)掃描劃分為若干個原子直掃描和原子反掃描的構(gòu)造過程，給出了反掃描過程中構(gòu)造關(guān)鍵掃描線段和原子反掃描的方法，結(jié)合原子直掃描的相關(guān)結(jié)論，設(shè)計出了原子掃描圖，并用迪杰斯特拉算法求解min-max問題，得到了最優(yōu)掃描方案。通過設(shè)計數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)了一個O(nlogn)時間復(fù)雜度的解決反掃描