测试两条线是否相交 - JavaScript函数

Question

我已经尝试搜索一个javascript函数,它将检测两条线是否相互交叉.

该函数将获取每一行的两个起始端点的x,y值(我们称之为A行和B行).

如果相交则返回true,否则返回false.

功能示例.如果答案使用矢量对象,我很高兴.

Function isIntersect (lineAp1x, lineAp1y, lineAp2x, lineAp2y, lineBp1x, lineBp1y, lineBp2x, lineBp2y) 
{

    // JavaScript line intersecting test here. 

}

一些背景信息:这段代码是我想在html5画布中制作的游戏,也是我碰撞检测的一部分.

Answer 1

// returns true iff the line from (a,b)->(c,d) intersects with (p,q)->(r,s)
function intersects(a,b,c,d,p,q,r,s) {
  var det, gamma, lambda;
  det = (c - a) * (s - q) - (r - p) * (d - b);
  if (det === 0) {
    return false;
  } else {
    lambda = ((s - q) * (r - a) + (p - r) * (s - b)) / det;
    gamma = ((b - d) * (r - a) + (c - a) * (s - b)) / det;
    return (0 < lambda && lambda < 1) && (0 < gamma && gamma < 1);
  }
};

说明:(向量,矩阵和厚脸皮的决定因素)

线可以用一些初始向量v和方向向量d来描述:

r = v + lambda*d 

我们使用一个点(a,b)作为初始向量,并将它们之间的差异(c-a,d-b)作为方向向量.同样对于我们的第二行.

如果我们的两条线相交,那么必须有一个点X,它可以通过沿着我们的第一条线行进一段距离λ,也可以通过沿着第二条线行进伽马单元到达.这给出了两个X坐标的联立方程:

X = v1 + lambda*d1 
X = v2 + gamma *d2

这些方程可以以矩阵形式表示.我们检查行列式是否为非零,以查看交集X是否存在.

如果有一个交叉点,那么我们必须检查交叉点是否实际位于两组点之间.如果lambda大于1,则交点超出第二个点.如果lambda小于0,则交点位于第一个点之前.

因此,0<lambda<1 && 0<gamma<1表明两条线相交!

Answer 2

function lineIntersect(x1,y1,x2,y2, x3,y3,x4,y4) {
    var x=((x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4))/((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4));
    var y=((x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4))/((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4));
    if (isNaN(x)||isNaN(y)) {
        return false;
    } else {
        if (x1>=x2) {
            if (!(x2<=x&&x<=x1)) {return false;}
        } else {
            if (!(x1<=x&&x<=x2)) {return false;}
        }
        if (y1>=y2) {
            if (!(y2<=y&&y<=y1)) {return false;}
        } else {
            if (!(y1<=y&&y<=y2)) {return false;}
        }
        if (x3>=x4) {
            if (!(x4<=x&&x<=x3)) {return false;}
        } else {
            if (!(x3<=x&&x<=x4)) {return false;}
        }
        if (y3>=y4) {
            if (!(y4<=y&&y<=y3)) {return false;}
        } else {
            if (!(y3<=y&&y<=y4)) {return false;}
        }
    }
    return true;
}

的维基页面,我发现,答案.

Answer 3

Peter Wone的答案是一个很好的解决方案,但它没有解释.我花了大约一小时左右了解它是如何工作的,并认为我理解得足以解释它.有关详细信息,请参阅他的答案:https://stackoverflow.com/a/16725715/697477

我还在下面的代码中包含了共线的解决方案.

使用旋转方向检查交叉点

为了解释答案,让我们看一下两条线的每个交叉点的共同点.如下图所示,我们可以看到P ₁到IP到P ₄逆时针旋转.我们可以看到它的互补侧顺时针旋转.现在,我们不知道它是否相交,所以我们不知道交点.但我们也可以看到P ₁到P ₂到P ₄也逆时针旋转.另外,P ₁至P ₂至P ₃顺时针旋转.我们可以使用这些知识来确定两条线是否相交.

交叉点示例

您会注意到相交线会创建四个指向相反方向的面.由于它们面向相反的方向,我们知道P ₁到P ₂到P ₃的方向旋转不同于P ₁到P ₂到P _4的方向.我们还知道P ₁到P ₃到P _4的旋转方向与P ₂到P ₃到P _4的方向不同.

非交叉示例

在此示例中,您应该注意到,在交叉点测试的相同模式之后,两个面会旋转相同的方向.由于它们面向相同的方向,我们知道它们不相交.

代码示例

因此,我们可以将其实现为Peter Wone提供的原始代码.

// Check the direction these three points rotate
function RotationDirection(p1x, p1y, p2x, p2y, p3x, p3y) {
  if (((p3y - p1y) * (p2x - p1x)) > ((p2y - p1y) * (p3x - p1x)))
    return 1;
  else if (((p3y - p1y) * (p2x - p1x)) == ((p2y - p1y) * (p3x - p1x)))
    return 0;
  
  return -1;
}

function containsSegment(x1, y1, x2, y2, sx, sy) {
  if (x1 < x2 && x1 < sx && sx < x2) return true;
  else if (x2 < x1 && x2 < sx && sx < x1) return true;
  else if (y1 < y2 && y1 < sy && sy < y2) return true;
  else if (y2 < y1 && y2 < sy && sy < y1) return true;
  else if (x1 == sx && y1 == sy || x2 == sx && y2 == sy) return true;
  return false;
}

function hasIntersection(x1, y1, x2, y2, x3, y3, x4, y4) {
  var f1 = RotationDirection(x1, y1, x2, y2, x4, y4);
  var f2 = RotationDirection(x1, y1, x2, y2, x3, y3);
  var f3 = RotationDirection(x1, y1, x3, y3, x4, y4);
  var f4 = RotationDirection(x2, y2, x3, y3, x4, y4);
  
  // If the faces rotate opposite directions, they intersect.
  var intersect = f1 != f2 && f3 != f4;
  
  // If the segments are on the same line, we have to check for overlap.
  if (f1 == 0 && f2 == 0 && f3 == 0 && f4 == 0) {
    intersect = containsSegment(x1, y1, x2, y2, x3, y3) || containsSegment(x1, y1, x2, y2, x4, y4) ||
    containsSegment(x3, y3, x4, y4, x1, y1) || containsSegment(x3, y3, x4, y4, x2, y2);
  }
  
  return intersect;
}

// Main call for checking intersection. Particularly verbose for explanation purposes.
function checkIntersection() {
  // Grab the values
  var x1 = parseInt($('#p1x').val());
  var y1 = parseInt($('#p1y').val());
  var x2 = parseInt($('#p2x').val());
  var y2 = parseInt($('#p2y').val());
  var x3 = parseInt($('#p3x').val());
  var y3 = parseInt($('#p3y').val());
  var x4 = parseInt($('#p4x').val());
  var y4 = parseInt($('#p4y').val());

  // Determine the direction they rotate. (You can combine this all into one step.)
  var face1CounterClockwise = RotationDirection(x1, y1, x2, y2, x4, y4);
  var face2CounterClockwise = RotationDirection(x1, y1, x2, y2, x3, y3);
  var face3CounterClockwise = RotationDirection(x1, y1, x3, y3, x4, y4);
  var face4CounterClockwise = RotationDirection(x2, y2, x3, y3, x4, y4);

  // If face 1 and face 2 rotate different directions and face 3 and face 4 rotate different directions, 
  // then the lines intersect.
  var intersect = hasIntersection(x1, y1, x2, y2, x3, y3, x4, y4);

  // Output the results.
  var output = "Face 1 (P1, P2, P4) Rotates: " + ((face1CounterClockwise > 0) ? "counterClockWise" : ((face1CounterClockwise == 0) ? "Linear" : "clockwise")) + "<br />";
  var output = output + "Face 2 (P1, P2, P3) Rotates: " + ((face2CounterClockwise > 0) ? "counterClockWise" : ((face2CounterClockwise == 0) ? "Linear" : "clockwise")) + "<br />";
  var output = output + "Face 3 (P1, P3, P4) Rotates: " + ((face3CounterClockwise > 0) ? "counterClockWise" : ((face3CounterClockwise == 0) ? "Linear" : "clockwise")) + "<br />";
  var output = output + "Face 4 (P2, P3, P4) Rotates: " + ((face4CounterClockwise > 0) ? "counterClockWise" : ((face4CounterClockwise == 0) ? "Linear" : "clockwise")) + "<br />";
  var output = output + "Intersection: " + ((intersect) ? "Yes" : "No") + "<br />";
  $('#result').html(output);


  // Draw the lines.
  var canvas = $("#canvas");
  var context = canvas.get(0).getContext('2d');
  context.clearRect(0, 0, canvas.get(0).width, canvas.get(0).height);
  context.beginPath();
  context.moveTo(x1, y1);
  context.lineTo(x2, y2);
  context.moveTo(x3, y3);
  context.lineTo(x4, y4);
  context.stroke();
}

checkIntersection();

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

<canvas id="canvas" width="200" height="200" style="border: 2px solid #000000; float: right;"></canvas>
<div style="float: left;">
  <div style="float: left;">
    <b>Line 1:</b>
    <br />P1 x:
    <input type="number" min="0" max="200" id="p1x" style="width: 40px;" onChange="checkIntersection();" value="0">y:
    <input type="number" min="0" max="200" id="p1y" style="width: 40px;" onChange="checkIntersection();" value="20">
    <br />P2 x:
    <input type="number" min="0" max="200" id="p2x" style="width: 40px;" onChange="checkIntersection();" value="100">y:
    <input type="number" min="0" max="200" id="p2y" style="width: 40px;" onChange="checkIntersection();" value="20">
    <br />
  </div>
  <div style="float: left;">
    <b>Line 2:</b>
    <br />P3 x:
    <input type="number" min="0" max="200" id="p3x" style="width: 40px;" onChange="checkIntersection();" value="150">y:
    <input type="number" min="0" max="200" id="p3y" style="width: 40px;" onChange="checkIntersection();" value="100">
    <br />P4 x:
    <input type="number" min="0" max="200" id="p4x" style="width: 40px;" onChange="checkIntersection();" value="0">y:
    <input type="number" min="0" max="200" id="p4y" style="width: 40px;" onChange="checkIntersection();" value="0">
    <br />
  </div>
  <br style="clear: both;" />
  <br />
  <div style="float: left; border: 1px solid #EEEEEE; padding: 2px;" id="result"></div>
</div>

Answer 4

尽管能够找到交叉点是有用的,但是测试线段是否相交最常用于多边形命中测试,并且考虑到它的通常应用,您需要快速完成.所以我建议你这样做,只使用减法,乘法,比较和AND.Turn计算由三个点描述的两个边缘之间的斜率变化的方向:1表示逆时针,0表示没有转动,-1表示顺时针.

此代码需要表示为GLatLng对象的点,但可以简单地重写为其他表示系统.斜率比较已经标准化为epsilon容差以抑制浮点误差.

function Turn(p1, p2, p3) {
  a = p1.lng(); b = p1.lat(); 
  c = p2.lng(); d = p2.lat();
  e = p3.lng(); f = p3.lat();
  A = (f - b) * (c - a);
  B = (d - b) * (e - a);
  return (A > B + Number.EPSILON) ? 1 : (A + Number.EPSILON < B) ? -1 : 0;
}

function isIntersect(p1, p2, p3, p4) {
  return (Turn(p1, p3, p4) != Turn(p2, p3, p4)) && (Turn(p1, p2, p3) != Turn(p1, p2, p4));
}

Answer 5

我用x/y而不是lat()/ long()重写了Peter Wone对单个函数的回答

function isIntersecting(p1, p2, p3, p4) {
    function CCW(p1, p2, p3) {
        return (p3.y - p1.y) * (p2.x - p1.x) > (p2.y - p1.y) * (p3.x - p1.x);
    }
    return (CCW(p1, p3, p4) != CCW(p2, p3, p4)) && (CCW(p1, p2, p3) != CCW(p1, p2, p4));
}

Answer 6

这是一个 TypeScript 实现，很大程度上受到 Dan Fox 解决方案的启发。此实现将为您提供交点（如果有）。否则（平行或无交集），undefined将被返回。

interface Point2D {
  x: number;
  y: number;
}

function intersection(from1: Point2D, to1: Point2D, from2: Point2D, to2: Point2D): Point2D {
  const dX: number = to1.x - from1.x;
  const dY: number = to1.y - from1.y;

  const determinant: number = dX * (to2.y - from2.y) - (to2.x - from2.x) * dY;
  if (determinant === 0) return undefined; // parallel lines

  const lambda: number = ((to2.y - from2.y) * (to2.x - from1.x) + (from2.x - to2.x) * (to2.y - from1.y)) / determinant;
  const gamma: number = ((from1.y - to1.y) * (to2.x - from1.x) + dX * (to2.y - from1.y)) / determinant;

  // check if there is an intersection
  if (!(0 <= lambda && lambda <= 1) || !(0 <= gamma && gamma <= 1)) return undefined;

  return {
    x: from1.x + lambda * dX,
    y: from1.y + lambda * dY,
  };
}