Ответ 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.

Если есть пересечение, то мы должны проверить, что пересечение фактически лежит между обеими наборами точек. Если лямбда больше 1, пересечение выходит за вторую точку. Если лямбда меньше 0, пересечение находится перед первой точкой.

Следовательно, 0<lambda<1 && 0<gamma<1 указывает, что две линии пересекаются!

Ответ 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;
}

Страница wiki Я нашел ответ.

Ответ 3

Ответ Питер Вон - отличное решение, но ему не хватает объяснений. Я провел последний час или около того, понимая, как это работает, и думаю, что я понимаю достаточно, чтобы объяснить это. См. Его ответ для деталей: fooobar.com/questions/235363/...

Я также включил решение для колинейных линий в приведенном ниже коде.

Использование поворотного направления для проверки пересечения

Чтобы объяснить ответ, рассмотрим что-то общее о каждом пересечении двух линий. Учитывая рисунок ниже, мы можем видеть, что P ₁ до IP до P ₄ вращается против часовой стрелки. Мы видим, что это бесплатные стороны вращаются по часовой стрелке. Теперь мы не знаем, пересекается ли она, поэтому мы не знаем точки пересечения. Но мы также можем видеть, что P ₁ до P ₂ до P ₄ также вращается против часовой стрелки. Кроме того << → << → << → << → вращает часы. Мы можем использовать это знание, чтобы определить, пересекаются ли две линии или нет.

Пример пересечения

Вы заметите, что пересекающиеся линии создают четыре лица, которые указывают противоположные направления. Поскольку они сталкиваются с противоположными направлениями, мы знаем, что направление P ₁ до P ₂ до P ₃ вращает направление, отличное от P ₁ до P ₂ до P ₄. Мы также знаем, что P ₁ до P ₃ до P ₄ вращает другое направление, чем 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>

Ответ 4

Несмотря на то, что полезно найти точку пересечения, тестирование того, пересекаются ли сегменты линии, чаще всего используется для тестирования полигонов, и, учитывая обычные приложения, вам нужно сделать это быстро. Поэтому я предлагаю вам сделать это так, используя только вычитание, умножение, сравнение и И. 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));
}

Ответ 5

Я переписал ответ Питера Вон на одну функцию, используя 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));
}

Ответ 6

Здесь версия, основанная на этой теме с некоторыми более краткими именами переменных и некоторым кофе.

версия 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)

Ответ 7

Сначала найдите координаты пересечения - здесь он подробно описан: http://www.mathopenref.com/coordintersection.html

Затем проверьте, находится ли x-координата для пересечения в пределах х для одной из строк (или если вы предпочитаете то же самое с y-координатой) то есть, если xIntersection находится между lineAp1x и lineAp2x, то они пересекаются.

Ответ 8

Для всех людей, которые хотели бы иметь готовые решения для 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>

Я надеюсь, что это может помочь в адаптации к другим языкам?