선분 교점 구하기, 선분 충돌(line segment collision)

Javascript로 구현한 선분충돌

투영을 통한 선분충돌

1번

2번

하지만 2번 이미지에서 초록 선분도 투영 결과는 같지만 충돌하지는 않은 상태입니다.
그렇기 때문에 파랑 선분의 직교 벡터에도 똑같이 투영을 하여 같은 결과가 나오는지 확인해주어야 합니다.

3번

3번 이미지는 파랑 선분의 직교 벡터인 파랑 직교 벡터에 투영을 한 결과입니다.
보라 선분은 아까와 같은 결과이지만 초록 선분은 그렇지 않습니다.

예외 : 두 선분의 벡터가 같은 방향을 가지고 있을 때,

4번

4번 이미지는 두 선분의 벡터가 같은 방향을 가지고 있을 때를 보여주는 이미지입니다.
해당 경우에는 직교 벡터에서 한 점에 투영이 됩니다.
이 경우에는 선분의 벡터에 투영하여 빨강 선분의 각 점 중 하나라도 파랑 선분의 사이에 있다면 충돌 된 것입니다.

보라 선분의 직교 벡터인 보라 직교벡터에 세 점을 투영하면 위와 같은 결과가 나옵니다.

이제 코드를 보겠습니다.

var myP1 = new PIXI.Vector(this.points[0].position.x, this.points[0].position.y);
var myP2 = new PIXI.Vector(this.points[1].position.x, this.points[1].position.y);
var otherP1 = new PIXI.Vector(other.points[0].position.x, other.points[0].position.y);
var otherP2 = new PIXI.Vector(other.points[1].position.x, other.points[1].position.y);
 
var myN = new PIXI.Vector(myP2.y - myP1.y, myP1.x - myP2.x);    
var otherN = new PIXI.Vector(otherP2.y - otherP1.y, otherP1.x - otherP2.x);

각 네점은 myP1, myP2, otherP1, otherP2 입니다.

myN과 otherN이 각 선분의 직교벡터입니다. 2차원 벡터의 직교벡터를 구하는 방법은 복소평면에서의 회전을 참고해주시면 좋을 것 같습니다.

var myDot = myN.dot(myP1);
var myDotA = myN.dot(otherP1) - myDot;
var myDotB = myN.dot(otherP2) - myDot;
 
if(myDotA * myDotB > 0)
    return false;
 

myN 벡터에 각 점을 투영하여 my가 other의 각 점 사이에 있는지 체크해줍니다.

투영은 벡터의 내적을 통해 얻을 수 있습니다.

var otherDot = otherN.dot(otherP1);
var otherDotA = otherN.dot(myP1) - otherDot;
var otherDotB = otherN.dot(myP2) - otherDot;
 
if(otherDotA * otherDotB > 0)
    return false;
 

똑같이 otherN벡터에 각 점을 투영하여 other가 my의 각 점 사이에 있는지 체크해줍니다.

두 선분의 벡터가 같은 방향을 가지고 있을 때 입니다.

// when vector same,
if(myDotA == 0 && myDotB == 0)
{
    var dir = myP2.clone().sub(myP1);
 
    var myP1Dot = dir.dot(myP1);
    var myP2Dot = dir.dot(myP2);
    var otherP1Dot = dir.dot(otherP1);
    var otherP2Dot = dir.dot(otherP2);
 
    if((myP1Dot - otherP1Dot) * (myP1Dot - otherP2Dot) < 0)
    {
        joint.x = myP1.x;
        joint.y = myP1.y;
        return true;
    }
    else if((myP2Dot - otherP1Dot) * (myP2Dot - otherP2Dot) < 0)
    {
        joint.x = myP2.x;
        joint.y = myP2.y;
        return true;
    }
}
 

my의 방향 벡터에 네 점을 투영하여 충돌을 검출합니다.

마지막으로 충돌 지점을 계산합니다.

var ratio = Math.abs(myDotA) / Math.abs(myDotB - myDotA);
 
var bPoint1 = otherP1.clone();
var bDelta = otherP2.clone().sub(otherP1).multiplyScalar(ratio);
var result = bPoint1.add(bDelta);
joint.x = result.x;
joint.y = result.y;
 

투영한 점의 비율을 계산하여 충돌 지점을 계산할 수 있습니다.

아래는 전체 코드입니다.

SegmentLine.prototype.getJoint = function (other, joint)
{
    var myP1 = new PIXI.Vector(this.points[0].position.x, this.points[0].position.y);
    var myP2 = new PIXI.Vector(this.points[1].position.x, this.points[1].position.y);
    var otherP1 = new PIXI.Vector(other.points[0].position.x, other.points[0].position.y);
    var otherP2 = new PIXI.Vector(other.points[1].position.x, other.points[1].position.y);
 
    var myN = new PIXI.Vector(myP2.y - myP1.y, myP1.x - myP2.x);    
    var otherN = new PIXI.Vector(otherP2.y - otherP1.y, otherP1.x - otherP2.x);

    var myDot = myN.dot(myP1);
    var myDotA = myN.dot(otherP1) - myDot;
    var myDotB = myN.dot(otherP2) - myDot;
 
    // when vector same,
    if(myDotA == 0 && myDotB == 0)
    {
        var dir = myP2.clone().sub(myP1);
        var myP1Dot = dir.dot(myP1);
        var myP2Dot = dir.dot(myP2);
        var otherP1Dot = dir.dot(otherP1);
        var otherP2Dot = dir.dot(otherP2);
        if((myP1Dot - otherP1Dot) * (myP1Dot - otherP2Dot) < 0)
        {
            joint.x = myP1.x;
            joint.y = myP1.y;
            return true;
        }
        else if((myP2Dot - otherP1Dot) * (myP2Dot - otherP2Dot) < 0)    
        {
            joint.x = myP2.x;
            joint.y = myP2.y;
            return true;
        }
    }
 
    if(myDotA * myDotB > 0)
        return false;
 
    var otherDot = otherN.dot(otherP1);
    var otherDotA = otherN.dot(myP1) - otherDot;    
    var otherDotB = otherN.dot(myP2) - otherDot;    
 
    if(otherDotA * otherDotB > 0)
        return false;
 
    var ratio = Math.abs(myDotA) / Math.abs(myDotB - myDotA);
    var bPoint1 = otherP1.clone();
    var bDelta = otherP2.clone().sub(otherP1).multiplyScalar(ratio);
    var result = bPoint1.add(bDelta);
    joint.x = result.x;
    joint.y = result.y;
    return true;
}