Test si deux lignes se croisent-fonction JavaScript
J'ai essayé de rechercher une fonction javascript qui détectera si deux lignes se croisent.
La fonction prendra les valeurs x, y des deux points de départ pour chaque ligne (nous les appellerons ligne A et ligne B).
Retourne true s'ils se croisent, sinon false.
Exemple de la fonction. Je suis heureux si la réponse utilise un objet vectoriel à la place.
Function isIntersect (lineAp1x, lineAp1y, lineAp2x, lineAp2y, lineBp1x, lineBp1y, lineBp2x, lineBp2y)
{
// JavaScript line intersecting test here.
}
Quelques informations de fond: ce code est pour un jeu que j'essaie de faire en toile html5, et fait partie de ma détection de collision.
8 réponses
// 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, une matrice et un déterminant effronté)
Les lignes peuvent être décrites par un vecteur initial, v, et un vecteur de direction, d:
r = v + lambda*d
Nous utilisons un point {[3] } comme vecteur initial et la différence entre eux (c-a,d-b) comme vecteur de direction. De même pour notre deuxième ligne.
Si nos deux lignes se croisent, alors il doit y avoir un point, X, qui est accessible en parcourant une certaine distance, lambda, le long de notre première ligne et également accessible par des unités gamma sur 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ées sous forme matricielle. Nous vérifions que le déterminant est non nul pour voir si L'intersection X existe même.
S'il y a une intersection, alors nous devons vérifier que l'intersection se trouve réellement 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érieur à 0, le l'intersection est avant le premier point.
Par conséquent, 0<lambda<1 && 0<gamma<1 indique que les deux lignes se croisent!
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;
}
La pagewiki j'ai trouvé la réponse.
La réponse de Peter Wone 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 les lignes Co-linéaires dans le code ci-dessous.
Utilisation des directions de rotation pour vérifier l'intersection
Pour expliquer la réponse, regardons quelque chose de commun à chaque intersection de deux lignes. Compte tenu de l'image ci-dessous, nous pouvons voir que P1 pour IP pour P4 tourne dans le sens antihoraire. Nous pouvons voir que ses côtés gratuits tournent dans le sens des aiguilles d'une montre. Maintenant, nous ne savons pas si elle se croise, donc nous ne connaissons pas le point d'intersection. Mais nous pouvons aussi voir que P1 pour P2 pour P4 aussi tourne dans le sens antihoraire. En outre, P1 pour P2 pour P3 tourne dans le sens horaire. Nous pouvons utiliser cette connaissance pour déterminer si deux lignes se croisent ou non.
Exemple D'Intersection
Vous remarquerez que les lignes croisées créent quatre faces qui pointent dans des directions opposées. Comme ils font face à des directions opposées, nous savons que la direction de P1 pour P2 pour P3 tourne un sens différent de celui P1 pour P2 pour P4. Nous savons aussi que P1 pour P3 pour P4 tourne une direction différente de celle P2 pour P3 pour P4.
Exemple De Non-Intersection
Dans cet exemple, vous devriez remarquer qu'en suivant le même modèle pour le test d'intersection, les deux faces tournent dans la même direction. Comme ils font face à la même direction, nous savons qu'ils ne se croisent pas.
Exemple De Code
Donc, nous pouvons l'implémenter dans le code original fourni par 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>Bien qu'il soit utile de pouvoir trouver le point d'intersection, tester pour si les segments de ligne se croisent est le plus souvent utilisé pour les tests de polygones, et compte tenu des applications habituelles de cela, vous devez le fairerapide . Par conséquent, je vous suggère de le faire comme ceci, en utilisant uniquement la soustraction, la multiplication, la comparaison et et. Turn calcule la direction du changement de pente entre les deux arêtes décrites par les trois points: 1 signifie dans le sens antihoraire, 0 signifie pas de virage et -1 signifie dans le sens horaire.
CE code attend des points exprimés en objets GLatLng mais peut être réécrit trivialement à d'autres systèmes de représentation. La comparaison de pente a été normalisée à Epsilon tolérance aux erreurs en virgule flottante humide.
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));
}
J'ai réécrit la réponse de Peter Wone à une seule fonction en utilisant x / y au lieu de 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));
}
Voici une version basée sur cet essentiel avec des noms de variables plus concis, et du café.
Version 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);
}
Version 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)
Tout d'abord, trouvez les coordonnées d'intersection-ici, il est décrit en détail: http://www.mathopenref.com/coordintersection.html
Vérifiez ensuite si la coordonnée X pour l'intersection se situe dans les plages x pour l'une des lignes (ou faites de même avec la coordonnée y, si vous préférez), c'est-à-dire si xIntersection est entre lineAp1x et lineAp2x, alors ils se croisent.
Pour toutes les personnes qui aimeraient avoir une solution prête pour coldfusion, voici ce que j'ai adapté de 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
Les fonctions imporants sont ccw et linesIntersect de java.awt.geom.Line2D et moi les avons écrits dans coldfusion, alors Ici nous aller:
<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>
J'espère que cela peut aider pour s'adapter à d'autres langues?