本文講的內(nèi)容都很初級(jí), 主要是面向和我一樣的初學(xué)者, 所以請(qǐng)各位算法帝們輕拍啊

引用

已知線(xiàn)段1(a,b) 和線(xiàn)段2(c,d) ,其中a b c d為端點(diǎn), 求線(xiàn)段交點(diǎn)p .(平行或共線(xiàn)視作不相交)

算法一: 求兩條線(xiàn)段所在直線(xiàn)的交點(diǎn), 再判斷交點(diǎn)是否在兩條線(xiàn)段上.

求直線(xiàn)交點(diǎn)時(shí) 我們可通過(guò)直線(xiàn)的一般方程 ax+by+c=0 求得(方程中的abc為系數(shù),不是前面提到的端點(diǎn),另外也可用點(diǎn)斜式方程和斜截式方程,此處暫且不論).

然后根據(jù)交點(diǎn)的與線(xiàn)段端點(diǎn)的位置關(guān)系來(lái)判斷交點(diǎn)是否在線(xiàn)段上.

公式如下圖:

<code class="hljs avrasm">function segmentsIntr(a, b, c, d){ 
 
/** 1 解線(xiàn)性方程組, 求線(xiàn)段交點(diǎn). **/ 
// 如果分母為0 則平行或共線(xiàn), 不相交 
 var denominator = (b.y - a.y)*(d.x - c.x) - (a.x - b.x)*(c.y - d.y); 
 if (denominator==0) { 
 return false; 
 } 
 
// 線(xiàn)段所在直線(xiàn)的交點(diǎn)坐標(biāo) (x , y) 
 var x = ( (b.x - a.x) * (d.x - c.x) * (c.y - a.y) 
  + (b.y - a.y) * (d.x - c.x) * a.x 
  - (d.y - c.y) * (b.x - a.x) * c.x ) / denominator ; 
 var y = -( (b.y - a.y) * (d.y - c.y) * (c.x - a.x) 
  + (b.x - a.x) * (d.y - c.y) * a.y 
  - (d.x - c.x) * (b.y - a.y) * c.y ) / denominator; 
 
/** 2 判斷交點(diǎn)是否在兩條線(xiàn)段上 **/ 
 if ( 
 // 交點(diǎn)在線(xiàn)段1上 
 (x - a.x) * (x - b.x) <= 0 && (y - a.y) * (y - b.y) <= 0 
 // 且交點(diǎn)也在線(xiàn)段2上 
  && (x - c.x) * (x - d.x) <= 0 && (y - c.y) * (y - d.y) <= 0 
 ){ 
 
 // 返回交點(diǎn)p 
 return { 
  x : x, 
  y : y 
  } 
 } 
 //否則不相交 
 return false 
 
} </code>

算法一思路比較清晰易懂, 但是性能并不高. 因?yàn)樗诓淮_定交點(diǎn)是否有效(在線(xiàn)段上)之前, 就先去計(jì)算了交點(diǎn), 耗費(fèi)了較多的時(shí)間.

如果最后發(fā)現(xiàn)交點(diǎn)無(wú)效, 那么之前的計(jì)算就白折騰了. 而且整個(gè)計(jì)算的過(guò)程也很復(fù)雜.

那么有沒(méi)有一種思路,可以讓我們先判斷是否存在有效交點(diǎn),然后再去計(jì)算它呢?

顯然答案是肯定的. 于是就有了后面的一些算法.

算法二: 判斷每一條線(xiàn)段的兩個(gè)端點(diǎn)是否都在另一條線(xiàn)段的兩側(cè), 是則求出兩條線(xiàn)段所在直線(xiàn)的交點(diǎn), 否則不相交.

第一步判斷兩個(gè)點(diǎn)是否在某條線(xiàn)段的兩側(cè), 通?？刹捎猛队胺?

求出線(xiàn)段的法線(xiàn)向量, 然后把點(diǎn)投影到法線(xiàn)上, 最后根據(jù)投影的位置來(lái)判斷點(diǎn)和線(xiàn)段的關(guān)系.

見(jiàn)下圖

點(diǎn)a和點(diǎn)b在線(xiàn)段cd法線(xiàn)上的投影如圖所示, 這時(shí)候我們還要做一次線(xiàn)段cd在自己法線(xiàn)上的投影(選擇點(diǎn)c或點(diǎn)d中的一個(gè)即可).

主要用來(lái)做參考.

圖中點(diǎn)a投影和點(diǎn)b投影在點(diǎn)c投影的兩側(cè), 說(shuō)明線(xiàn)段ab的端點(diǎn)在線(xiàn)段cd的兩側(cè).

同理, 再判斷一次cd是否在線(xiàn)段ab兩側(cè)即可.

求法線(xiàn) , 求投影 什么的聽(tīng)起來(lái)很復(fù)雜的樣子, 實(shí)際上對(duì)于我來(lái)說(shuō)也確實(shí)挺復(fù)雜,在幾個(gè)月前我也不會(huì)(念書(shū)那會(huì)兒的幾何知識(shí)都忘光了 :'( )'

不過(guò)好在學(xué)習(xí)和實(shí)現(xiàn)起來(lái)還不算復(fù)雜, 皆有公式可循

求線(xiàn)段ab的法線(xiàn):

var nx=b.y - a.y, 
 ny=a.x - b.x; 
var normalLine = { x: nx, y: ny };

注意: 其中 normalLine.x和normalLine.y的幾何意義表示法線(xiàn)的方向, 而不是坐標(biāo).

求點(diǎn)c在法線(xiàn)上的投影位置:

var dist= normalLine.x*c.x + normalLine.y*c.y; 

注意: 這里的"投影位置"是一個(gè)標(biāo)量, 表示的是到法線(xiàn)原點(diǎn)的距離, 而不是投影點(diǎn)的坐標(biāo).

通常知道這個(gè)距離就足夠了.

當(dāng)我們把圖中 點(diǎn)a投影(distA),點(diǎn)b投影(distB),點(diǎn)c投影(distC) 都求出來(lái)之后, 就可以很容易的根據(jù)各自的大小判斷出相對(duì)位置.

       distA==distB==distC 時(shí), 兩條線(xiàn)段共線(xiàn)

       distA==distB!=distC 時(shí), 兩條線(xiàn)段平行

       distA 和 distB 在distC 同側(cè)時(shí), 兩條線(xiàn)段不相交.

       distA 和 distB 在distC 異側(cè)時(shí), 兩條線(xiàn)段是否相交需要再判斷點(diǎn)c點(diǎn)d與線(xiàn)段ab的關(guān)系.

前面的那些步驟, 只是實(shí)現(xiàn)了"判斷線(xiàn)段是否相交", 當(dāng)結(jié)果為true時(shí), 我們還需要進(jìn)一步求交點(diǎn).

求交點(diǎn)的過(guò)程后面再說(shuō), 先看一下該算法的完整實(shí)現(xiàn) :

function segmentsIntr(a, b, c, d){ 
 
 //線(xiàn)段ab的法線(xiàn)N1 
 var nx1 = (b.y - a.y), ny1 = (a.x - b.x); 
 
 //線(xiàn)段cd的法線(xiàn)N2 
 var nx2 = (d.y - c.y), ny2 = (c.x - d.x); 
 
 //兩條法線(xiàn)做叉乘, 如果結(jié)果為0, 說(shuō)明線(xiàn)段ab和線(xiàn)段cd平行或共線(xiàn),不相交 
 var denominator = nx1*ny2 - ny1*nx2; 
 if (denominator==0) { 
 return false; 
 } 
 
 //在法線(xiàn)N2上的投影 
 var distC_N2=nx2 * c.x + ny2 * c.y; 
 var distA_N2=nx2 * a.x + ny2 * a.y-distC_N2; 
 var distB_N2=nx2 * b.x + ny2 * b.y-distC_N2; 
 
 // 點(diǎn)a投影和點(diǎn)b投影在點(diǎn)c投影同側(cè) (對(duì)點(diǎn)在線(xiàn)段上的情況,本例當(dāng)作不相交處理); 
 if ( distA_N2*distB_N2>=0 ) { 
 return false; 
 } 
 
 // 
 //判斷點(diǎn)c點(diǎn)d 和線(xiàn)段ab的關(guān)系, 原理同上 
 // 
 //在法線(xiàn)N1上的投影 
 var distA_N1=nx1 * a.x + ny1 * a.y; 
 var distC_N1=nx1 * c.x + ny1 * c.y-distA_N1; 
 var distD_N1=nx1 * d.x + ny1 * d.y-distA_N1; 
 if ( distC_N1*distD_N1>=0 ) { 
 return false; 
 } 
 
 //計(jì)算交點(diǎn)坐標(biāo) 
 var fraction= distA_N2 / denominator; 
 var dx= fraction * ny1, 
 dy= -fraction * nx1; 
 return { x: a.x + dx , y: a.y + dy }; 
}

最后 求交點(diǎn)坐標(biāo)的部分 所用的方法看起來(lái)有點(diǎn)奇怪, 有種摸不著頭腦的感覺(jué).

其實(shí)它和算法一 里面的算法是類(lèi)似的,只是里面的很多計(jì)算項(xiàng)已經(jīng)被提前計(jì)算好了.

換句話(huà)說(shuō), 算法二里求交點(diǎn)坐標(biāo)的部分 其實(shí)也是用的直線(xiàn)的線(xiàn)性方程組來(lái)做的.

現(xiàn)在來(lái)簡(jiǎn)單粗略 很不科學(xué)的對(duì)比一下算法一和算法二:

      1、最好情況下, 兩種算法的復(fù)雜度相同

      2、最壞情況, 算法一和算法二的計(jì)算量差不多

      3、但是算法二提供了 更多的”提前結(jié)束條件”,所以平均情況下,應(yīng)該算法二更優(yōu).

實(shí)際測(cè)試下來(lái), 實(shí)際情況也確實(shí)如此.

前面的兩種算法基本上是比較常見(jiàn)的可以應(yīng)付絕大多數(shù)情況. 但是事實(shí)上還有一種更好的算法.
這也是我最近才新學(xué)會(huì)的(我現(xiàn)學(xué)現(xiàn)賣(mài)了,大家不要介意啊…)

算法三: 判斷每一條線(xiàn)段的兩個(gè)端點(diǎn)是否都在另一條線(xiàn)段的兩側(cè), 是則求出兩條線(xiàn)段所在直線(xiàn)的交點(diǎn), 否則不相交.

(咦? 怎么感覺(jué)和算法二一樣啊? 不要懷疑 確實(shí)一樣 … 囧)

所謂算法三, 其實(shí)只是對(duì)算法二的一個(gè)改良, 改良的地方主要就是 :

不通過(guò)法線(xiàn)投影來(lái)判斷點(diǎn)和線(xiàn)段的位置關(guān)系, 而是通過(guò)點(diǎn)和線(xiàn)段構(gòu)成的三角形面積來(lái)判斷.

先來(lái)復(fù)習(xí)下三角形面積公式: 已知三角形三點(diǎn)a(x,y) b(x,y) c(x,y), 三角形面積為:

<code class="hljs avrasm">var triArea=( (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x) ) /2 ; </code>

因?yàn)?兩向量叉乘==兩向量構(gòu)成的平行四邊形(以?xún)上蛄繛猷忂?的面積 , 所以上面的公式也不難理解.

而且由于向量是有方向的, 所以面積也是有方向的, 通常我們以逆時(shí)針為正, 順時(shí)針為負(fù)數(shù).

改良算法關(guān)鍵點(diǎn)就是:

如果”線(xiàn)段ab和點(diǎn)c構(gòu)成的三角形面積”與”線(xiàn)段ab和點(diǎn)d構(gòu)成的三角形面積” 構(gòu)成的三角形面積的正負(fù)符號(hào)相異,

那么點(diǎn)c和點(diǎn)d位于線(xiàn)段ab兩側(cè).

 如下圖所示:

圖中虛線(xiàn)所示的三角形, 纏繞方向(三邊的定義順序)不同, 所以面積的正負(fù)符號(hào)不同.

下面還是先看代碼:

由于我們只要判斷符號(hào)即可, 所以前面的三角形面積公式我們就不需要后面的 除以2 了.

function segmentsIntr(a, b, c, d){ 
 
 // 三角形abc 面積的2倍 
 var area_abc = (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x); 
 
 // 三角形abd 面積的2倍 
 var area_abd = (a.x - d.x) * (b.y - d.y) - (a.y - d.y) * (b.x - d.x); 
 
 // 面積符號(hào)相同則兩點(diǎn)在線(xiàn)段同側(cè),不相交 (對(duì)點(diǎn)在線(xiàn)段上的情況,本例當(dāng)作不相交處理); 
 if ( area_abc*area_abd>=0 ) { 
 return false; 
 } 
 
 // 三角形cda 面積的2倍 
 var area_cda = (c.x - a.x) * (d.y - a.y) - (c.y - a.y) * (d.x - a.x); 
 // 三角形cdb 面積的2倍 
 // 注意: 這里有一個(gè)小優(yōu)化.不需要再用公式計(jì)算面積,而是通過(guò)已知的三個(gè)面積加減得出. 
 var area_cdb = area_cda + area_abc - area_abd ; 
 if ( area_cda * area_cdb >= 0 ) { 
 return false; 
 } 
 
 //計(jì)算交點(diǎn)坐標(biāo) 
 var t = area_cda / ( area_abd- area_abc ); 
 var dx= t*(b.x - a.x), 
 dy= t*(b.y - a.y); 
 return { x: a.x + dx , y: a.y + dy }; 
 
}

最后 計(jì)算交點(diǎn)坐標(biāo)的部分 和算法二同理.

算法三在算法二的基礎(chǔ)上, 大大簡(jiǎn)化了計(jì)算步驟, 代碼也更精簡(jiǎn). 可以說(shuō),是三種算法里, 最好的.實(shí)際測(cè)試結(jié)果也是如此.

當(dāng)然必須坦誠(chéng)的來(lái)說(shuō), 在Javascript里, 對(duì)于普通的計(jì)算, 三種算法的時(shí)間復(fù)雜度其實(shí)是差不多的(尤其是V8引擎下).
我的測(cè)試用例里也是進(jìn)行變態(tài)的百萬(wàn)次級(jí)別的線(xiàn)段相交測(cè)試 才能拉開(kāi)三種算法之間的差距.

總結(jié)

不過(guò)本著精益求精 以及學(xué)習(xí)的態(tài)度而言, 追求一個(gè)更好的算法, 總是有其積極意義的。以上就是利用js實(shí)現(xiàn)線(xiàn)段交點(diǎn)的幾種算法，內(nèi)容不是很深?yuàn)W，希望對(duì)大家學(xué)習(xí)js有所幫助。

最新評(píng)論