欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

詳解js實現(xiàn)線段交點的三種算法

 更新時間:2016年08月09日 09:52:58   投稿:daisy  
下面小編就最近學會的一些”求線段交點”的算法說一說, 希望對大家有所幫助?!扒缶€段交點”是一種非?;A的幾何計算, 在很多游戲中都會被使用到。有需要的可以參考學習

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

引用

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

算法一: 求兩條線段所在直線的交點, 再判斷交點是否在兩條線段上.

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

然后根據(jù)交點的與線段端點的位置關系來判斷交點是否在線段上.

公式如下圖:

<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>

算法一思路比較清晰易懂, 但是性能并不高. 因為它在不確定交點是否有效(在線段上)之前, 就先去計算了交點, 耗費了較多的時間.

如果最后發(fā)現(xiàn)交點無效, 那么之前的計算就白折騰了. 而且整個計算的過程也很復雜.

那么有沒有一種思路,可以讓我們先判斷是否存在有效交點,然后再去計算它呢?

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

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

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

求出線段的法線向量, 然后把點投影到法線上, 最后根據(jù)投影的位置來判斷點和線段的關系.

見下圖

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

主要用來做參考.

圖中點a投影和點b投影在點c投影的兩側(cè), 說明線段ab的端點在線段cd的兩側(cè).

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

求法線 , 求投影 什么的聽起來很復雜的樣子, 實際上對于我來說也確實挺復雜,在幾個月前我也不會(念書那會兒的幾何知識都忘光了 :'( )'

不過好在學習和實現(xiàn)起來還不算復雜, 皆有公式可循

求線段ab的法線:

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

注意: 其中 normalLine.xnormalLine.y的幾何意義表示法線的方向, 而不是坐標.

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

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

注意: 這里的"投影位置"是一個標量, 表示的是到法線原點的距離, 而不是投影點的坐標.

通常知道這個距離就足夠了.

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

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

       distA==distB!=distC 時, 兩條線段平行

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

       distA 和 distB 在distC 異側(cè)時, 兩條線段是否相交需要再判斷點c點d與線段ab的關系.

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

求交點的過程后面再說, 先看一下該算法的完整實現(xiàn) :

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); 
 
 //兩條法線做叉乘, 如果結(jié)果為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投影同側(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 }; 
}

最后 求交點坐標的部分 所用的方法看起來有點奇怪, 有種摸不著頭腦的感覺.

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

換句話說, 算法二里求交點坐標的部分 其實也是用的直線的線性方程組來做的.

現(xiàn)在來簡單粗略 很不科學的對比一下算法一和算法二:

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

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

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

實際測試下來, 實際情況也確實如此.

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

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

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

所謂算法三, 其實只是對算法二的一個改良, 改良的地方主要就是 :

不通過法線投影來判斷點和線段的位置關系, 而是通過點和線段構(gòu)成的三角形面積來判斷.

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

因為 兩向量叉乘==兩向量構(gòu)成的平行四邊形(以兩向量為鄰邊)的面積 , 所以上面的公式也不難理解.

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

改良算法關鍵點就是:

如果”線段ab和點c構(gòu)成的三角形面積”與”線段ab和點d構(gòu)成的三角形面積” 構(gòu)成的三角形面積的正負符號相異,

那么點c和點d位于線段ab兩側(cè).

 如下圖所示:


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

下面還是先看代碼:

由于我們只要判斷符號即可, 所以前面的三角形面積公式我們就不需要后面的 除以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); 
 
 // 面積符號相同則兩點在線段同側(cè),不相交 (對點在線段上的情況,本例當作不相交處理); 
 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倍 
 // 注意: 這里有一個小優(yōu)化.不需要再用公式計算面積,而是通過已知的三個面積加減得出. 
 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 }; 
 
}

最后 計算交點坐標的部分 和算法二同理.

算法三在算法二的基礎上, 大大簡化了計算步驟, 代碼也更精簡. 可以說,是三種算法里, 最好的.實際測試結(jié)果也是如此.

當然必須坦誠的來說, 在Javascript里, 對于普通的計算, 三種算法的時間復雜度其實是差不多的(尤其是V8引擎下).
我的測試用例里也是進行變態(tài)的百萬次級別的線段相交測試 才能拉開三種算法之間的差距.

總結(jié)

不過本著精益求精 以及學習的態(tài)度而言, 追求一個更好的算法, 總是有其積極意義的。以上就是利用js實現(xiàn)線段交點的幾種算法,內(nèi)容不是很深奧,希望對大家學習js有所幫助。

相關文章

  • js操作XML文件的實現(xiàn)方法兼容IE與FireFox

    js操作XML文件的實現(xiàn)方法兼容IE與FireFox

    下面小編就為大家?guī)硪黄猨s操作XML文件的實現(xiàn)方法兼容IE與FireFox。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-06-06
  • JavaScript如何調(diào)試有哪些建議和技巧附五款有用的調(diào)試工具

    JavaScript如何調(diào)試有哪些建議和技巧附五款有用的調(diào)試工具

    這篇文章給大家介紹javascript如何調(diào)試有哪些建議和技巧,涉及到javascript調(diào)試方法相關知識,對javascript調(diào)試方法感興趣的朋友可以參考下本篇文章
    2015-10-10
  • Webpack?ECMAScript?模塊詳解

    Webpack?ECMAScript?模塊詳解

    ECMAScript 模塊(ESM)是在 Web 中使用模塊的規(guī)范, 所有現(xiàn)代瀏覽器均支持此功能,同時也是在 Web 中編寫模塊化代碼的推薦方式,這篇文章主要介紹了Webpack?ECMAScript?模塊,需要的朋友可以參考下
    2023-12-12
  • Javascript 實現(xiàn)放大鏡效果實例詳解

    Javascript 實現(xiàn)放大鏡效果實例詳解

    這篇文章主要介紹了Javascript 實現(xiàn)放大鏡效果實例詳解的相關資料,這里附有實現(xiàn)實例代碼,具有參考價值,需要的朋友可以參考下
    2016-12-12
  • JavaScript內(nèi)存管理與閉包實例詳解

    JavaScript內(nèi)存管理與閉包實例詳解

    不管什么樣的編程語言,在代碼的執(zhí)行過程中都是需要給它分配內(nèi)存的,下面這篇文章主要給大家介紹了關于JavaScript內(nèi)存管理與閉包的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下
    2022-06-06
  • JS性能優(yōu)化實現(xiàn)方法及優(yōu)點進行

    JS性能優(yōu)化實現(xiàn)方法及優(yōu)點進行

    這篇文章主要介紹了JS性能優(yōu)化實現(xiàn)方法及優(yōu)點進行,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2020-08-08
  • JS實現(xiàn)時間選擇器

    JS實現(xiàn)時間選擇器

    這篇文章主要為大家詳細介紹了JS實現(xiàn)時間選擇器,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-07-07
  • JS中eval函數(shù)的使用示例

    JS中eval函數(shù)的使用示例

    eval函數(shù)會將 obj 當做代碼去執(zhí)行一遍,下面舉個例子為大家詳細介紹下具體的使用方法,感興趣的朋友可以參考下哈,希望對大家有所幫助
    2013-07-07
  • 詳解微信小程序開發(fā)聊天室—實時聊天,支持圖片預覽

    詳解微信小程序開發(fā)聊天室—實時聊天,支持圖片預覽

    這篇文章主要介紹了微信小程序?qū)崟r聊天支持圖片預覽,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2019-05-05
  • 使用JS實現(xiàn)簡單的圖片切換功能

    使用JS實現(xiàn)簡單的圖片切換功能

    這篇文章主要為大家詳細介紹了使用JS實現(xiàn)簡單的圖片切換功能,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-07-07

最新評論