Tester si deux droites se coupent - fonction JavaScript

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

Explication: (vecteurs, matrices et un coup de déterminant)

Lignes peut être décrit par certains initial vecteur v, et un vecteur de direction, d:

r = v + lambda*d 

Nous utilisons un point (a,b) comme le premier vecteur et la différence entre eux (c-a,d-b) comme le vecteur de direction. De même pour notre deuxième ligne.

Si nos deux lignes se croisent, alors il doit y avoir un point de X, qui est accessible en voyageant à une certaine distance, lambda, le long de notre première ligne et également accessible par le voyage gamma unités le long de notre deuxième ligne. Cela nous donne deux équations simultanées pour les coordonnées de X:

X = v1 + lambda*d1 
X = v2 + gamma *d2

Ces équations peuvent être représentés sous forme de matrice. Nous vérifions que le déterminant est non nul pour voir si l'intersection de X existe même.

Si il y a une intersection, il faut vérifier que l'intersection réalité se situe entre les deux ensembles de points. Si lambda est supérieur à 1, l'intersection est au-delà du deuxième point. Si lambda est inférieure à 0, l'intersection est avant le premier point.

Donc, 0<lambda<1 && 0<gamma<1 indique que les deux lignes se croisent!

Peter Wone réponse est une excellente solution, mais il manque une explication. J'ai passé la dernière heure à comprendre comment il fonctionne et pense que je comprends assez pour l'expliquer ainsi. Voir sa réponse pour plus de détails: https://stackoverflow.com/a/16725715/697477

J'ai également inclus une solution pour le co-linéaire des lignes dans le code ci-dessous.

À l'aide de Rotation des Directions de vérifier pour l'intersection

Pour expliquer la réponse, regardez quelque chose de commun à propos de chaque point d'intersection de deux lignes. Compte tenu de l'image ci-dessous, nous pouvons voir que P₁ à IP à P₄ tourne dans le sens antihoraire. Nous pouvons voir que c'est gratuit côtés tourner dans le sens horaire. Maintenant, nous ne savons pas si elle croise, de sorte que nous ne savons pas le point d'intersection. Mais nous pouvons aussi voir que P₁ à P₂ à P₄ aussi tourne dans le sens antihoraire. En outre, P₁ à P₂ à P₃ tourne dans le sens horaire. Nous pouvons utiliser ces informations pour déterminer si deux droites se coupent ou pas.

Exemple D'Intersection De

Vous remarquerez que l'intersection des lignes de créer quatre faces point des directions opposées. Depuis ils font face à des directions opposées, nous savons que la direction de P₁ à P₂ à P₃ tourne un sens différent de celui P₁ à P₂ à P₄. Nous savons aussi que P₁ à P₃ à P₄ tourne une direction différente de celle P₂ à P₃ à P₄.

Non-Intersection Exemple

Dans cet exemple, vous devriez remarquer que, suivant le même schéma pour l'intersection de test, les deux faces de tourner dans la même direction. Depuis ils font face à la même direction, nous savons qu'ils ne se croisent pas.

Exemple De Code

Donc, nous pouvons mettre en œuvre dans le code d'origine fourni par Peter Wone.

JS:

//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();

HTML:

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

J'ai réécrit Peter Wone, la réponse à une seule fonction à l'aide de x/y, au lieu de la 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));
}

Tout d'abord, trouver l'intersection des coordonnées - là, il est décrit en détail:
http://www.mathopenref.com/coordintersection.html

De vérifier ensuite si la coordonnée x de l'intersection entre dans le x varie de l'une des lignes (ou de faire de même avec la coordonnée y, si vous préférez),
c'est à dire si xIntersection est entre lineAp1x et lineAp2x, alors qu'ils se croisent.

Utiliser le pythageorum theorum pour trouver la distance entre les 2 objets et ajouter le rayon Pythageorum Theorum Formule De La Distance De