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

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

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