DIV CSS 佈局教程網

詳解 JS 求線段交點的三種實現思路
編輯:關於JavaScript     

這篇筆記主要寫給和我一樣剛入門的同學,內容偏基礎,歡迎各路高手多多包涵、不吝指正。

問題描述

已知線段一(端點 a、b)與線段二(端點 c、d),求兩線段的交點 p。約定:平行或共線的情況一律視為不相交。

算法一:先求所在直線交點,再判斷是否落在線段上

思路很直白:先算出兩條線段各自所在直線的交點,再檢驗這個交點是否同時落在兩條線段之內。

求直線交點可以借助直線的一般式方程 ax + by + c = 0(此處的 a、b、c 是方程係數,並非前面的端點;點斜式、斜截式同樣可行,這裡暫不展開),再結合交點與線段端點的位置關係判斷交點是否有效。

公式如下圖:

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

這種做法邏輯清晰、容易理解,但性能並不理想:它在還不確定交點是否有效之前,就先花力氣把交點算了出來。萬一最後發現交點根本不在線段上,前面的計算就全白做了,而且整個過程也偏繁瑣。

那麼,有沒有一種思路能讓我們「先判斷是否存在有效交點,確認存在後再去計算」呢?答案是肯定的,於是便有了下面的改進方案。

算法二:先用投影法判斷相對於線段的兩側關係,再求交點

核心判據是:檢查每一條線段的兩個端點是否都落在另一條線段的兩側。若是,則兩線段所在直線相交,進而求出交點;否則不相交。

判斷「兩點是否位於某條線段兩側」,常用投影法:先求出線段的法線向量,再把點投影到法線上,最後依據投影位置判斷點與線段的相對關係。

見下圖

圖中點 a、點 b 在線段 cd 法線上的投影已標出。此時還需要把線段 cd 自身也投影到它的法線上(取 c 或 d 其一即可)作為參照基準。

可以看到,點 a 的投影與點 b 的投影分列於點 c 投影的兩側,這說明線段 ab 的端點位於線段 cd 兩側。同理,再判斷一次 cd 是否位於 ab 兩側即可。

「求法線、求投影」聽上去頗唬人,坦白說對我而言幾個月前也確實一頭霧水(學生時代的幾何知識早還給老師了)。好在動手實現起來並不算難,都有現成公式可循。

求線段 ab 的法線:

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

注意:此處 normalLine.x 與 normalLine.y 的幾何含義是法線的方向,而非某個坐標。

求點 c 在法線上的投影位置:

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

注意:這裡的「投影位置」是一個標量,表示到法線原點的距離,而不是投影點的坐標。通常掌握這個距離就已足夠。

把點 a、b、c 的投影值 distA、distB、distC 都算出來後,就能依據三者大小輕鬆判斷相對位置:

    distA == distB == distC 時,兩線段共線

    distA == distB ≠ distC 時,兩線段平行

    distA 與 distB 位於 distC 同側時,兩線段不相交

    distA 與 distB 位於 distC 異側時,是否相交還需再判斷點 c、d 與線段 ab 的關係

以上步驟只解決了「是否相交」的判定;當結果為真時,我們還要進一步求出交點。求交點的部分稍後再說,先看看完整實現:

 function segmentsIntr(a, b, c, d){ //線段ab的法線N1 var nx1 = (b.y - a.y), ny1 = (a.x - b.x); //線段cd的法線N2 var nx2 = (d.y - c.y), ny2 = (c.x - d.x); //兩條法線做叉乘, 如果結果為0, 說明線段ab和線段cd平行或共線,不相交 var denominator = nx1*ny2 - ny1*nx2; if (denominator==0) { return false; } //在法線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; // 點a投影和點b投影在點c投影同側 (對點在線段上的情況,本例當作不相交處理); if ( distA_N2*distB_N2>=0 ) { return false; } // //判斷點c點d 和線段ab的關系, 原理同上 // //在法線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; } //計算交點坐標 var fraction= distA_N2 / denominator; var dx= fraction * ny1, dy= -fraction * nx1; return { x: a.x + dx , y: a.y + dy }; }

最後求交點坐標的那段乍看有些摸不著頭腦,其實它與算法一的思路同源,只是很多中間項在前面已經算好了——本質上仍是借助直線的線性方程組求解。

粗略、很不嚴謹地對比一下算法一與算法二:

    1、最好情況下,兩者複雜度相同;

    2、最壞情況下,兩者計算量也差不多;

    3、但算法二提供了更多「提前結束」的條件,因此平均下來算法二更佔優。實際測試也印證了這一點。

前兩種算法基本能應付絕大多數場景,但其實還存在一種更優的做法,這也是我最近才學會、現學現賣的。

算法三:同樣判斷端點是否分居兩側,但改用三角形面積來判斷

(咦?這描述怎麼和算法二一樣?別懷疑,判斷目標確實一樣……)

算法三本質上是對算法二的一次改良,改良之處在於:不再借助法線投影來判斷點與線段的位置關係,而是改用「點與線段構成的三角形面積」來判斷。

先複習三角形面積公式:已知三點 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>

由於兩向量叉乘等於以它們為鄰邊的平行四邊形面積,這個公式便不難理解。又因向量有方向,面積也就帶上了正負:通常規定逆時針為正、順時針為負。

改良算法的關鍵在於:

若「線段 ab 與點 c 構成的三角形面積」和「線段 ab 與點 d 構成的三角形面積」正負符號相反,

則說明點 c 與點 d 位於線段 ab 的兩側。

如下圖所示:


圖中虛線三角形的繞行方向(三邊的定義順序)不同,因此面積的正負符號也不同。

下面還是先看代碼:

由於只需判斷符號,三角形面積公式後面的「除以 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); // 面積符號相同則兩點在線段同側,不相交 (對點在線段上的情況,本例當作不相交處理); 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倍 // 注意: 這裡有一個小優化.不需要再用公式計算面積,而是通過已知的三個面積加減得出. var area_cdb = area_cda + area_abc - area_abd ; if ( area_cda * area_cdb >= 0 ) { return false; } //計算交點坐標 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 }; }

最後求交點坐標的部分與算法二同理。

算法三在算法二的基礎上大幅簡化了計算步驟,代碼也更精煉,可謂三者之中最優,實測結果亦是如此。

當然也必須坦誠地說:在 JavaScript 裡,就普通規模的計算而言,三種算法的時間複雜度其實相差無幾(尤其在 V8 引擎下)。只有在進行變態級別的百萬次線段相交測試時,才能把三者的差距真正拉開。

總結

本著精益求精與學習的態度,追求更好的算法總有其積極意義。以上就是 JS 求線段交點的幾種實現思路,內容並不深奧,希望能對大家學習 JS 有所幫助。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved