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;
}

Strona wiki z której znalazłem odpowiedź.

Odpowiedź Petera Wone ' a jest świetnym rozwiązaniem, ale brakuje w niej wyjaśnienia. Spędziłem ostatnią godzinę rozumiejąc, jak to działa i myślę, że rozumiem wystarczająco, aby to wyjaśnić. Zobacz jego odpowiedź po szczegóły: https://stackoverflow.com/a/16725715/697477

Umieściłem również rozwiązanie dla linii współliniowych w poniższym kodzie.

Używanie wskazówek obrotowych do sprawdzania przecięcia

Aby wyjaśnić odpowiedź, spójrzmy na coś wspólnego w każdym przecięcie dwóch linii. Biorąc pod uwagę zdjęcie poniżej, możemy zobaczyć, że P₁ na IP na P₄ obraca się w lewo. Widzimy, że jego boki obracają się zgodnie z ruchem wskazówek zegara. Nie wiemy, czy się przecina, więc nie znamy punktu przecięcia. Ale widzimy też, że P₁ na P₂ na P₄ również obraca się w lewo. Dodatkowo, P₁ na P₂ na P₃ obraca zegar mądry. Możemy użyć tej wiedzy, aby określić, czy dwie linie przecinają się, czy nie.

Przykład Przecięcia

Zauważysz, że przecinające się linie tworzą cztery twarze, które punktują w przeciwnych kierunkach. Ponieważ stoją w przeciwnych kierunkach, wiemy, że kierunek P₁ na P₂ na P₃ obraca się w kierunku innym niż P₁ na P₂ na P₄. Wiemy również, że P₁ na P₃ na P₄ obraca się w innym kierunku niż P₂ na P₃ na P₄.

Przykład Bez Przecięcia

W tym przykładzie należy zauważyć, że zgodnie z tym samym wzorem dla testu przecięcia obie powierzchnie obracają się w tym samym kierunku. Ponieważ zmierzają w tym samym kierunku, wiemy, że nie przecinają się.

Próbka Kodu

Możemy więc zaimplementować to do oryginalnego kodu dostarczonego przez Petera 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>

Chociaż przydatne jest znalezienie punktu przecięcia, testowanie Czy odcinki linii przecinają się najczęściej jest używane do testowania trafień wielokątów, a biorąc pod uwagę zwykłe zastosowania tego, musisz to zrobićszybko . Dlatego proponuję zrobić to w ten sposób, używając tylko odejmowania, mnożenia, porównywania i. Turn oblicza kierunek zmiany nachylenia między dwoma krawędziami opisanymi przez trzy punkty: 1 oznacza przeciwnie do ruchu wskazówek zegara, 0 oznacza brak skrętu i -1 oznacza zgodnie z ruchem wskazówek zegara.

Ten kod oczekuje punktów wyrażonych jako obiekty GLatLng, ale może być trywialnie przepisany na inne systemy reprezentacji. Porównanie nachylenia zostało znormalizowane na tolerancję epsilon na wilgotne błędy zmiennoprzecinkowe.

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));
}

Przepisałem odpowiedź Petera Wone ' a na jedną funkcję używając x / y zamiast 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));
}

Oto wersja oparta na gist z bardziej zwięzłymi nazwami zmiennych i kawą.

Wersja 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);
}

Wersja 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)

Najpierw znajdź współrzędne przecięcia-tutaj jest to szczegółowo opisane: http://www.mathopenref.com/coordintersection.html

Następnie sprawdź, czy współrzędna x dla przecięcia mieści się w zakresach x dla jednej z linii (lub zrób to samo z współrzędną y, jeśli wolisz), tzn. jeśli xIntersection znajduje się pomiędzy lineAp1x i lineAp2x, to przecinają się.

Dla wszystkich, którzy chcieliby mieć gotowe rozwiązania dla coldfusion, oto, co zaadaptowałem z 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

Funkcje imporantów to ccw i linesIntersect z Javy.awt.geom.Line2D i ja zapisaliśmy je do coldfusion, więc tutaj idź:

<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>

Mam nadzieję, że to pomoże w przystosowaniu się do innych laguages?