Link-2可視多邊形中三守衛(wèi)問題的求解算法研究.pdf

1、本文針對三個守衛(wèi)(three-guard)問題進行研究，該問題可描述為:給定平面上一個簡單多邊形P，以及P邊界上的兩點s和t（分別作為起始點和終點）。點s和t將多邊形邊界分割成兩條邊界鏈L和R。三個守衛(wèi)按從s到t的方向移動，協(xié)同完成對P的掃描，并最終將可能的入侵者從t點驅(qū)逐出去。要求兩守衛(wèi)分別沿L鏈和R鏈移動，第三個守衛(wèi)可在P內(nèi)部或P的邊界上移動，且在移動過程中相鄰守衛(wèi)要時刻保持相互可見。
　　論文首先論述了計算幾何領(lǐng)域中的幾個經(jīng)

2、典問題，然后在論述相關(guān)理論知識的基礎(chǔ)上，著重研究了三個守衛(wèi)問題的掃描機理。為解決三個守衛(wèi)的掃描問題，詳細分析了two-guard問題的求解思路，通過分析three-guard問題與two-guard問題求解方案中移動操作對應約束條件，在引入link-2可視和link-2射點等概念的基礎(chǔ)上，提出了判斷給定簡單多邊形是否為三個守衛(wèi)可掃描的多邊形的充分必要條件，并在三個守衛(wèi)可掃描的前提下，論述了具體掃描方案的構(gòu)造過程。本文提出的算法能夠在O(