?

超聲檢測(cè)技術(shù)的妙用

碰撞干涉檢測(cè)問(wèn)題是確定不同的物體在空間是否占有相同區(qū)域的問(wèn)題。該問(wèn)題可描述如下：“給定N 個(gè)物體s1，s2 ，… ，sn，它們?cè)诳臻g中的位置是由定義在時(shí)間域[t0，t1] 上的函數(shù)f1，f2，…，fn來(lái)確定的，判定在這個(gè)時(shí)間域內(nèi)相同時(shí)刻是否存在任何一對(duì)物體占有公共空間”。該問(wèn)題的描述說(shuō)明了這樣的意義，物體占有的空間決定于時(shí)間，由此又引出靜態(tài)干涉和動(dòng)態(tài)干涉檢測(cè)的定義。

靜態(tài)干涉檢測(cè): 物體在空間中的位置是可移動(dòng)的，但不隨時(shí)間變化，位置的變化是由其它參數(shù)定義的，判別是否有任何一對(duì)物體占有公共空間?？臻g布局和裝配干涉檢測(cè)等即屬于此類問(wèn)題。

動(dòng)態(tài)干涉檢測(cè)：動(dòng)態(tài)干涉檢測(cè)與時(shí)間相關(guān)，即碰撞檢測(cè)。物體在空間中的位置是隨時(shí)間變化的，它可分為二種情況：

(1) 運(yùn)動(dòng)空間中只有一個(gè)物體是運(yùn)動(dòng)的。例如一個(gè)機(jī)器人在車間里運(yùn)動(dòng)，機(jī)器人是運(yùn)動(dòng)的，車間里的其它障礙物是靜止的；

(2) 一對(duì)物體都必須是運(yùn)動(dòng)的，例如車間里兩個(gè)運(yùn)動(dòng)的機(jī)器人。無(wú)論是靜態(tài)干涉檢測(cè)還是動(dòng)態(tài)干涉檢測(cè)，目的都是要求避免物體間的碰撞。

Tetsuya，Toshiaki和Mario等人提出了一種稱為空間占有的方法，即物體在目標(biāo)空間移動(dòng)，當(dāng)試圖占有相同的球體時(shí)來(lái)檢測(cè)它們的碰撞。這種算法基于這樣一條原理沒(méi)有任何物體和其它物體占有同一個(gè)球體，也不需要特殊的計(jì)算來(lái)檢測(cè)碰撞。并且，在它們的方法中，每個(gè)物體連同它們所占有的球體在三維空間中都被賦予一個(gè)名字，因而其它物體知道它們和哪個(gè)物體發(fā)生碰撞。

chin和wang研究了兩個(gè)多邊形的相交和最小距離問(wèn)題。利用可視邊鏈和凸的頂點(diǎn)相對(duì)于其內(nèi)部點(diǎn)的單調(diào)性，提出了判別凸一邊形和一個(gè)簡(jiǎn)單非凸m-邊形的相交問(wèn)題的最優(yōu)算法，并且研究了當(dāng)兩個(gè)多邊形相交時(shí)一個(gè)多邊形是否被另一個(gè)多邊形完全包含的問(wèn)題，其時(shí)間復(fù)雜度都為o(m+n)。

汪嘉業(yè)利用單調(diào)折線研究了在一個(gè)多邊形的凸包和另一個(gè)多邊形不相交的條件下，確定兩個(gè)多邊形是否碰撞，并在碰撞時(shí)確定全部碰撞部位的問(wèn)題，提出了時(shí)間復(fù)雜度為o(m+n)的最優(yōu)算法，并且其算法還可推廣到確定包含有圓弧邊的多邊形之間的最初碰撞部位。

李輝利用最大最小坐標(biāo)的頂點(diǎn)子集的方法研究了一個(gè)凸多邊形沿一給定方向移動(dòng)時(shí)是否與另一凸多邊形發(fā)生碰撞，并且利用斜支撐線的方法來(lái)研究一個(gè)凸多邊形相對(duì)于另一個(gè)凸多邊形的可移動(dòng)區(qū)域問(wèn)題，提出了時(shí)間復(fù)雜度為o(log(n+m))和o(m+n)的算法，在常數(shù)意義下，它們都是最優(yōu)的。