tipos - Probar si dos líneas se cruzan-función de JavaScript
son líneas que se cortan en un solo punto formando ángulos de 90 grados (8)
Aquí hay una versión basada en gist.github.com/Joncom/e8e8d18ebe7fe55c3894 con algunos nombres de variables más concisos y algo de café.
Versión de 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);
}
Versión 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)
He intentado buscar una función javascript que detectará si dos líneas se intersecan entre sí.
La función tomará los valores x, y de los dos puntos finales de inicio de cada línea (los llamaremos línea A y línea B).
Es devolver verdadero si se intersecan, de lo contrario falso.
Ejemplo de la función. Estoy feliz si la respuesta utiliza un objeto vectorial en su lugar.
Function isIntersect (lineAp1x, lineAp1y, lineAp2x, lineAp2y, lineBp1x, lineBp1y, lineBp2x, lineBp2y)
{
// JavaScript line intersecting test here.
}
Alguna información de fondo: este código es para un juego que estoy tratando de hacer en lienzo html5, y es parte de mi detección de colisiones.
He reescrito la respuesta de Peter Wone a una sola función usando x / y en lugar 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));
}
La respuesta de Peter Wone es una gran solución, pero carece de una explicación. Pasé la última hora más o menos entendiendo cómo funciona y creo que también entiendo lo suficiente como para explicarlo. Vea su respuesta para más detalles: https://.com/a/16725715/697477
También he incluido una solución para las líneas co-lineales en el código a continuación.
Usando direcciones de rotación para verificar la intersección
Para explicar la respuesta, veamos algo común en cada intersección de dos líneas. Dada la imagen de abajo, podemos ver que P 1 a IP a P 4 gira en sentido antihorario. Podemos ver que los lados complementarios giran en sentido horario. Ahora, no sabemos si se cruza, por lo que no sabemos el punto de intersección. Pero también podemos ver que P 1 a P 2 a P 4 también giran en sentido contrario a las agujas del reloj. Además, P 1 a P 2 a P 3 gira en sentido horario. Podemos usar este conocimiento para determinar si dos líneas se intersecan o no.
Ejemplo de intersección
Notará que las líneas que se cruzan crean cuatro caras que apuntan en direcciones opuestas. Como se enfrentan a direcciones opuestas, sabemos que la dirección de P 1 a P 2 a P 3 gira en una dirección diferente a P 1 a P 2 a P 4 . También sabemos que P 1 a P 3 a P 4 gira en una dirección diferente a P 2 a P 3 a P 4 .
Ejemplo de no intersección
En este ejemplo, debe observar que siguiendo el mismo patrón para la prueba de intersección, las dos caras giran en la misma dirección. Como se enfrentan en la misma dirección, sabemos que no se cruzan.
Ejemplo de código
Por lo tanto, podemos implementar esto en el código original suministrado por 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>
Para todas las personas que deseen tener una solución lista para la fusión en frío, esto es lo que 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
Las funciones importantes son ccw y linesIntersect de java.awt.geom.Line2D y las escribí en ColdFusion, así que aquí vamos:
<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>
Espero que esto pueda ayudar para adaptarse a otros idiomas.
Primero, encuentre las coordenadas de la intersección: aquí se describe en detalle: http://www.mathopenref.com/coordintersection.html
Luego, verifique si la coordenada x para la intersección cae dentro de los rangos x para una de las líneas (o haga lo mismo con la coordenada y, si lo prefiere), es decir, si xIntersection se encuentra entre lineAp1x y lineAp2x, entonces se intersecan.
Si bien es útil poder encontrar el punto de intersección, la prueba para determinar si la intersección de los segmentos de línea se usa con mayor frecuencia para las pruebas de impacto de polígonos, y dadas las aplicaciones habituales de eso, debe hacerlo rápidamente . Por lo tanto, te sugiero que lo hagas de esta manera, usando solo resta, multiplicación, comparación y AND. Turn calcula la dirección del cambio en la pendiente entre los dos bordes descritos por los tres puntos: 1 significa en sentido antihorario, 0 significa sin giro y -1 significa en sentido horario.
Este código espera puntos expresados como objetos GLatLng pero se pueden reescribir trivialmente en otros sistemas de representación. La comparación de la pendiente se ha normalizado a la tolerancia de epsilon a los errores de punto flotante húmedo.
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));
}
// 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);
}
};
Explicación: (vectores, una matriz y un determinante descarado)
Las líneas se pueden describir mediante un vector inicial, v, y un vector de dirección, d:
r = v + lambda*d
Utilizamos un punto (a,b) como el vector inicial y la diferencia entre ellos (ca,db) como el vector de dirección. Igualmente para nuestra segunda línea.
Si nuestras dos líneas se intersecan, entonces debe haber un punto, X, al que se puede llegar viajando una cierta distancia, lambda, a lo largo de nuestra primera línea y también que se puede alcanzar mediante unidades gamma de viaje a lo largo de nuestra segunda línea. Esto nos da dos ecuaciones simultáneas para las coordenadas de X:
X = v1 + lambda*d1
X = v2 + gamma *d2
Estas ecuaciones se pueden representar en forma de matriz. Verificamos que el determinante sea distinto de cero para ver si existe la intersección X.
Si hay una intersección, entonces debemos verificar que la intersección realmente se encuentra entre ambos conjuntos de puntos. Si lambda es mayor que 1, la intersección está más allá del segundo punto. Si lambda es menor que 0, la intersección es anterior al primer punto.
Por lo tanto, 0<lambda<1 && 0<gamma<1 indica que las dos líneas se cruzan.
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 página wiki que encontré la respuesta.