测试两条线是否相交 - JavaScript 函数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9043805/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Test if two lines intersect - JavaScript function
提问by Jarrod
I've tried searching for a javascript function that will detect if two lines intersect each other.
我试过寻找一个 javascript 函数来检测两条线是否相交。
The function will take the x,y values of both the start end points for each line (we'll call them line A and line B).
该函数将获取每条线（我们将它们称为线 A 和线 B）的两个起点的 x,y 值。
Is to return true if they intersect, otherwise false.
如果它们相交则返回真，否则返回假。
Example of the function. I'm happy if the answer uses a vector object instead.
函数示例。如果答案使用矢量对象，我很高兴。
Function isIntersect (lineAp1x, lineAp1y, lineAp2x, lineAp2y, lineBp1x, lineBp1y, lineBp2x, lineBp2y)
{
// JavaScript line intersecting test here.
}
Some background info: this code is for a game I'm trying to make in html5 canvas, and is part of my collision detection.
一些背景信息：此代码用于我尝试在 html5 画布中制作的游戏，并且是我的碰撞检测的一部分。
回答by Dan Fox
// 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);
}
};
Explanation: (vectors, a matrix and a cheeky determinant)
解释：（向量、矩阵和厚脸皮行列式）
Lines can be described by some initial vector, v, and a direction vector, d:
线可以用一些初始向量 v 和方向向量 d 来描述：
r = v + lambda*d
We use one point (a,b)as the initial vector and the difference between them (c-a,d-b)as the direction vector. Likewise for our second line.
我们使用一个点(a,b)作为初始向量，它们之间的差(c-a,d-b)作为方向向量。同样对于我们的第二行。
If our two lines intersect, then there must be a point, X, that is reachable by travelling some distance, lambda, along our first line and also reachable by travelling gamma units along our second line. This gives us two simultaneous equations for the coordinates of X:
如果我们的两条线相交，那么一定有一个点 X，它可以通过沿着我们的第一条线移动一段距离 lambda 到达，也可以通过沿着我们的第二条线移动伽马单位到达。这为我们提供了 X 坐标的两个联立方程：
X = v1 + lambda*d1
X = v2 + gamma *d2
These equations can be represented in matrix form. We check that the determinant is non-zero to see if the intersection X even exists.
这些方程可以用矩阵形式表示。我们检查行列式是否非零以查看交集 X 是否存在。
If there is an intersection, then we must check that the intersection actually lies between both sets of points. If lambda is greater than 1, the intersection is beyond the second point. If lambda is less than 0, the intersection is before the first point.
如果有交点，那么我们必须检查交点是否确实位于两组点之间。如果 lambda 大于 1，则交点超出第二个点。如果 lambda 小于 0，则交点在第一个点之前。
Hence, 0<lambda<1 && 0<gamma<1indicates that the two lines intersect!
因此，0<lambda<1 && 0<gamma<1表示两条线相交！
回答by Alex Malcolm
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;
}
The wikipage I found the answer from.
我从中找到了答案的维基页面。
回答by teynon
Peter Wone's answer is a great solution, but it lacks an explanation. I spent the last hour or so understanding how it works and think I understand enough to explain it as well. See his answer for details: https://stackoverflow.com/a/16725715/697477
Peter Wone 的回答是一个很好的解决方案，但缺乏解释。我花了最后一个小时左右来了解它是如何工作的，并且我认为我也足够理解来解释它。详情见他的回答：https: //stackoverflow.com/a/16725715/697477
I've also included a solution for the co-linear lines in the code below.
我还在下面的代码中包含了共线线的解决方案。
Using Rotational Directions to check for intersection
使用旋转方向检查相交
To explain the answer, let's look at something common about every intersection of two lines. Given the picture below, we can see that P1to IPto P4rotates counter clockwise. We can see that it's complimentary sides rotate clockwise. Now, we don't know if it intersects, so we don't know the intersection point. But we can also see that P1to P2to P4also rotates counter clockwise. Additionally, P1to P2to P3rotates clock wise. We can use this knowledge to determine whether two lines intersect or not.
为了解释答案，让我们看一下两条线的每个交点的共同点。给定下图，我们可以看到P 1到IP到P 4逆时针旋转。我们可以看到它的互补边顺时针旋转。现在，我们不知道它是否相交，所以我们不知道交点。但是我们也可以看到P 1到P 2到P 4也逆时针旋转。此外，P 1到P 2到P 3顺时针旋转。我们可以利用这些知识来确定两条线是否相交。
Intersection Example
交叉路口示例
You'll notice that intersecting lines create four faces that point opposite directions. Since they face opposite directions, we know that the direction of P1to P2to P3rotates a direction different than P1to P2to P4. We also know that P1to P3to P4rotates a different direction than P2to P3to P4.
您会注意到相交线会创建四个指向相反方向的面。由于它们面向相反的方向，我们知道P 1到P 2到P 3的方向旋转的方向不同于P 1到P 2到P 4 的方向。我们还知道P 1到P 3到P 4 的旋转方向与P 2到P 3到P 4 的旋转方向不同。
Non-Intersection Example
非交集示例
In this example, you should notice that following the same pattern for the intersection test, the two faces rotate the same direction. Since they face the same direction, we know that they do not intersect.
在此示例中，您应该注意到，按照相交测试的相同模式，两个面旋转相同的方向。由于它们面向同一方向，我们知道它们不相交。
Code Sample
代码示例
So, we can implement this into the original code supplied by Peter Wone.
因此，我们可以将其实现到 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>回答by Peter Wone
Although it is useful to be able to find the intersection point, testing for whetherline segments intersect is most often used for polygon hit-testing, and given the usual applications of that, you need to do it fast. Therefore I suggest you do it like this, using only subtraction, multiplication, comparison and AND. Turncomputes the direction of the change in slope between the two edges described by the three points: 1 means counter-clockwise, 0 means no turn and -1 means clockwise.
虽然能够找到交点很有用，但测试线段是否相交最常用于多边形命中测试，并且鉴于其通常的应用，您需要快速完成。因此我建议你这样做，只使用减法、乘法、比较和与。Turn计算由三个点描述的两条边之间斜率变化的方向：1 表示逆时针，0 表示不转弯，-1 表示顺时针。
This code expects points expressed as GLatLng objects but can be trivially rewritten to other systems of representation. The slope comparison has been normalised to epsilontolerance to damp floating point errors.
此代码期望点表示为 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));
}
回答by Jonathan
I've rewritten Peter Wone's answer to a single function using x/y instead of lat()/long()
我已经使用 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));
}
回答by 1j01
Here's a version based on this gistwith some more concise variable names, and some Coffee.
这是一个基于此要点的版本，带有一些更简洁的变量名称和一些 Coffee。
JavaScript version
JavaScript 版本
var lineSegmentsIntersect = (x1, y1, x2, y2, x3, y3, x4, y4)=> {
var a_dx = x2 - x1;
var a_dy = y2 - y1;
var b_dx = x4 - x3;
var b_dy = y4 - y3;
var s = (-a_dy * (x1 - x3) + a_dx * (y1 - y3)) / (-b_dx * a_dy + a_dx * b_dy);
var t = (+b_dx * (y1 - y3) - b_dy * (x1 - x3)) / (-b_dx * a_dy + a_dx * b_dy);
return (s >= 0 && s <= 1 && t >= 0 && t <= 1);
}
CoffeeScript version
CoffeeScript 版本
lineSegmentsIntersect = (x1, y1, x2, y2, x3, y3, x4, y4)->
a_dx = x2 - x1
a_dy = y2 - y1
b_dx = x4 - x3
b_dy = y4 - y3
s = (-a_dy * (x1 - x3) + a_dx * (y1 - y3)) / (-b_dx * a_dy + a_dx * b_dy)
t = (+b_dx * (y1 - y3) - b_dy * (x1 - x3)) / (-b_dx * a_dy + a_dx * b_dy)
(0 <= s <= 1 and 0 <= t <= 1)
回答by egres
First, find intersection coordinates - here it's described in detail: http://www.mathopenref.com/coordintersection.html
首先，找到交点坐标 - 这里有详细描述：http: //www.mathopenref.com/coordintersection.html
Then check if the x-coordinate for intersection falls within the x ranges for one of the lines (or do the same with y-coordinate, if you prefer), i.e. if xIntersection is between lineAp1x and lineAp2x, then they intersect.
然后检查相交的 x 坐标是否在其中一条线的 x 范围内（或者对 y 坐标执行相同的操作，如果您愿意），即如果 xIntersection 在 lineAp1x 和 lineAp2x 之间，则它们相交。
回答by 1FpGLLjZSZMx6k
Here comes a TypeScript implementation, heavily inspired by Dan Fox's solution.
This implementation will give you the intersection point, if there is one. Otherwise (parallel or no intersection), undefinedwill be returned.
这是一个 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,
};
}
回答by Raffael Meier
For all folks who would like to have a solutions ready for coldfusion, here is what I adapted from http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/awt/geom/Line2D.java#Line2D.linesIntersect%28double%2Cdouble%2Cdouble%2Cdouble%2Cdouble%2Cdouble%2Cdouble%2Cdouble%29
对于所有想要为冷融合准备好解决方案的人，这里是我改编自http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/ awt/geom/Line2D.java#Line2D.linesIntersect%28double%2Cdouble%2Cdouble%2Cdouble%2Cdouble%2Cdouble%2Cdouble%2Cdouble%29
the imporants functions are ccw and linesIntersect from java.awt.geom.Line2D and I wrote them into coldfusion, so here we go:
重要的函数是来自 java.awt.geom.Line2D 的 ccw 和 linesIntersect，我将它们写入了 Coldfusion，所以我们开始：
<cffunction name="relativeCCW" description="schnittpunkt der vier punkte (2 geraden) berechnen">
<!---
Returns an indicator of where the specified point (px,py) lies with respect to this line segment. See the method comments of relativeCCW(double,double,double,double,double,double) to interpret the return value.
Parameters:
px the X coordinate of the specified point to be compared with this Line2D
py the Y coordinate of the specified point to be compared with this Line2D
Returns:
an integer that indicates the position of the specified coordinates with respect to this Line2D
--->
<cfargument name="x1" type="numeric" required="yes" >
<cfargument name="y1" type="numeric" required="yes">
<cfargument name="x2" type="numeric" required="yes" >
<cfargument name="y2" type="numeric" required="yes">
<cfargument name="px" type="numeric" required="yes" >
<cfargument name="py" type="numeric" required="yes">
<cfscript>
x2 = x2 - x1;
y2 = y2 - y1;
px = px - x1;
py = py - y1;
ccw = (px * y2) - (py * x2);
if (ccw EQ 0) {
// The point is colinear, classify based on which side of
// the segment the point falls on. We can calculate a
// relative value using the projection of px,py onto the
// segment - a negative value indicates the point projects
// outside of the segment in the direction of the particular
// endpoint used as the origin for the projection.
ccw = (px * x2) + (py * y2);
if (ccw GT 0) {
// Reverse the projection to be relative to the original x2,y2
// x2 and y2 are simply negated.
// px and py need to have (x2 - x1) or (y2 - y1) subtracted
// from them (based on the original values)
// Since we really want to get a positive answer when the
// point is "beyond (x2,y2)", then we want to calculate
// the inverse anyway - thus we leave x2 & y2 negated.
px = px - x2;
py = py - y2;
ccw = (px * x2) + (py * y2);
if (ccw LT 0) {
ccw = 0;
}
}
}
if (ccw LT 0) {
ret = -1;
}
else if (ccw GT 0) {
ret = 1;
}
else {
ret = 0;
}
</cfscript>
<cfreturn ret>
</cffunction>
<cffunction name="linesIntersect" description="schnittpunkt der vier punkte (2 geraden) berechnen">
<cfargument name="x1" type="numeric" required="yes" >
<cfargument name="y1" type="numeric" required="yes">
<cfargument name="x2" type="numeric" required="yes" >
<cfargument name="y2" type="numeric" required="yes">
<cfargument name="x3" type="numeric" required="yes" >
<cfargument name="y3" type="numeric" required="yes">
<cfargument name="x4" type="numeric" required="yes" >
<cfargument name="y4" type="numeric" required="yes">
<cfscript>
a1 = relativeCCW(x1, y1, x2, y2, x3, y3);
a2 = relativeCCW(x1, y1, x2, y2, x4, y4);
a3 = relativeCCW(x3, y3, x4, y4, x1, y1);
a4 = relativeCCW(x3, y3, x4, y4, x2, y2);
aa = ((relativeCCW(x1, y1, x2, y2, x3, y3) * relativeCCW(x1, y1, x2, y2, x4, y4) LTE 0)
&& (relativeCCW(x3, y3, x4, y4, x1, y1) * relativeCCW(x3, y3, x4, y4, x2, y2) LTE 0));
</cfscript>
<cfreturn aa>
</cffunction>
I hope this can help for adapting to other laguages?
我希望这可以帮助适应其他语言？
回答by Edu Faus
Use the pythageorum theorum to find the distance between the 2 objects and add the radius Pythageorum Theorum Distance Formula
使用勾股定理求2个物体之间的距离并加上半径勾股定理距离公式
