行走機(jī)器人避障問題1

1、下圖是一個(gè)100×80的平面場(chǎng)景圖，在R（0，0）點(diǎn)處有一個(gè)機(jī)器人，機(jī)器人只能在該100×80的范圍內(nèi)活動(dòng)，圖中四個(gè)矩形區(qū)域是機(jī)器人不能與之發(fā)生碰撞的障礙物，障礙物的數(shù)學(xué)描述分別為B1（20，40；5，10）、B2（30，30；10，15）、B3（70，50；15，5）、B4（85，15；5，10），其中B1（20，40；5，10）表示一個(gè)矩形障礙物，其中心坐標(biāo)為（20，40），5表示從中心沿橫軸方向左右各5個(gè)單位，即矩形沿橫軸方向長(zhǎng)5×2=10個(gè)單位，10表示從中心沿縱軸方向上下各10個(gè)單位，即矩形沿縱軸方向長(zhǎng)10×2=20個(gè)單位，所以，障礙物B1的中

2、心在（20，40），大小為10×20個(gè)單位的矩形，其它三個(gè)障礙物的描述完全類似。在平面場(chǎng)景中、障礙物外指定一點(diǎn)為機(jī)器人要到達(dá)的目標(biāo)點(diǎn)（要求目標(biāo)點(diǎn)與障礙物的距離至少超過1個(gè)單位），為此，須要確定機(jī)器人的最優(yōu)行走路線由直線段和圓弧線段組成的光滑曲線，其中圓弧線段是機(jī)器人轉(zhuǎn)彎路線，機(jī)器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑是與直線相切的一圓形曲線段，也可以是兩個(gè)或多個(gè)相切的圓弧曲線段組成，但每個(gè)圓形路線的半徑都必須大于某個(gè)最小轉(zhuǎn)彎半徑，假設(shè)為1個(gè)單位。另外，為了不與障礙物發(fā)生碰撞，要求機(jī)器人行走線路與障礙物間的最短距離為1個(gè)單位，越遠(yuǎn)越安全，否則將發(fā)生碰撞，若碰撞發(fā)生，則機(jī)器人無(wú)法到達(dá)目標(biāo)點(diǎn)，行走失敗。

3、請(qǐng)回答如下問題：1. 場(chǎng)景圖中有三個(gè)目標(biāo)點(diǎn)A（50，40）、B（75，60）、C（95，20），請(qǐng)用數(shù)學(xué)建模的方法給出機(jī)器人從R（0，0）出發(fā)安全到達(dá)每個(gè)目標(biāo)點(diǎn)的最短路線。2. 求機(jī)器人從R（0，0）出發(fā)，依次安全通過A、B到達(dá)C的最短路線。二、 問題分析1、問題一中要求求定點(diǎn)R（0, 0）按照一定的行走規(guī)則繞過障礙物到達(dá)目標(biāo)點(diǎn)的最短路徑，我們先可以包絡(luò)線畫出機(jī)器人行走的危險(xiǎn)區(qū)域，這樣的話，拐角處就是一個(gè)半徑為1的四分之一圓弧，通過那么然后采用拉繩子的方法尋找可能的最短路徑（比如求R和A之間的最短路徑，我們就可以連接R和A之間的一段繩子，以拐角處的圓弧為支撐拉緊，那么這段繩子的長(zhǎng)度便是R到A的

4、一條可能的最短路徑），然后采用窮舉法列出R到每個(gè)目標(biāo)點(diǎn)的可能路徑的最短路徑，然后比較其大小便可得出R到目標(biāo)點(diǎn)的最短路徑。2、問題二中要求求定點(diǎn)R（0， 0）經(jīng)過中間的若干點(diǎn)按照一定的規(guī)則繞過障礙物到達(dá)目標(biāo)點(diǎn)，這使我們考慮就不僅僅是經(jīng)過障礙物拐點(diǎn)的問題，也應(yīng)該考慮經(jīng)過路徑中的目標(biāo)點(diǎn)處轉(zhuǎn)彎的問題，這時(shí)簡(jiǎn)單的線圓結(jié)構(gòu)就不能解決這種問題，我們?cè)诠拯c(diǎn)及途中目標(biāo)點(diǎn)處都采用最小轉(zhuǎn)彎半徑的形式，也可以適當(dāng)?shù)淖儞Q拐點(diǎn)處的拐彎半徑，使機(jī)器人能夠沿直線通過途中的目標(biāo)點(diǎn)，然后建立優(yōu)化模型對(duì)這兩種方案分別進(jìn)行優(yōu)化，最終求得最短路徑。三、 模型假設(shè)1、假設(shè)障礙物全是矩形。2、假設(shè)機(jī)器人能夠抽象成點(diǎn)來(lái)處理。四、符號(hào)說(shuō)明符號(hào)

5、符號(hào)說(shuō)明L路徑的總長(zhǎng)度第段切線的長(zhǎng)度第段圓弧的長(zhǎng)度轉(zhuǎn)彎半徑障礙物上的任意點(diǎn)與行走路徑之間的最短距離五、模型的建立5.1先來(lái)證明一個(gè)猜想：猜想一：具有圓形限定區(qū)域的最短路徑是由兩部分組成的：一部分是平面上的自然最短路徑（即直線段），另一部分是限定區(qū)域的部分邊界，這兩部分是相切的，互相連接的。（即問題分析中的拉繩子拉到最緊時(shí)的狀況）證明：假設(shè)在平面中有A（a，0）和B（-a，0）兩點(diǎn)，中間有一個(gè)半圓形的障礙物，證明從A到B的最路徑為AB。平面上連接兩點(diǎn)最短的路徑是通過這兩點(diǎn)的直線段，但是連接兩點(diǎn)的線段于障礙物相交，所以設(shè)法嘗試折線路徑。在y軸上取一點(diǎn)C（0，y），若y適當(dāng)大，則折線ACB與障礙物不

6、相交，折線ACB的長(zhǎng)度為：顯然隨著y的減小而減小，減小得，即,使得與與障礙物相切，切點(diǎn)分別為E和F,顯然是這種折線路徑中最短的。由于滿足0<<的角滿足<,所以易知弧度EF小于的長(zhǎng)， 即<E,從而+FB<,記線段AE、弧度EF、線段FB為AEFB,那么AEFB比任何折線路徑都短。下面在考察一條不穿過障礙物的任何一條路徑，設(shè)其分別于OE和OF的延長(zhǎng)線交與P、Q兩點(diǎn)，記A和P之間的路徑長(zhǎng)度為，顯然>|AP|,又由AEEO,所以|AP|>AE,從而>AE,同理可得>BF。再來(lái)比較PQ之間路徑長(zhǎng)度和圓弧EF的長(zhǎng)度的大小。若PQ之間的路徑可有極坐標(biāo)方程

7、,則有,可得：=-亦即路徑APQB的長(zhǎng)度超過路徑AEFB的長(zhǎng)度。以上證明足以說(shuō)明了AEFB是滿足條件A到B的最短路徑。5.2 模型準(zhǔn)備一有了4.1中的定理，我們就可以這樣認(rèn)為，起點(diǎn)到目標(biāo)點(diǎn)無(wú)論中間障礙物有多少，最短路徑都應(yīng)該是若干個(gè)線圓結(jié)構(gòu)所組成。在本題中存在障礙物的狀況，且障礙物在拐點(diǎn)處的危險(xiǎn)區(qū)域是一個(gè)半徑為1的圓弧，所以結(jié)合定理一，我們易知，求兩點(diǎn)之間的最短路徑中的轉(zhuǎn)彎半徑我們應(yīng)該按照最小的轉(zhuǎn)彎半徑來(lái)算才能達(dá)到最優(yōu)。線圓結(jié)構(gòu)5.211）如上圖，設(shè)A（為起點(diǎn)，B（為目標(biāo)點(diǎn)，C（和D（分別為機(jī)器人經(jīng)過拐點(diǎn)分別于隔離危險(xiǎn)線拐角小圓弧的切點(diǎn)，圓心為O（，圓的半徑為r，AB的長(zhǎng)度為a，AO的長(zhǎng)度為b

8、，BO的長(zhǎng)度為c，角度=,=,=，.求AB的長(zhǎng)度，設(shè)為L(zhǎng).解法如下：如上圖可得有以下關(guān)系：在：在中：所以：從而可得：2）而對(duì)于下圖兩種情況我們不能直接采用線圓的結(jié)構(gòu)來(lái)解決，需要做簡(jiǎn)單的變換。 情況一：線圓結(jié)構(gòu)5.22我們假設(shè)兩圓心坐標(biāo)分別為和,半徑均為r，M點(diǎn)坐標(biāo)為，那么我們很容易可以求得:這樣我們就可以利用1）中的方法，先求A到M，再求M到B，這樣分兩段就可以求解。同理如果有更多的轉(zhuǎn)彎，我們同樣可以按照此種方法分解。情況二：線圓結(jié)構(gòu)5.23這里我們依然設(shè)圓心坐標(biāo)分別為和,半徑均為r，這樣我們可以得到：那么直線方程為：因?yàn)楣芯€DE與平行，那么DE的直線方程可以表示為：其中：那么把公切線的方程

9、于圓的方程聯(lián)立，渴可以求得切點(diǎn)D和E的坐標(biāo)。這樣用D和E任意一點(diǎn)作為分割點(diǎn)都可以將上圖分割成兩個(gè)4.21所示的線圓結(jié)構(gòu)，這樣就可以對(duì)其進(jìn)行求解。同理多個(gè)這樣的轉(zhuǎn)彎時(shí)，用同樣的方法可以進(jìn)行分割。5.3 模型準(zhǔn)備二一、對(duì)于從起點(diǎn)經(jīng)過若干點(diǎn)然后再到達(dá)目標(biāo)點(diǎn)的狀況，因?yàn)椴荒茏哒劬€路徑，我們就必須考慮在經(jīng)過路徑中的一個(gè)目標(biāo)點(diǎn)時(shí)轉(zhuǎn)彎的狀況。為了研究這個(gè)問題的方便，我們先來(lái)證明一個(gè)猜想：猜想二:如果一個(gè)圓環(huán)可以繞著環(huán)上一個(gè)定點(diǎn)轉(zhuǎn)動(dòng)，那么過圓環(huán)外兩定點(diǎn)連接一根繩子，并以該圓環(huán)為支撐拉緊繩子，達(dá)到平衡狀態(tài)時(shí)，圓心與該頂點(diǎn)以及兩條切線的延長(zhǎng)線的交點(diǎn)共線。圖5.31證明猜想：如，E點(diǎn)就是圓環(huán)上的一個(gè)頂點(diǎn)，AB就是拉

10、緊的繩子，就是切線AC和BD的延長(zhǎng)線的交點(diǎn)，證明、E、三點(diǎn)共線。我們可以用力學(xué)的知識(shí)進(jìn)行證明，因?yàn)槭抢o的繩子，所以兩邊的繩子拉力相等，設(shè)為，它們的合力設(shè)為，定點(diǎn)對(duì)圓環(huán)的作用力設(shè)為。那么由幾何學(xué)的知識(shí)我們可以知道一定與共線，而又由力的平衡條件可知：=-即與共線。綜上所述、和三點(diǎn)一定共線。二、有了以上這個(gè)定理我們可以建立以下模型：如圖4.32，要求求出機(jī)器人從A繞過障礙物經(jīng)過M點(diǎn)到達(dá)目標(biāo)點(diǎn)B的最短路徑，我們采用以下方法：用一根釘子使一個(gè)圓環(huán)定在M點(diǎn)，使這個(gè)圓環(huán)能夠繞M點(diǎn)轉(zhuǎn)動(dòng)。然后連接A和B的繩子并以這些轉(zhuǎn)彎處的圓弧為支撐（這里轉(zhuǎn)彎處圓弧的半徑均按照最小轉(zhuǎn)彎半徑來(lái)計(jì)算），拉緊繩子，那么繩子的長(zhǎng)度就

11、是A到B的最短距離。我們可以把路徑圖抽象為以下的幾何圖形。下面我們對(duì)這段路徑求解：圖5.32如圖，A是起點(diǎn)，B是終點(diǎn)，和是兩個(gè)固定的圓，是一個(gè)可以繞M(p，q)點(diǎn)轉(zhuǎn)動(dòng)的圓環(huán)，三個(gè)圓的半徑均為r，C、D、E、F、G、H均為切點(diǎn)。a、b、c、e，f分別是A、A、A、的長(zhǎng)度。A、B、均是已知點(diǎn)，是未知點(diǎn)。那么最短路徑就可以表示為：L=|AC|+|DE|+|FG|+|HB|因?yàn)辄c(diǎn)的坐標(biāo)未知，所以我們就不能用模型一中的線圓結(jié)構(gòu)對(duì)其進(jìn)行求解。故得先求出點(diǎn)的坐標(biāo)。設(shè)坐標(biāo)為（m，n），、分別為（=1、2、3、4、5），、分別為、。這樣便有以下關(guān)系：在中：在中：在中：在中：則：又因?yàn)橐欢〞?huì)在的角平分線上，所以滿

12、足：我們采用向量的形式來(lái)求，易知的一個(gè)方向向量：而與垂直，故其一個(gè)方向向量：而：所以：綜合以上式子可以求得的坐標(biāo)，從而可以得出路徑的長(zhǎng)為：=+HB，這可以采用模型一中的線圓結(jié)構(gòu)來(lái)求解。5.4 模型準(zhǔn)備三求解從起點(diǎn)經(jīng)過若干個(gè)點(diǎn)再到達(dá)目標(biāo)點(diǎn)的問題，與4.4不同，我們還可以有另一種方案，即適當(dāng)擴(kuò)大障礙物拐點(diǎn)處的拐彎半徑使機(jī)器人能夠沿直線通過路徑中的目標(biāo)點(diǎn)。這樣拐點(diǎn)處拐彎圓弧的半徑和圓心都是個(gè)變量，對(duì)于該題，那么我們可以首先設(shè)定三個(gè)圓心、,然后按照以下步驟進(jìn)行作圖：1） 給定，以為圓心，為半徑，畫圓，然后過R點(diǎn)做圓的切線，切點(diǎn)為D。然后過A點(diǎn)做的切線設(shè)為，切點(diǎn)為E。2） 然后做F垂直于，垂足為F，F(xiàn)的

13、長(zhǎng)就是，然后以為圓心，為半徑畫圓。很顯然能由來(lái)確定，即。3） 然后過B點(diǎn)做的切線為，切點(diǎn)為G，再過F垂直于，垂足為H，那么H的長(zhǎng)度就是，然后以為圓心，為半徑，畫圓。很顯然能由來(lái)確定，即=。4） 過C做的切線。這就完成了由R經(jīng)過A和B在到達(dá)C的路徑。5） 然后再變換、，可得到新的路徑。找出最小者即可。5.5 模型的建立假設(shè)機(jī)器人從起點(diǎn)R到到目標(biāo)點(diǎn)，由4.2知路徑一定是由圓弧和線段組成，設(shè)有m條線段，n條圓弧。那么目標(biāo)函數(shù)可以表示為：用此模型就可以對(duì)起點(diǎn)到目標(biāo)點(diǎn)之間的路徑進(jìn)行優(yōu)化求解。六、模型的求解6.1問題一一、以下給出了R到個(gè)目標(biāo)點(diǎn)的可能路徑的最短路徑：1）如圖一，解決的就是R到目標(biāo)點(diǎn)A的最短

14、路徑問題，很顯然的一個(gè)問題是機(jī)器人從的上方走的最短路徑肯定是大于機(jī)器人從下方走的最短路徑，所以機(jī)器人從方向走的最優(yōu)路線我們?cè)趫D一中沒有給出。圖一中，藍(lán)線就可以為機(jī)器人隔出了危險(xiǎn)區(qū)域，紅線表示的就是通過點(diǎn)的圓為支撐而拉緊的繩子，這樣計(jì)算出繩子的長(zhǎng)度就是R到A的最短路徑。2）如圖二，解決的是R到目標(biāo)點(diǎn)B的最短路徑問題，圖中給出了可能的三條路徑的最短路徑（圖中的紅線所示），我們可以分別計(jì)算出三條可能路徑的最短路徑的長(zhǎng)度，然后進(jìn)行比較，取最小者就是R到目標(biāo)點(diǎn)B的最優(yōu)路徑。3)如圖三，解決的是R到目標(biāo)點(diǎn)C的最短路徑問題。圖中給出了兩條可能路徑的最短路徑（圖中的紅線所示），我們同樣可以分別計(jì)算出兩條可能的

15、最短路徑，取最小者就是R到目標(biāo)點(diǎn)C的最優(yōu)路徑。圖6.12圖6.13二、 然后用matlab求解結(jié)果如下：1)2)R到目標(biāo)點(diǎn)B的可能路徑有三條，即就有三條可能的最短路徑。 而機(jī)器人經(jīng)過中間一條路徑到達(dá)B,這條路徑由三條線段和兩段圓弧組成，直接用三中的解法是結(jié)不出來(lái)的。于是我們做了如下變換，先求出中間一條直線的中點(diǎn)設(shè)為F，那么可以采用三中的解法，分別求R到F和F到B的最短路徑，然后兩段相加，便可求出R到B的最短路徑。求解結(jié)果為 機(jī)器人經(jīng)過最下邊一條路徑，同理這條路徑由四條直線和三個(gè)圓弧組成，同樣可以采取中的變換，分三部分求解。求解結(jié)果如下為綜合所述，R到目標(biāo)點(diǎn)B的最短路徑為3）R到目標(biāo)點(diǎn)C的可能路

16、徑由兩條，和2中的方法一樣，最終求解結(jié)果R到目標(biāo)點(diǎn)C的最短路徑為6.2問題二 一、我們先按照4.3中的思想來(lái)進(jìn)行求解，這樣我們可以做出5.21所示的示意圖：圖6.21二、我們?cè)诓捎媚Ｐ蜏?zhǔn)備三中的算法進(jìn)行求解，可以畫出5.22所示的示意圖：顯然運(yùn)用模型準(zhǔn)備二中的方法求解的結(jié)果小于用模型準(zhǔn)備三中的方法求解的結(jié)果，說(shuō)明模型準(zhǔn)備二的方法優(yōu)于模型準(zhǔn)備三的方法。七、模型推廣7.1 問題深入分析在本題中只有四個(gè)障礙物，按照線圓結(jié)構(gòu)畫出從起點(diǎn)到達(dá)目標(biāo)點(diǎn)的路徑是有限的，我們完全可以采用窮舉法把這些路徑列出來(lái)，然后比較大小取最小者即可，但是我們可以設(shè)想如果這個(gè)區(qū)域內(nèi)有n個(gè)障礙物，那么按照線圓結(jié)構(gòu)從起點(diǎn)到達(dá)目標(biāo)點(diǎn)的

17、可能路徑就有無(wú)數(shù)多條，這時(shí)我們?nèi)绻诓捎酶F舉法是不現(xiàn)實(shí)的。所以我們必須尋求新的算法來(lái)解決這個(gè)問題。中的，給這些定點(diǎn)賦一個(gè)等于切線長(zhǎng)度的權(quán)值，如果某兩條切線有一個(gè)公切圓弧，則代表這兩條曲線的頂點(diǎn)是一條直線的兩個(gè)端點(diǎn)，邊上的權(quán)值等于這兩條切線之間的劣弧長(zhǎng)度。然后在這張圖中加一個(gè)源點(diǎn)和終點(diǎn)，那么在所有代表出發(fā)點(diǎn)與其它圓弧之間切線的頂點(diǎn)與源點(diǎn)連成一條邊，權(quán)值均為0，同理在所有代表目標(biāo)點(diǎn)到其它圓弧切線的頂點(diǎn)與終點(diǎn)連成一條邊，權(quán)值均為0，這樣題目就轉(zhuǎn)化成了求源點(diǎn)到達(dá)終點(diǎn)之間的最短路徑問題了，這里最短路徑就是指經(jīng)過所有頂點(diǎn)與邊的權(quán)值之和最小。我們可以采用Dijkstra算法進(jìn)行求解。7.2模型的進(jìn)一步求解根

18、據(jù)6.1的分析，在有若干個(gè)障礙物的區(qū)域中，我們把按照線圓結(jié)構(gòu)畫出從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的路徑圖依據(jù)6.1中的想法轉(zhuǎn)換成了下面這張圖，圖中的A和G點(diǎn)就是添加的源點(diǎn)和終點(diǎn)，其它節(jié)點(diǎn)均是出發(fā)點(diǎn)和目標(biāo)點(diǎn)到圓弧的切線和圓弧與圓弧之間的切線轉(zhuǎn)化而成。圖7.21對(duì)于最短路徑的求解，有以下步驟：1）我們畫出出發(fā)點(diǎn)和目標(biāo)點(diǎn)和各個(gè)圓弧的切線，以及圓弧與圓弧之間的切線，但是切線有可能經(jīng)過障礙物的內(nèi)部或危險(xiǎn)區(qū)域，也可能出現(xiàn)切線重復(fù)的狀況，既有很多不合法的切線。于是我們對(duì)模型做了以下修正：1、 檢驗(yàn)切線兩個(gè)端點(diǎn)是否在障礙物內(nèi)部。2、 檢驗(yàn)切線是否障礙物的對(duì)角線相交。3、 檢驗(yàn)圓弧所對(duì)應(yīng)的圓心，即障礙物的頂點(diǎn)到切線的距離是否小

19、于1。如果以上三種情況滿足其一，我們規(guī)定對(duì)應(yīng)這段切線的頂點(diǎn)為M（M為無(wú)窮大）。4、 另外還有如下圖所示的一種特殊情況：兩個(gè)大小相同在同一水平或者豎直位置上，不考慮切線滿足1、2、3的狀況它們由2條內(nèi)公切線，8條外公切線，但是有6條外公切線是重復(fù)的。因此我們作如下規(guī)定:如果某條切線與某段圓弧相切，且切點(diǎn)不在切線的端點(diǎn)上，則該切線為不合法。權(quán)值矩陣中表示它的頂點(diǎn)也為M。圖7.222） 然后把合法的切線與這些切線之間的劣弧轉(zhuǎn)化成如7.21所示的形式。假設(shè)轉(zhuǎn)化過后有m條合法切線，那么就有m個(gè)頂點(diǎn)，設(shè)這些點(diǎn)的權(quán)值（），即第條合法曲線的長(zhǎng)度。為邊的權(quán)值，即第條弧的長(zhǎng)度。3）然后把路徑圖轉(zhuǎn)化成如圖6.21所

20、示，按照求得權(quán)值矩陣給圖中的頂點(diǎn)及邊長(zhǎng)賦值。4）最后依據(jù)Dijkstra算法求得最短路徑。八、模型評(píng)價(jià)一、模型優(yōu)點(diǎn)1、運(yùn)用多個(gè)方案對(duì)路徑進(jìn)行優(yōu)化，在相對(duì)優(yōu)化之中取得最優(yōu)解。2、模型優(yōu)化后用解析幾何進(jìn)行求解，精確度較高。3、模型簡(jiǎn)單易懂，便于實(shí)際檢驗(yàn)及應(yīng)用。二、模型缺陷 1、此模型適于全局規(guī)劃，獲得精確解卻失去了效率。2、在障礙物較多時(shí)，且形狀不規(guī)則時(shí)，模型需要進(jìn)一步改進(jìn)。九、參考文獻(xiàn)1譚永基，數(shù)學(xué)模型，上海，復(fù)旦大學(xué)出版社，20112邦迪，圖論及其應(yīng)用，西安，西安科學(xué)出版社 19843胡海星，RPG游戲中精靈的移動(dòng)問題，雜志程序員 2011；4尤承業(yè)，解析幾何，北京，北京大學(xué)出版社，20045

21、周培德，計(jì)算幾何算法與設(shè)計(jì)，北京清華大學(xué)出版社，2005十、附錄1）%求解一次轉(zhuǎn)彎所經(jīng)路線總長(zhǎng)%T：初始點(diǎn) V:轉(zhuǎn)彎圓弧圓心 W:到達(dá)點(diǎn) function result=zongchang(T,W,V,r)TV=sqrt(T(1)-V(1)2+(T(2)-V(2)2);TW=sqrt(T(1)-W(1)2+(T(2)-W(2)2);VW=sqrt(V(1)-W(1)2+(V(2)-W(2)2);alpha1=acos(TV2+VW2-TW2)/(2*TV*VW);alpha2=acos(r/TV);alpha3=acos(r/VW);alpha4=2*pi-alpha1-alpha2-alpha3;%alpha4為轉(zhuǎn)彎圓心角TS1=sqrt(TV2-r2);%TS1,TS2均為圓弧切線%S2W=sqrt(VW2-r2);S1S2hu=r*alpha4;result=TS1+S1S2hu+S2W;2）%判定是否經(jīng)過路障,采用跨立實(shí)驗(yàn)（計(jì)算幾何算法）function m=intersect(H1,H2,G1,G2)if min(H1(1),H2(1)<=max(