我尝试搜索一个 javascript 函数，该函数将检测两条线是否相互交叉。
该函数将获取每条线的起点和终点的 x,y 值（我们将它们称为线 A 和线 B）。
如果它们相交则返回true，否则返回false。
函数示例。如果答案使用矢量对象，我很高兴。
Function isIntersect (lineAp1x, lineAp1y, lineAp2x, lineAp2y, lineBp1x, lineBp1y, lineBp2x, lineBp2y)
{
// JavaScript line intersecting test here.
}
一些背景信息：此代码适用于我尝试在 html5 画布中制作的游戏，并且是我的碰撞检测的一部分。
// returns true if 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，它可以通过沿第一条线移动一段距离 lambda 到达，也可以通过沿第二条线移动伽马单位到达。这为我们提供了 X 坐标的两个联立方程：
X = v1 + lambda*d1
X = v2 + gamma *d2
这些方程可以用矩阵形式表示。我们检查行列式是否非零以查看交点 X 是否存在。
如果有交点，那么我们必须检查交点是否确实位于两组点之间。如果 lambda 大于 1，则交点超出第二个点。如果 lambda 小于 0，则交点在第一个点之前。
因此，0<lambda<1 && 0<gamma<1表明两条线相交！
Peter Wone 的回答是一个很好的解决方案，但它缺乏解释。我花了最后一个小时左右的时间来了解它是如何工作的，并且认为我理解的也足以解释它。有关详细信息，请参阅他的答案：https ://stackoverflow.com/a/16725715/697477
我还在下面的代码中包含了共线行的解决方案。
为了解释答案，让我们看一下两条线的每个交点的共同点。鉴于下图，我们可以看到P 1到IP到P 4逆时针旋转。我们可以看到它的互补边顺时针旋转。现在，我们不知道它是否相交，所以我们不知道相交点。但我们也可以看到，P 1到P 2到P 4也逆时针旋转。另外，P 1到P 2到P 3顺时针旋转。我们可以利用这些知识来确定两条线是否相交。
您会注意到相交的线创建了四个指向相反方向的面。由于它们面向相反的方向，我们知道P 1到P 2到P 3的方向旋转的方向不同于P 1到P 2到P 4的方向。我们还知道P 1到P 3到P 4的旋转方向与P 2到P 3到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>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;
}
我从中找到答案的wiki页面。
尽管能够找到交点很有用，但线段是否相交的测试最常用于多边形命中测试，并且考虑到通常的应用，您需要快速完成。因此我建议你这样做，只使用减法、乘法、比较和 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));
}
我已经使用 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));
}
这是基于此要点的版本，其中包含一些更简洁的变量名称和一些 Coffee。
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);
}
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)
这是一个 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,
};
}
首先，找到交点坐标 - 这里有详细描述：http: //www.mathopenref.com/coordintersection.html
然后检查交叉点的 x 坐标是否在其中一条线的 x 范围内（或者如果您愿意，也可以对 y 坐标执行相同操作），即如果 xIntersection 在 lineAp1x 和 lineAp2x 之间，则它们相交。
对于所有希望为冷融合准备好解决方案的人，这是我改编自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
重要的函数是来自 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>
我希望这可以帮助适应其他语言？
使用 pythageorum theorum 找到 2 个对象之间的距离并添加半径Pythageorum Theorum Distance Formula
