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

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

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

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