簡(jiǎn)單多邊形內(nèi)LR可視問題的求解算法研究.pdf

1、LR可視性問題是計(jì)算幾何領(lǐng)域的重要研究課題之一。通過對(duì)LR可視多邊形特性的研究,能夠得到求解計(jì)算幾何經(jīng)典問題的有效算法。因此,對(duì)于LR可視多邊形的研究,不僅具有重大的理論研究意義,而且也有非常重要的實(shí)際應(yīng)用價(jià)值。
　　 本文在論述簡(jiǎn)單多邊形分割的相關(guān)理論的基礎(chǔ)上,對(duì)簡(jiǎn)單多邊形的LR可視性的判別問題進(jìn)行了深入的研究,給出了判別一個(gè)簡(jiǎn)單多邊形是否為L(zhǎng)R可視多邊形的充分必要條件,并加以嚴(yán)格證明。通過將LR可視多邊形上的非冗余組件架構(gòu)映

2、射成一組圓上的弦,給出了LR可視多邊形所具有的簡(jiǎn)單特性。通過這些特性,本文提出了一個(gè)時(shí)間復(fù)雜度為O(n)的計(jì)算LR可視多邊形內(nèi)部非冗余組件數(shù)目的算法,通過該算法以及判別一個(gè)簡(jiǎn)單多邊形是否為L(zhǎng)R可視多邊形的充分必要條件,可以在線性時(shí)間內(nèi)判斷一個(gè)簡(jiǎn)單多邊形是否具有LR可視性。這大大簡(jiǎn)化了利用找出多邊形內(nèi)的點(diǎn)對(duì)來判斷多邊形是否具有LR可視性的這一已知算法。
　　 為了驗(yàn)證算法的可行性和有效性,本文針對(duì)測(cè)試數(shù)據(jù)求解出了簡(jiǎn)單多邊形內(nèi)部非冗