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

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

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