2025-02-09

 

在圖形編程中,經常需要檢測兩個線段是否相交,例如,不規則圖形的碰撞檢測,檢測線段的碰撞時基礎.

 

線段不是直線,計算起來會麻煩一點,而且有很多種方法,這裡就介紹一種向量法的解法.

 

如何檢測兩條線段是相交的呢?首先需要四個點p1,p2,p3,p4,其中p1和p2表示一條線段,p3和p4表示第二條線段.

 

然後,推導,如果兩條線段相交,那麼對於第一條線段來說(由p1和p2為端點)p3和p4必然是分別在它兩邊的.同時,對於第二條線段來說(由p3和p4為端點),p1和p2也必然是在第二條線段的兩邊的.反過來,要證明兩條線段相交,隻需要證明後面的兩個條件即可,這是一個充分必要條件.

 

那麼如何證明兩個點分別在一條直線的兩邊呢?用向量法,看圖:

 

 

圖中,p1,p2,p3,p4對應四個點,表示兩條綠色的線段,我們先用線段p3->p4為基準線,判斷p1和p2是否在它的兩邊.

 

如圖,根據四個點,建立三個向量,v1,v2,v3,方向在圖中已經標示清楚.

 

要判斷p1和p2是否在線段的兩側,需要先計算v1×v3和v2×v3的值,這裡涉及到向量的乘法,這裡用到的是叉乘,

 

向量a和向量b叉乘得出來的結果是一個和向量a,向量b組成的平面垂直方向的一個向量,它的值有正負之分.

 

這裡,我們利用叉乘得出來的結果來指導夾角的方向, v1×v3和v2×v3兩個結果如果是同號的,就說明,兩個點在線段的同一側,如果是異號的,說明,兩個點在線段的不同側.

 

最後,其實我們就是判斷下( v1×v3)*(v2×v3)<=0 說明他們在不同側.

 

向量的叉乘公式是: V1(x1, y1) ×V2(x2, y2) = x1y2 –y1x2

 

然後,接著,用同樣的方式判斷一下以p1->p2作為基準線,判斷p3和p4是否在兩邊,如果都滿足瞭,那說明兩個線段是相交的.

 

js實現如下:

 

 

 

 

01

//計算叉乘

02

 var crossMul=function(v1,v2){

03

        return   v1.x*v2.y-v1.y*v2.x;

04

    }

05

//相交返回true

06

    var checkCross=function(p1,p2,p3,p4){

07

        var v1={x:p1.x-p3.x,y:p1.y-p3.y},

08

        v2={x:p2.x-p3.x,y:p2.y-p3.y},

09

        v3={x:p4.x-p3.x,y:p4.y-p3.y},

10

        v=crossMul(v1,v3)*crossMul(v2,v3)

11

        v1={x:p3.x-p1.x,y:p3.y-p1.y}

12

        v2={x:p4.x-p1.x,y:p4.y-p1.y}

13

        v3={x:p2.x-p1.x,y:p2.y-p1.y}

14

        return (v<=0&&crossMul(v1,v3)*crossMul(v2,v3)<=0)?true:false

15

    }

然後這樣調用:

 

01

checkCross({

02

        x:0,

03

        y:0

04

    },{

05

        x:100,

06

        y:100

07

    },{

08

        x:20,

09

        y:0

10

    },{

11

        x:50,

12

        y:40

13

    })

這裡有個簡單的demo,不過參數是寫死的….沒空寫瞭….

 

http://www.html-js.com/mj/version1.0.3/lab/point-rect-test.html

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *