计算两条线的交点

Question

我有动态生成的动画线,我希望在线撞到另一条线时检测到.我正在尝试实现一些基本的线性代数来获得线的方程,然后求解x,y,但结果是不稳定的.在这一点上,我只测试两条线,这意味着我应该得到一个交叉点,但我得到两条线.我只是想确保我的数学运算正常,我应该在其他地方寻找问题.

function collision(boid1, boid2) {
    var x1 = boid1.initialX, y1 = boid1.initialY, x2 = boid1.x, y2 = boid1.y, x3 = boid2.initialX, y3 = boid2.initialY, x4 = boid2.x, y4 = boid2.y;

      slope1 = (y1 - y2)/(x1 - x2);
      slope2 = (y3 - y4)/(x3- x4);

      //console.log("slope1:"+slope1);
  //console.log('x2:'+x2+' y2:'+y2);

    if(slope1 != slope2){
        var b1 = getB(slope1,x1,y1);
        var b2 = getB(slope2,x3,y3);

        if(slope2 >= 0){
            u = slope1 - slope2;
        }else{
            u = slope1 + slope2;
        }

        if(b1 >= 0){
            z = b2 - b1;
        }else{
            z = b2 + b1;
        }

        pointX = z / u;

        pointY = (slope1*pointX)+b1;

        pointYOther = (slope2*pointX)+b2;

            console.log("pointx:"+pointX+" pointy:"+pointY+" othery:"+pointYOther);
            //return true;
            context.beginPath();
      context.arc(pointX, pointY, 2, 0, 2 * Math.PI, false);
      context.fillStyle = 'green';
      context.fill();
      context.lineWidth = 1;
      context.strokeStyle = '#003300';
      context.stroke();



    }

 return false;


}




function getB(slope,x,y){

    var y = y, x = x, m = slope;

    a = m*x;

    if(a>=0){
        b = y - a;
    }else{

        b = y + a;
    }

    return b;
}

编辑:

问题是我得到两个不同的交叉点值.应该只有一个,这让我相信我的计算是错误的.是的,x2,y2,x4,y4都在移动,但它们有一个设定角度,一致的斜率确认了这一点.

Answer 1

我找到了Paul Bourke的一个很好的解决方案.在这里,它是用JavaScript实现的:

function line_intersect(x1, y1, x2, y2, x3, y3, x4, y4)
{
    var ua, ub, denom = (y4 - y3)*(x2 - x1) - (x4 - x3)*(y2 - y1);
    if (denom == 0) {
        return null;
    }
    ua = ((x4 - x3)*(y1 - y3) - (y4 - y3)*(x1 - x3))/denom;
    ub = ((x2 - x1)*(y1 - y3) - (y2 - y1)*(x1 - x3))/denom;
    return {
        x: x1 + ua * (x2 - x1),
        y: y1 + ua * (y2 - y1),
        seg1: ua >= 0 && ua <= 1,
        seg2: ub >= 0 && ub <= 1
    };
}

Answer 2

对于线段与线段的交点，请使用Paul Bourke 的解决方案：

// line intercept math by Paul Bourke http://paulbourke.net/geometry/pointlineplane/
// Determine the intersection point of two line segments
// Return FALSE if the lines don't intersect
function intersect(x1, y1, x2, y2, x3, y3, x4, y4) {

  // Check if none of the lines are of length 0
    if ((x1 === x2 && y1 === y2) || (x3 === x4 && y3 === y4)) {
        return false
    }

    denominator = ((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1))

  // Lines are parallel
    if (denominator === 0) {
        return false
    }

    let ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denominator
    let ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denominator

  // is the intersection along the segments
    if (ua < 0 || ua > 1 || ub < 0 || ub > 1) {
        return false
    }

  // Return a object with the x and y coordinates of the intersection
    let x = x1 + ua * (x2 - x1)
    let y = y1 + ua * (y2 - y1)

    return {x, y}
}

对于无限线交点，请使用Justin C. Round 算法：

function checkLineIntersection(line1StartX, line1StartY, line1EndX, line1EndY, line2StartX, line2StartY, line2EndX, line2EndY) {
    // if the lines intersect, the result contains the x and y of the intersection (treating the lines as infinite) and booleans for whether line segment 1 or line segment 2 contain the point
    var denominator, a, b, numerator1, numerator2, result = {
        x: null,
        y: null,
        onLine1: false,
        onLine2: false
    };
    denominator = ((line2EndY - line2StartY) * (line1EndX - line1StartX)) - ((line2EndX - line2StartX) * (line1EndY - line1StartY));
    if (denominator == 0) {
        return result;
    }
    a = line1StartY - line2StartY;
    b = line1StartX - line2StartX;
    numerator1 = ((line2EndX - line2StartX) * a) - ((line2EndY - line2StartY) * b);
    numerator2 = ((line1EndX - line1StartX) * a) - ((line1EndY - line1StartY) * b);
    a = numerator1 / denominator;
    b = numerator2 / denominator;

    // if we cast these lines infinitely in both directions, they intersect here:
    result.x = line1StartX + (a * (line1EndX - line1StartX));
    result.y = line1StartY + (a * (line1EndY - line1StartY));

    // if line1 is a segment and line2 is infinite, they intersect if:
    if (a > 0 && a < 1) {
        result.onLine1 = true;
    }
    // if line2 is a segment and line1 is infinite, they intersect if:
    if (b > 0 && b < 1) {
        result.onLine2 = true;
    }
    // if line1 and line2 are segments, they intersect if both of the above are true
    return result;
};

Answer 3

将'found-x'插回其中一个方程式时,您无需在添加/减去y-intersects之间切换:

(function () {
    window.linear = {
        slope: function (x1, y1, x2, y2) {
            if (x1 == x2) return false;
            return (y1 - y2) / (x1 - x2);
        },
        yInt: function (x1, y1, x2, y2) {
            if (x1 === x2) return y1 === 0 ? 0 : false;
            if (y1 === y2) return y1;
            return y1 - this.slope(x1, y1, x2, y2) * x1 ;
        },
        getXInt: function (x1, y1, x2, y2) {
            var slope;
            if (y1 === y2) return x1 == 0 ? 0 : false;
            if (x1 === x2) return x1;
            return (-1 * ((slope = this.slope(x1, y1, x2, y2)) * x1 - y1)) / slope;
        },
        getIntersection: function (x11, y11, x12, y12, x21, y21, x22, y22) {
            var slope1, slope2, yint1, yint2, intx, inty;
            if (x11 == x21 && y11 == y21) return [x11, y11];
            if (x12 == x22 && y12 == y22) return [x12, y22];

            slope1 = this.slope(x11, y11, x12, y12);
            slope2 = this.slope(x21, y21, x22, y22);
            if (slope1 === slope2) return false;

            yint1 = this.yInt(x11, y11, x12, y12);
            yint2 = this.yInt(x21, y21, x22, y22);
            if (yint1 === yint2) return yint1 === false ? false : [0, yint1];

            if (slope1 === false) return [y21, slope2 * y21 + yint2];
            if (slope2 === false) return [y11, slope1 * y11 + yint1];
            intx = (slope1 * x11 + yint1 - yint2)/ slope2;
            return [intx, slope1 * intx + yint1];
        }
    }
}());