Проверить, пересекаются ли две линии - функция JavaScript
Я попытался найти функцию javascript, которая будет определять, пересекаются ли две линии.
Функция будет принимать значения x,y обеих начальных конечных точек для каждой линии (мы будем называть их линией A и линией B).
Возвращать true, если они пересекаются, иначе false.
Пример функции. Я рад, если вместо ответа используется векторный объект.
Function isIntersect (lineAp1x, lineAp1y, lineAp2x, lineAp2y, lineBp1x, lineBp1y, lineBp2x, lineBp2y)
{
// JavaScript line intersecting test here.
}
Некоторая справочная информация: этот код предназначен для игры, которую я пытаюсь создать в html5 canvas, и является частью моего обнаружения столкновений.
8 ответов
// 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 даже.
Если есть пересечение, то мы должны проверить, что пересечение действительно лежит между обоими наборами точек. Если лямбда больше 1, пересечение выходит за пределы второй точки. Если лямбда меньше 0, то пересечение находится перед первой точкой.
Следовательно, 0<lambda<1 && 0<gamma<1 указывает на то, что две линии пересекаются!
Ответ Питера Воне - отличное решение, но ему не хватает объяснения. Я провел последний час или около того, понимая, как это работает, и думаю, что понимаю достаточно, чтобы объяснить это. Подробности смотрите в его ответе: /questions/35816169/proverit-peresekayutsya-li-dve-linii-funktsiya-javascript/35816172#35816172
Я также включил решение для коллинеарных линий в коде ниже.
Использование указателей поворота для проверки пересечения
Чтобы объяснить ответ, давайте рассмотрим нечто общее в каждом пересечении двух линий. Учитывая рисунок ниже, мы можем видеть, что 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.
Пример без пересечения
В этом примере вы должны заметить, что, следуя одинаковому шаблону для теста на пересечение, две грани вращаются в одном направлении. Поскольку они сталкиваются в одном направлении, мы знаем, что они не пересекаются.
Пример кода
Итак, мы можем реализовать это в исходном коде, предоставленном Питером Воне.
// 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;
}
Вики- страница, на которой я нашел ответ.
Хотя полезно найти точку пересечения, проверка того, пересекаются ли отрезки, чаще всего используется для проверки попадания многоугольника, и с учетом обычных применений этого вам нужно сделать это быстро. Поэтому я предлагаю вам сделать это, используя только вычитание, умножение, сравнение и AND. Turn вычисляет направление изменения наклона между двумя ребрами, описанными тремя точками: 1 означает против часовой стрелки, 0 означает отсутствие поворота и -1 означает по часовой стрелке.
Этот код ожидает точки, выраженные как объекты GLatLng, но может быть тривиально переписан в другие системы представления. Сравнение наклона было нормализовано к эпсилонному допуску на погрешности с плавающей запятой.
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()
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));
}
А вот и реализация TypeScript, во многом вдохновленная решением Дэна Фокса. Эта реализация даст вам точку пересечения, если она есть. В противном случае (параллельно или без пересечения),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,
};
}
Вот версия, основанная на этом, с более краткими именами переменных и кофе.
Версия 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
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)
Сначала найдите координаты пересечения - здесь это подробно описано: http://www.mathopenref.com/coordintersection.html
Затем проверьте, попадает ли x-координата для пересечения в диапазоны x для одной из линий (или, если хотите, проделайте то же самое с y-координатой), т.е. если xIntersection находится между lineAp1x и lineAp2x, то они пересекаются.
Для всех, кто хотел бы иметь готовые решения для Coldfusion, вот что я адаптировал с 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
функции imporants - ccw и linesIntersect из java.awt.geom.Line2D, и я записал их в 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, чтобы найти расстояние между двумя объектами и добавьте радиус Формула расстояния Pythageorum Theorum