多邊形搜索的幾種策略研究.pdf

1、多邊形搜索是計(jì)算幾何中的一類基本問題,這類問題考慮的是如何利用一個(gè)或多個(gè)移動(dòng)的搜索者(搜索者有不同的視覺范圍)對(duì)一個(gè)多邊形區(qū)域進(jìn)行搜索以便檢測(cè)到移動(dòng)的入侵者。搜索者和入侵者均可用一個(gè)點(diǎn)表示,都可以在多邊形區(qū)域內(nèi)連續(xù)、任意地移動(dòng),但是后者的移動(dòng)速度要比前者快。多邊形搜索問題與機(jī)器人技術(shù)相結(jié)合被廣泛應(yīng)用于航海,安全防御,目標(biāo)探測(cè)和追蹤等諸多領(lǐng)域。因此,對(duì)于一個(gè)給定的多邊形,判斷其是否可被一個(gè)或多個(gè)不同視覺的搜索者搜索,以及如何找出一條有效的

2、搜索路徑顯得尤為重要。
　　 本文主要研究的是用一個(gè)邊界單線搜索者(1-searcher)對(duì)一個(gè)含有n條邊的簡(jiǎn)單多邊形的搜索問題。所謂邊界單線搜索者,是指搜索者只能沿多邊形的邊界移動(dòng)且從其位置只能發(fā)出一束光。作為一種特殊類型的搜索模型得到了許多學(xué)者的研究,雖然已經(jīng)提出了一些檢測(cè)和搜索算法,但各個(gè)算法還是存在一些不足。本文在對(duì)多邊形邊界單線搜索的研究現(xiàn)狀和存在的不足進(jìn)行深入分析的基礎(chǔ)上做了以下工作：首先,闡述了多邊形搜索問題的相關(guān)

3、概念,并將雙切線與多邊形的可視圖(ν圖)聯(lián)系構(gòu)造了簡(jiǎn)化骨架ν圖。其次,針對(duì)邊界單線搜索問題,給出了檢測(cè)多邊形的邊界單線可搜索性的充要條件。利用這些條件判斷一個(gè)多邊形是否可被一個(gè)邊界單線搜索者搜索只需O(n)的時(shí)間和空間,改進(jìn)了以前的時(shí)間復(fù)雜度O(nlogn)。此時(shí)間復(fù)雜度是檢測(cè)多邊形邊界單線可搜索性的下界,已不可能再優(yōu)化。同時(shí),對(duì)這些特性的正確性用簡(jiǎn)化骨架ν圖論證,簡(jiǎn)化了已有的證明過程。最后,給出了一種新的邊界單線搜索算法,并對(duì)此算法進(jìn)