geometry - rectas - interseccion de segmentos c++

¿Cómo detectas dónde se cruzan dos segmentos de línea?

Question

¿Cómo puedo determinar si dos líneas se intersecan o no, y si lo hacen, en qué punto x, y?

Answer 1

Pregunta C: ¿Cómo detecta si dos segmentos de línea se intersecan o no?

Busqué el mismo tema y no me gustaron las respuestas. Así que he escrito un artículo que explica muy detalladamente cómo verificar si dos segmentos de línea se cruzan con muchas imágenes. Hay código Java completo (y probado).

Aquí está el artículo, recortado a las partes más importantes:

El algoritmo, que verifica si el segmento de línea a se cruza con el segmento de línea b, se ve así:

¿Qué son los cuadros delimitadores? Aquí hay dos cuadros delimitadores de dos segmentos de línea:

Si ambos cuadros delimitadores tienen una intersección, mueva el segmento de línea a para que un punto esté en (0 | 0). Ahora tienes una línea a través del origen definido por a. Ahora mueva el segmento de línea b de la misma manera y verifique si los nuevos puntos del segmento de línea b están en diferentes lados de la línea a. Si este es el caso, revísalo al revés. Si este es también el caso, los segmentos de línea se intersecan. Si no, no se entrecruzan.

Pregunta A: ¿Dónde se intersecan dos segmentos de línea?

Usted sabe que dos segmentos de línea a y b se intersecan. Si no lo sabe, verifíquelo con las herramientas que le proporcioné en la "Pregunta C".

Ahora puede pasar por algunos casos y obtener la solución con matemáticas de séptimo grado (consulte el código y el ejemplo interactivo ).

Pregunta B: ¿Cómo detectas si dos líneas se intersecan o no?

Digamos que tu punto A = (x1, y1) , punto B = (x2, y2) , C = (x_3, y_3) , D = (x_4, y_4) . Su primera línea está definida por AB (con A! = B), y la segunda por CD (con C! = D).

function doLinesIntersect(AB, CD) {
if (x1 == x2) {
return !(x3 == x4 && x1 != x3);
} else if (x3 == x4) {
return true;
} else {
// Both lines are not parallel to the y-axis
m1 = (y1-y2)/(x1-x2);
m2 = (y3-y4)/(x3-x4);
return m1 != m2;
}
}

Pregunta D: ¿Dónde se intersecan dos líneas?

Verifique con la pregunta B si se intersecan.

Las líneas a y b están definidas por dos puntos para cada línea. Básicamente puede aplicar la misma lógica que se utilizó en la pregunta A.

Answer 2

C y Objective-C

Basado en la respuesta de Gareth Rees.

const AGKLine AGKLineZero = (AGKLine){(CGPoint){0.0, 0.0}, (CGPoint){0.0, 0.0}};
AGKLine AGKLineMake(CGPoint start, CGPoint end)
{
return (AGKLine){start, end};
}
double AGKLineLength(AGKLine l)
{
return CGPointLengthBetween_AGK(l.start, l.end);
}
BOOL AGKLineIntersection(AGKLine l1, AGKLine l2, CGPoint *out_pointOfIntersection)
{
// http://.com/a/565282/202451
CGPoint p = l1.start;
CGPoint q = l2.start;
CGPoint r = CGPointSubtract_AGK(l1.end, l1.start);
CGPoint s = CGPointSubtract_AGK(l2.end, l2.start);
double s_r_crossProduct = CGPointCrossProductZComponent_AGK(r, s);
double t = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), s) / s_r_crossProduct;
double u = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), r) / s_r_crossProduct;
if(t < 0 || t > 1.0 || u < 0 || u > 1.0)
{
if(out_pointOfIntersection != NULL)
{
*out_pointOfIntersection = CGPointZero;
}
return NO;
}
else
{
if(out_pointOfIntersection != NULL)
{
CGPoint i = CGPointAdd_AGK(p, CGPointMultiply_AGK(r, t));
*out_pointOfIntersection = i;
}
return YES;
}
}
CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
return v1.x * v2.y - v1.y * v2.x;
}
CGPoint CGPointSubtract_AGK(CGPoint p1, CGPoint p2)
{
return (CGPoint){p1.x - p2.x, p1.y - p2.y};
}
CGPoint CGPointAdd_AGK(CGPoint p1, CGPoint p2)
{
return (CGPoint){p1.x + p2.x, p1.y + p2.y};
}
CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
return v1.x * v2.y - v1.y * v2.x;
}
CGPoint CGPointMultiply_AGK(CGPoint p1, CGFloat factor)
{
return (CGPoint){p1.x * factor, p1.y * factor};
}

Muchas de las funciones y estructuras son privadas, pero debería ser muy fácil saber lo que sucede. Esto es público en este repositorio https://github.com/hfossli/AGGeometryKit/

Answer 3

Aquí hay una mejora en la respuesta de Gavin. La solución de marcp también es similar, pero ninguna pospone la división.

Esto en realidad también resulta ser una aplicación práctica de la respuesta de Gareth Rees, porque el equivalente de producto cruzado en 2D es el producto perp-dot, que es el código que usa tres de estos. Cambiar a 3D y utilizar el producto cruzado, al interpolar tanto s como t al final, da como resultado los dos puntos más cercanos entre las líneas en 3D. De todos modos, la solución 2D:

int get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y,
float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
float s02_x, s02_y, s10_x, s10_y, s32_x, s32_y, s_numer, t_numer, denom, t;
s10_x = p1_x - p0_x;
s10_y = p1_y - p0_y;
s32_x = p3_x - p2_x;
s32_y = p3_y - p2_y;
denom = s10_x * s32_y - s32_x * s10_y;
if (denom == 0)
return 0; // Collinear
bool denomPositive = denom > 0;
s02_x = p0_x - p2_x;
s02_y = p0_y - p2_y;
s_numer = s10_x * s02_y - s10_y * s02_x;
if ((s_numer < 0) == denomPositive)
return 0; // No collision
t_numer = s32_x * s02_y - s32_y * s02_x;
if ((t_numer < 0) == denomPositive)
return 0; // No collision
if (((s_numer > denom) == denomPositive) || ((t_numer > denom) == denomPositive))
return 0; // No collision
// Collision detected
t = t_numer / denom;
if (i_x != NULL)
*i_x = p0_x + (t * s10_x);
if (i_y != NULL)
*i_y = p0_y + (t * s10_y);
return 1;
}

Básicamente, pospone la división hasta el último momento y mueve la mayoría de las pruebas hasta antes de que se realicen ciertos cálculos, agregando así salidas anticipadas. Finalmente, también evita el caso de división por cero que se produce cuando las líneas son paralelas.

También es posible que desee considerar utilizar una prueba de épsilon en lugar de una comparación con cero. Las líneas que están muy cerca del paralelo pueden producir resultados que están ligeramente apagados. Esto no es un error, es una limitación con las matemáticas de punto flotante.

Answer 4

El problema se reduce a esta pregunta: ¿Se intersecan dos líneas de A a B y de C a D? Luego puedes preguntarlo cuatro veces (entre la línea y cada uno de los cuatro lados del rectángulo).

Aquí está el vector de matemáticas para hacerlo. Supongo que la línea de A a B es la línea en cuestión y la línea de C a D es una de las líneas rectangulares. Mi notación es que Ax es la "coordenada x de A" y Cy es la "coordenada y" de C. Y " * " significa punto-producto, por ejemplo, A*B = Ax*Bx + Ay*By .

E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy )
P = ( -Ey, Ex )
h = ( (A-C) * P ) / ( F * P )

Este número h es la clave. Si h está entre 0 y 1 , las líneas se intersecan, de lo contrario no lo hacen. Si F*P es cero, por supuesto que no puede realizar el cálculo, pero en este caso las líneas son paralelas y, por lo tanto, solo se intersecan en los casos obvios.

El punto exacto de intersección es C + F*h .

Más diversión:

Si h es exactamente 0 o 1 las líneas se tocan en un punto final. Puede considerar esto como una "intersección" o no como mejor le parezca.

Específicamente, h es cuánto tienes que multiplicar la longitud de la línea para tocar exactamente la otra línea.

Por lo tanto, si h<0 , significa que la línea del rectángulo está "detrás" de la línea dada (con "la dirección" es "de A a B"), y si h>1 la línea del rectángulo está "al frente" de la línea dada .

Derivación:

A y C son vectores que apuntan al inicio de la línea; E y F son los vectores de los extremos de A y C que forman la línea.

Para cualquiera de las dos líneas no paralelas en el plano, debe haber exactamente un par de escalar g y h modo que esta ecuación sea válida:

A + E*g = C + F*h

¿Por qué? Debido a que dos líneas no paralelas deben intersecarse, lo que significa que puede escalar ambas líneas en cierta cantidad cada una y tocarse entre sí.

(¡ Al principio, esto parece una ecuación con dos incógnitas! Pero no lo es si consideras que se trata de una ecuación vectorial en 2D, lo que significa que en realidad es un par de ecuaciones en x e y ).

Tenemos que eliminar una de estas variables. Una forma fácil es hacer que el término E cero. Para hacer eso, toma el producto puntual de ambos lados de la ecuación usando un vector que se pondrá a cero con E. Ese vector al que llamé P arriba, e hice la transformación obvia de E.

Ahora tienes:

A*P = C*P + F*P*h
(A-C)*P = (F*P)*h
( (A-C)*P ) / (F*P) = h

Answer 5

Encontrar la intersección correcta de dos segmentos de línea es una tarea no trivial con muchos casos de borde. Aquí hay una solución bien documentada, en funcionamiento y probada en Java.

En esencia, hay tres cosas que pueden suceder al encontrar la intersección de dos segmentos de línea:

1. Los segmentos no se intersecan.

2. Hay un punto de intersección único

3. La intersección es otro segmento.

NOTA : En el código, asumo que un segmento de línea (x1, y1), (x2, y2) con x1 = x2 e y1 = y2 es un segmento de línea válido. Hablando matemáticamente, un segmento de línea consta de puntos distintos, pero estoy permitiendo que los segmentos sean puntos en esta implementación para completarlos.

El código se toma de mi repositorio github

/**
* This snippet finds the intersection of two line segments.
* The intersection may either be empty, a single point or the
* intersection is a subsegment there''s an overlap.
*/
import static java.lang.Math.abs;
import static java.lang.Math.max;
import static java.lang.Math.min;
import java.util.ArrayList;
import java.util.List;
public class LineSegmentLineSegmentIntersection {
// Small epsilon used for double value comparison.
private static final double EPS = 1e-5;
// 2D Point class.
public static class Pt {
double x, y;
public Pt(double x, double y) {
this.x = x;
this.y = y;
}
public boolean equals(Pt pt) {
return abs(x - pt.x) < EPS && abs(y - pt.y) < EPS;
}
}
// Finds the orientation of point ''c'' relative to the line segment (a, b)
// Returns 0 if all three points are collinear.
// Returns -1 if ''c'' is clockwise to segment (a, b), i.e right of line formed by the segment.
// Returns +1 if ''c'' is counter clockwise to segment (a, b), i.e left of line
// formed by the segment.
public static int orientation(Pt a, Pt b, Pt c) {
double value = (b.y - a.y) * (c.x - b.x) -
(b.x - a.x) * (c.y - b.y);
if (abs(value) < EPS) return 0;
return (value > 0) ? -1 : +1;
}
// Tests whether point ''c'' is on the line segment (a, b).
// Ensure first that point c is collinear to segment (a, b) and
// then check whether c is within the rectangle formed by (a, b)
public static boolean pointOnLine(Pt a, Pt b, Pt c) {
return orientation(a, b, c) == 0 &&
min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x) &&
min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
}
// Determines whether two segments intersect.
public static boolean segmentsIntersect(Pt p1, Pt p2, Pt p3, Pt p4) {
// Get the orientation of points p3 and p4 in relation
// to the line segment (p1, p2)
int o1 = orientation(p1, p2, p3);
int o2 = orientation(p1, p2, p4);
int o3 = orientation(p3, p4, p1);
int o4 = orientation(p3, p4, p2);
// If the points p1, p2 are on opposite sides of the infinite
// line formed by (p3, p4) and conversly p3, p4 are on opposite
// sides of the infinite line formed by (p1, p2) then there is
// an intersection.
if (o1 != o2 && o3 != o4) return true;
// Collinear special cases (perhaps these if checks can be simplified?)
if (o1 == 0 && pointOnLine(p1, p2, p3)) return true;
if (o2 == 0 && pointOnLine(p1, p2, p4)) return true;
if (o3 == 0 && pointOnLine(p3, p4, p1)) return true;
if (o4 == 0 && pointOnLine(p3, p4, p2)) return true;
return false;
}
public static List<Pt> getCommonEndpoints(Pt p1, Pt p2, Pt p3, Pt p4) {
List<Pt> points = new ArrayList<>();
if (p1.equals(p3)) {
points.add(p1);
if (p2.equals(p4)) points.add(p2);
} else if (p1.equals(p4)) {
points.add(p1);
if (p2.equals(p3)) points.add(p2);
} else if (p2.equals(p3)) {
points.add(p2);
if (p1.equals(p4)) points.add(p1);
} else if (p2.equals(p4)) {
points.add(p2);
if (p1.equals(p3)) points.add(p1);
}
return points;
}
// Finds the intersection point(s) of two line segments. Unlike regular line
// segments, segments which are points (x1 = x2 and y1 = y2) are allowed.
public static Pt[] lineSegmentLineSegmentIntersection(Pt p1, Pt p2, Pt p3, Pt p4) {
// No intersection.
if (!segmentsIntersect(p1, p2, p3, p4)) return new Pt[]{};
// Both segments are a single point.
if (p1.equals(p2) && p2.equals(p3) && p3.equals(p4))
return new Pt[]{p1};
List<Pt> endpoints = getCommonEndpoints(p1, p2, p3, p4);
int n = endpoints.size();
// One of the line segments is an intersecting single point.
// NOTE: checking only n == 1 is insufficient to return early
// because the solution might be a sub segment.
boolean singleton = p1.equals(p2) || p3.equals(p4);
if (n == 1 && singleton) return new Pt[]{endpoints.get(0)};
// Segments are equal.
if (n == 2) return new Pt[]{endpoints.get(0), endpoints.get(1)};
boolean collinearSegments = (orientation(p1, p2, p3) == 0) &&
(orientation(p1, p2, p4) == 0);
// The intersection will be a sub-segment of the two
// segments since they overlap each other.
if (collinearSegments) {
// Segment #2 is enclosed in segment #1
if (pointOnLine(p1, p2, p3) && pointOnLine(p1, p2, p4))
return new Pt[]{p3, p4};
// Segment #1 is enclosed in segment #2
if (pointOnLine(p3, p4, p1) && pointOnLine(p3, p4, p2))
return new Pt[]{p1, p2};
// The subsegment is part of segment #1 and part of segment #2.
// Find the middle points which correspond to this segment.
Pt midPoint1 = pointOnLine(p1, p2, p3) ? p3 : p4;
Pt midPoint2 = pointOnLine(p3, p4, p1) ? p1 : p2;
// There is actually only one middle point!
if (midPoint1.equals(midPoint2)) return new Pt[]{midPoint1};
return new Pt[]{midPoint1, midPoint2};
}
/* Beyond this point there is a unique intersection point. */
// Segment #1 is a vertical line.
if (abs(p1.x - p2.x) < EPS) {
double m = (p4.y - p3.y) / (p4.x - p3.x);
double b = p3.y - m * p3.x;
return new Pt[]{new Pt(p1.x, m * p1.x + b)};
}
// Segment #2 is a vertical line.
if (abs(p3.x - p4.x) < EPS) {
double m = (p2.y - p1.y) / (p2.x - p1.x);
double b = p1.y - m * p1.x;
return new Pt[]{new Pt(p3.x, m * p3.x + b)};
}
double m1 = (p2.y - p1.y) / (p2.x - p1.x);
double m2 = (p4.y - p3.y) / (p4.x - p3.x);
double b1 = p1.y - m1 * p1.x;
double b2 = p3.y - m2 * p3.x;
double x = (b2 - b1) / (m1 - m2);
double y = (m1 * b2 - m2 * b1) / (m1 - m2);
return new Pt[]{new Pt(x, y)};
}
}

Aquí hay un ejemplo de uso simple:

 public static void main(String[] args) {
// Segment #1 is (p1, p2), segment #2 is (p3, p4)
Pt p1, p2, p3, p4;
p1 = new Pt(-2, 4); p2 = new Pt(3, 3);
p3 = new Pt(0, 0); p4 = new Pt(2, 4);
Pt[] points = lineSegmentLineSegmentIntersection(p1, p2, p3, p4);
Pt point = points[0];
// Prints: (1.636, 3.273)
System.out.printf("(%.3f, %.3f)/n", point.x, point.y);
p1 = new Pt(-10, 0); p2 = new Pt(+10, 0);
p3 = new Pt(-5, 0); p4 = new Pt(+5, 0);
points = lineSegmentLineSegmentIntersection(p1, p2, p3, p4);
Pt point1 = points[0], point2 = points[1];
// Prints: (-5.000, 0.000) (5.000, 0.000)
System.out.printf("(%.3f, %.3f) (%.3f, %.3f)/n", point1.x, point1.y, point2.x, point2.y);
}

Answer 6

Esto está funcionando bien para mí. Tomado de here .

 // calculates intersection and checks for parallel lines.
// also checks that the intersection point is actually on
// the line segment p1-p2
Point findIntersection(Point p1,Point p2,
Point p3,Point p4) {
float xD1,yD1,xD2,yD2,xD3,yD3;
float dot,deg,len1,len2;
float segmentLen1,segmentLen2;
float ua,ub,div;
// calculate differences
xD1=p2.x-p1.x;
xD2=p4.x-p3.x;
yD1=p2.y-p1.y;
yD2=p4.y-p3.y;
xD3=p1.x-p3.x;
yD3=p1.y-p3.y;
// calculate the lengths of the two lines
len1=sqrt(xD1*xD1+yD1*yD1);
len2=sqrt(xD2*xD2+yD2*yD2);
// calculate angle between the two lines.
dot=(xD1*xD2+yD1*yD2); // dot product
deg=dot/(len1*len2);
// if abs(angle)==1 then the lines are parallell,
// so no intersection is possible
if(abs(deg)==1) return null;
// find intersection Pt between two lines
Point pt=new Point(0,0);
div=yD2*xD1-xD2*yD1;
ua=(xD2*yD3-yD2*xD3)/div;
ub=(xD1*yD3-yD1*xD3)/div;
pt.x=p1.x+ua*xD1;
pt.y=p1.y+ua*yD1;
// calculate the combined length of the two segments
// between Pt-p1 and Pt-p2
xD1=pt.x-p1.x;
xD2=pt.x-p2.x;
yD1=pt.y-p1.y;
yD2=pt.y-p2.y;
segmentLen1=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);
// calculate the combined length of the two segments
// between Pt-p3 and Pt-p4
xD1=pt.x-p3.x;
xD2=pt.x-p4.x;
yD1=pt.y-p3.y;
yD2=pt.y-p4.y;
segmentLen2=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);
// if the lengths of both sets of segments are the same as
// the lenghts of the two lines the point is actually
// on the line segment.
// if the point isn’t on the line, return null
if(abs(len1-segmentLen1)>0.01 || abs(len2-segmentLen2)>0.01)
return null;
// return the valid intersection
return pt;
}
class Point{
float x,y;
Point(float x, float y){
this.x = x;
this.y = y;
}
void set(float x, float y){
this.x = x;
this.y = y;
}
}

Answer 7

FWIW, la siguiente función (en C) detecta las intersecciones de línea y determina el punto de intersección. Se basa en un algoritmo en " Trucos de los gurús de la programación de juegos de Windows " de Andre LeMothe. No es diferente de algunos de los algoritmos en otras respuestas (por ejemplo, de Gareth). LeMothe luego usa la Regla de Cramer (no me pida) para resolver las ecuaciones.

Puedo dar fe de que funciona en mi débil clon de asteroides, y parece tratar correctamente los casos de borde descritos en otras respuestas por Elemental, Dan y Wodzu. Probablemente también sea más rápido que el código publicado por KingNestor porque es todo multiplicación y división, ¡no raíces cuadradas!

Supongo que existe cierto potencial de división por cero, aunque no ha sido un problema en mi caso. Lo suficientemente fácil de modificar para evitar el accidente de todos modos.

// Returns 1 if the lines intersect, otherwise 0. In addition, if the lines
// intersect the intersection point may be stored in the floats i_x and i_y.
char get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y,
float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
float s1_x, s1_y, s2_x, s2_y;
s1_x = p1_x - p0_x; s1_y = p1_y - p0_y;
s2_x = p3_x - p2_x; s2_y = p3_y - p2_y;
float s, t;
s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);
if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
{
// Collision detected
if (i_x != NULL)
*i_x = p0_x + (t * s1_x);
if (i_y != NULL)
*i_y = p0_y + (t * s1_y);
return 1;
}
return 0; // No collision
}

Por cierto, debo decir que en el libro de LeMothe, aunque aparentemente hace bien el algoritmo, el ejemplo concreto muestra que se enchufa en los números incorrectos y hace los cálculos de manera incorrecta. Por ejemplo:

(4 * (4 - 1) + 12 * (7 - 1)) / (17 * 4 + 12 * 10)

= 844 / 0.88

= 0.44

Eso me confundió por horas . :(

Answer 8

Hay muchas soluciones disponibles arriba, pero creo que la solución que aparece a continuación es bastante simple y fácil de entender.

Dos segmentos Vector AB y Vector CD se intersecan si y solo si

1. Los puntos finales a y b están en lados opuestos del segmento CD.
2. Los puntos finales c y d están en el lado opuesto del segmento AB.

Más específicamente, a y b están en el lado opuesto del segmento CD si y solo si uno de los dos triples a, c, d y b, c, d está en el orden contrario a las agujas del reloj.

Intersect(a, b, c, d)
if CCW(a, c, d) == CCW(b, c, d)
return false;
else if CCW(a, b, c) == CCW(a, b, d)
return false;
else
return true;

Aquí CCW representa en sentido contrario a las agujas del reloj que devuelve verdadero / falso según la orientación de los puntos.

Fuente: http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf Página 2

Answer 9

Hay un buen enfoque para este problema que utiliza productos cruzados vectoriales. Defina el producto cruzado vectorial bidimensional v × w para que sea v _x w _y - v _y w _x .

Supongamos que los dos segmentos de línea van de p a p + r y de q a q + s . Luego, cualquier punto en la primera línea se puede representar como p + t r (para un parámetro escalar t ) y cualquier punto en la segunda línea como q + u s (para un parámetro escalar u ).

Las dos líneas se intersecan si podemos encontrar t y u de tal manera que:

p + t r = q + u s

Cruza ambos lados con s , consiguiendo

( p + t r ) × s = ( q + u s ) × s

Y como s × s = 0, esto significa

t ( r × s ) = ( q - p ) × s

Y por lo tanto, resolviendo para t :

t = ( q - p ) × s / ( r × s )

De la misma manera, podemos resolver para u :

( p + t r ) × r = ( q + u s ) × r

u ( s × r ) = ( p - q ) × r

u = ( p - q ) × r / ( s × r )

Para reducir el número de pasos de cómputo, es conveniente reescribirlo de la siguiente manera (recordando que s × r = - r × s ):

u = ( q - p ) × r / ( r × s )

Ahora hay cuatro casos:

1. Si r × s = 0 y ( q - p ) × r = 0, entonces las dos líneas son colineales.

   En este caso, exprese los puntos finales del segundo segmento ( q y q + s ) en términos de la ecuación del primer segmento de línea ( p + t r ):

   t ₀ = ( q - p ) · r / ( r · r )

   t ₁ = ( q + s - p ) · r / ( r · r ) = t ₀ + s · r / ( r · r )

   Si el intervalo entre t ₀ y t ₁ intersecta el intervalo [0, 1], entonces los segmentos de línea son colineales y se superponen; De lo contrario son colineales y desunidos.

   Tenga en cuenta que si s y r apuntan en direcciones opuestas, entonces s · r <0 y, por lo tanto, el intervalo a verificar es [ t ₁ , t ₀ ] en lugar de [ t ₀ , t ₁ ].

2. Si r × s = 0 y ( q - p ) × r ≠ 0, entonces las dos líneas son paralelas y no se intersecan.

3. Si r × s ≠ 0 y 0 ≤ t ≤ 1 y 0 ≤ u ≤ 1, los dos segmentos de línea se encuentran en el punto p + t r = q + u s .

4. De lo contrario, los dos segmentos de línea no son paralelos, pero no se intersecan.

Crédito: este método es la especialización bidimensional del algoritmo de intersección de líneas 3D del artículo "Intersección de dos líneas en tres espacios" por Ronald Goldman, publicado en Graphics Gems , página 304. En tres dimensiones, el caso habitual es que las líneas son sesgadas (ni paralelas ni intersecantes), en cuyo caso el método proporciona los puntos de acercamiento más cercano de las dos líneas.

Answer 10

He intentado implementar el algoritmo tan elegantemente descrito anteriormente por Jason; Desafortunadamente, mientras trabajaba con las matemáticas en la depuración, encontré muchos casos en los que no funciona.

Por ejemplo, considere los puntos A (10,10) B (20,20) C (10,1) D (1,10) da h = .5 y, sin embargo, queda claro por el examen que estos segmentos no están cerca de cada uno otro.

Al graficar esto, queda claro que los criterios 0 <h <1 solo indican que el punto de intercepción estaría en el CD si existiera, pero no le dice a nadie si ese punto se encuentra en AB. Para asegurarse de que haya un punto de cruce, debe realizar el cálculo simétrico para la variable gy el requisito para la intercepción es: 0 <g <1 Y 0 <h <1

Answer 11

La respuesta una vez aceptada aquí es incorrecta (desde entonces no ha sido aceptada, así que ¡hurra!). No elimina correctamente todas las no intersecciones. Trivialmente puede parecer que funciona pero puede fallar, especialmente en el caso de que 0 y 1 se consideren válidos para h.

Considere el siguiente caso:

Líneas en (4,1) - (5,1) y (0,0) - (0,2)

Estas son líneas perpendiculares que claramente no se superponen.

A = (4,1)
B = (5,1)
C = (0,0)
D = (0,2)
E = (5,1) - (4,1) = (- 1,0)
F = (0,2) - (0,0) = (0, -2)
P = (0,1)
h = ((4,1) - (0,0)) punto (0,1) / ((0, -2) punto (0,1)) = 0

De acuerdo con la respuesta anterior, estos dos segmentos de línea se encuentran en un punto final (valores de 0 y 1). Ese punto final sería:

(0,0) + (0, -2) * 0 = (0,0)

Entonces, aparentemente los dos segmentos de línea se encuentran en (0,0), que está en el CD de la línea, pero no en la línea AB. Entonces, ¿qué va mal? La respuesta es que los valores de 0 y 1 no son válidos y, a veces, HAPPEN para predecir correctamente la intersección del punto final. Cuando la extensión de una línea (pero no la otra) cumple con el segmento de línea, el algoritmo predice una intersección de segmentos de línea, pero esto no es correcto. Me imagino que al probar con AB vs CD y luego con CD vs AB, este problema se eliminaría. Solo si ambos caen entre 0 y 1 inclusive se puede decir que se intersectan.

Recomiendo usar el método de producto cruzado vectorial si debe predecir los puntos finales.

-Dan

Answer 12

Solo quería mencionar que se puede encontrar una buena explicación y una solución explícita en la serie de Recetas numéricas. Tengo la tercera edición y la respuesta está en la página 1117, sección 21.4. Otra solución con una nomenclatura diferente se puede encontrar en un artículo de Marina Gavrilova Reliable Line Section Intersection Testing . Su solución es, en mi opinión, un poco más simple.

Mi implementación es a continuación:

bool NuGeometry::IsBetween(const double& x0, const double& x, const double& x1){
return (x >= x0) && (x <= x1);
}
bool NuGeometry::FindIntersection(const double& x0, const double& y0,
const double& x1, const double& y1,
const double& a0, const double& b0,
const double& a1, const double& b1,
double& xy, double& ab) {
// four endpoints are x0, y0 & x1,y1 & a0,b0 & a1,b1
// returned values xy and ab are the fractional distance along xy and ab
// and are only defined when the result is true
bool partial = false;
double denom = (b0 - b1) * (x0 - x1) - (y0 - y1) * (a0 - a1);
if (denom == 0) {
xy = -1;
ab = -1;
} else {
xy = (a0 * (y1 - b1) + a1 * (b0 - y1) + x1 * (b1 - b0)) / denom;
partial = NuGeometry::IsBetween(0, xy, 1);
if (partial) {
// no point calculating this unless xy is between 0 & 1
ab = (y1 * (x0 - a1) + b1 * (x1 - x0) + y0 * (a1 - x1)) / denom;
}
}
if ( partial && NuGeometry::IsBetween(0, ab, 1)) {
ab = 1-ab;
xy = 1-xy;
return true;
} else return false;
}

Answer 13

Versión de Python de la respuesta de iMalc:

def find_intersection( p0, p1, p2, p3 ) :
s10_x = p1[0] - p0[0]
s10_y = p1[1] - p0[1]
s32_x = p3[0] - p2[0]
s32_y = p3[1] - p2[1]
denom = s10_x * s32_y - s32_x * s10_y
if denom == 0 : return None # collinear
denom_is_positive = denom > 0
s02_x = p0[0] - p2[0]
s02_y = p0[1] - p2[1]
s_numer = s10_x * s02_y - s10_y * s02_x
if (s_numer < 0) == denom_is_positive : return None # no collision
t_numer = s32_x * s02_y - s32_y * s02_x
if (t_numer < 0) == denom_is_positive : return None # no collision
if (s_numer > denom) == denom_is_positive or (t_numer > denom) == denom_is_positive : return None # no collision
# collision detected
t = t_numer / denom
intersection_point = [ p0[0] + (t * s10_x), p0[1] + (t * s10_y) ]
return intersection_point

Answer 14

Un programa en C ++ para verificar si dos segmentos de línea dados se intersecan

#include <iostream>
using namespace std;
struct Point
{
int x;
int y;
};
// Given three colinear points p, q, r, the function checks if
// point q lies on line segment ''pr''
bool onSegment(Point p, Point q, Point r)
{
if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
return true;
return false;
}
// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p, Point q, Point r)
{
// See 10th slides from following link for derivation of the formula
// http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
int val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);
if (val == 0) return 0; // colinear
return (val > 0)? 1: 2; // clock or counterclock wise
}
// The main function that returns true if line segment ''p1q1''
// and ''p2q2'' intersect.
bool doIntersect(Point p1, Point q1, Point p2, Point q2)
{
// Find the four orientations needed for general and
// special cases
int o1 = orientation(p1, q1, p2);
int o2 = orientation(p1, q1, q2);
int o3 = orientation(p2, q2, p1);
int o4 = orientation(p2, q2, q1);
// General case
if (o1 != o2 && o3 != o4)
return true;
// Special Cases
// p1, q1 and p2 are colinear and p2 lies on segment p1q1
if (o1 == 0 && onSegment(p1, p2, q1)) return true;
// p1, q1 and p2 are colinear and q2 lies on segment p1q1
if (o2 == 0 && onSegment(p1, q2, q1)) return true;
// p2, q2 and p1 are colinear and p1 lies on segment p2q2
if (o3 == 0 && onSegment(p2, p1, q2)) return true;
// p2, q2 and q1 are colinear and q1 lies on segment p2q2
if (o4 == 0 && onSegment(p2, q1, q2)) return true;
return false; // Doesn''t fall in any of the above cases
}
// Driver program to test above functions
int main()
{
struct Point p1 = {1, 1}, q1 = {10, 1};
struct Point p2 = {1, 2}, q2 = {10, 2};
doIntersect(p1, q1, p2, q2)? cout << "Yes/n": cout << "No/n";
p1 = {10, 0}, q1 = {0, 10};
p2 = {0, 0}, q2 = {10, 10};
doIntersect(p1, q1, p2, q2)? cout << "Yes/n": cout << "No/n";
p1 = {-5, -5}, q1 = {0, 0};
p2 = {1, 1}, q2 = {10, 10};
doIntersect(p1, q1, p2, q2)? cout << "Yes/n": cout << "No/n";
return 0;
}

Answer 15

Basado en la respuesta de @Gareth Rees, versión para Python:

import numpy as np
def np_perp( a ) :
b = np.empty_like(a)
b[0] = a[1]
b[1] = -a[0]
return b
def np_cross_product(a, b):
return np.dot(a, np_perp(b))
def np_seg_intersect(a, b, considerCollinearOverlapAsIntersect = False):
# https://.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/565282#565282
# http://www.codeproject.com/Tips/862988/Find-the-intersection-point-of-two-line-segments
r = a[1] - a[0]
s = b[1] - b[0]
v = b[0] - a[0]
num = np_cross_product(v, r)
denom = np_cross_product(r, s)
# If r x s = 0 and (q - p) x r = 0, then the two lines are collinear.
if np.isclose(denom, 0) and np.isclose(num, 0):
# 1. If either 0 <= (q - p) * r <= r * r or 0 <= (p - q) * s <= * s
# then the two lines are overlapping,
if(considerCollinearOverlapAsIntersect):
vDotR = np.dot(v, r)
aDotS = np.dot(-v, s)
if (0 <= vDotR and vDotR <= np.dot(r,r)) or (0 <= aDotS and aDotS <= np.dot(s,s)):
return True
# 2. If neither 0 <= (q - p) * r = r * r nor 0 <= (p - q) * s <= s * s
# then the two lines are collinear but disjoint.
# No need to implement this expression, as it follows from the expression above.
return None
if np.isclose(denom, 0) and not np.isclose(num, 0):
# Parallel and non intersecting
return None
u = num / denom
t = np_cross_product(v, s) / denom
if u >= 0 and u <= 1 and t >= 0 and t <= 1:
res = b[0] + (s*u)
return res
# Otherwise, the two line segments are not parallel but do not intersect.
return None

Answer 16

Basado en la respuesta de t3chb0t:

int intersezione_linee(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
//L1: estremi (x1,y1)(x2,y2) L2: estremi (x3,y3)(x3,y3)
int d;
d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
if(!d)
return 0;
p_x = ((x1*y2-y1*x2)*(x3-x4) - (x1-x2)*(x3*y4-y3*x4))/d;
p_y = ((x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4))/d;
return 1;
}
int in_bounding_box(int x1, int y1, int x2, int y2, int p_x, int p_y)
{
return p_x>=x1 && p_x<=x2 && p_y>=y1 && p_y<=y2;
}
int intersezione_segmenti(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
if (!intersezione_linee(x1,y1,x2,y2,x3,y3,x4,y4,p_x,p_y))
return 0;
return in_bounding_box(x1,y1,x2,y2,p_x,p_y) && in_bounding_box(x3,y3,x4,y4,p_x,p_y);
}

Answer 17

Esta solución puede ayudar

public static float GetLineYIntesept(PointF p, float slope)
{
return p.Y - slope * p.X;
}
public static PointF FindIntersection(PointF line1Start, PointF line1End, PointF line2Start, PointF line2End)
{
float slope1 = (line1End.Y - line1Start.Y) / (line1End.X - line1Start.X);
float slope2 = (line2End.Y - line2Start.Y) / (line2End.X - line2Start.X);
float yinter1 = GetLineYIntesept(line1Start, slope1);
float yinter2 = GetLineYIntesept(line2Start, slope2);
if (slope1 == slope2 && yinter1 != yinter2)
return PointF.Empty;
float x = (yinter2 - yinter1) / (slope1 - slope2);
float y = slope1 * x + yinter1;
return new PointF(x, y);
}

Answer 18

Leí estos algoritmos del libro "geometría de vista múltiple"

siguiente texto usando

''como signo de transposición

* como producto puntual

x como producto cruzado, cuando se usa como operador

1. definición de línea

un punto x_vec = (x, y) ''se encuentra en la línea ax + by + c = 0

denotamos L = (a, b, c) '', el punto como (x, y, 1)'' como coordenadas homogéneas

la ecuación de línea se puede escribir como

(x, y, 1) (a, b, c) ''= 0 o x'' * L = 0

2. intersección de líneas

tenemos dos líneas L1 = (a1, b1, c1) '', L2 = (a2, b2, c2)''

Supongamos que x es un punto, un vector y x = L1 x L2 (producto cruzado L1 L2).

tenga cuidado, x siempre es un punto 2D, lea las coordenadas homogéneas si está confundido (L1xL2) es un vector de tres elementos y x es una coordenadas 2D.

De acuerdo al triple producto, sabemos que.

L1 * (L1 x L2) = 0, y L2 * (L1 x L2) = 0, debido al co-plano de L1, L2

sustituimos (L1xL2) con el vector x, luego tenemos L1 * x = 0, L2 * x = 0, lo que significa que x se encuentra en L1 y L2, x es el punto de intersección.

tenga cuidado, aquí x es coordenadas homogéneas, si el último elemento de x es cero, significa que L1 y L2 son paralelos.

Answer 19

Aquí hay una implementación básica de un segmento de línea en C #, con el correspondiente código de detección de intersección. Requiere una estructura de punto / vector 2D llamada Vector2f, aunque puede reemplazarla con cualquier otro tipo que tenga propiedades X / Y También puede reemplazar floatcon doublesi se adapte mejor a sus necesidades.

Este código se usa en mi biblioteca de física .NET, Boing .

public struct LineSegment2f
{
public Vector2f From { get; }
public Vector2f To { get; }
public LineSegment2f(Vector2f @from, Vector2f to)
{
From = @from;
To = to;
}
public Vector2f Delta => new Vector2f(To.X - From.X, To.Y - From.Y);
/// <summary>
/// Attempt to intersect two line segments.
/// </summary>
/// <remarks>
/// Even if the line segments do not intersect, <paramref name="t"/> and <paramref name="u"/> will be set.
/// If the lines are parallel, <paramref name="t"/> and <paramref name="u"/> are set to <see cref="float.NaN"/>.
/// </remarks>
/// <param name="other">The line to attempt intersection of this line with.</param>
/// <param name="intersectionPoint">The point of intersection if within the line segments, or empty..</param>
/// <param name="t">The distance along this line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
/// <param name="u">The distance along the other line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
/// <returns><c>true</c> if the line segments intersect, otherwise <c>false</c>.</returns>
public bool TryIntersect(LineSegment2f other, out Vector2f intersectionPoint, out float t, out float u)
{
var p = From;
var q = other.From;
var r = Delta;
var s = other.Delta;
// t = (q − p) × s / (r × s)
// u = (q − p) × r / (r × s)
var denom = Fake2DCross(r, s);
if (denom == 0)
{
// lines are collinear or parallel
t = float.NaN;
u = float.NaN;
intersectionPoint = default(Vector2f);
return false;
}
var tNumer = Fake2DCross(q - p, s);
var uNumer = Fake2DCross(q - p, r);
t = tNumer / denom;
u = uNumer / denom;
if (t < 0 || t > 1 || u < 0 || u > 1)
{
// line segments do not intersect within their ranges
intersectionPoint = default(Vector2f);
return false;
}
intersectionPoint = p + r * t;
return true;
}
private static float Fake2DCross(Vector2f a, Vector2f b)
{
return a.X * b.Y - a.Y * b.X;
}
}

Answer 20

Creo que hay una solución mucho más simple para este problema. Se me ocurrió otra idea hoy y parece funcionar bien (al menos en 2D por ahora). Todo lo que tiene que hacer, es calcular la intersección entre dos líneas, luego verificar si el punto de intersección calculado está dentro de los cuadros de límite de ambos segmentos de línea. Si es así, los segmentos de línea se intersecan. Eso es.

EDITAR:

Así es como calculo la intersección (ya no sé dónde encontré este fragmento de código)

Point3D

viene de

System.Windows.Media.Media3D
public static Point3D? Intersection(Point3D start1, Point3D end1, Point3D start2, Point3D end2) {
double a1 = end1.Y - start1.Y;
double b1 = start1.X - end1.X;
double c1 = a1 * start1.X + b1 * start1.Y;
double a2 = end2.Y - start2.Y;
double b2 = start2.X - end2.X;
double c2 = a2 * start2.X + b2 * start2.Y;
double det = a1 * b2 - a2 * b1;
if (det == 0) { // lines are parallel
return null;
}
double x = (b2 * c1 - b1 * c2) / det;
double y = (a1 * c2 - a2 * c1) / det;
return new Point3D(x, y, 0.0);
}

y esta es mi clase BoundingBox (simplificada para el propósito de la respuesta):

public class BoundingBox {
private Point3D min = new Point3D();
private Point3D max = new Point3D();
public BoundingBox(Point3D point) {
min = point;
max = point;
}
public Point3D Min {
get { return min; }
set { min = value; }
}
public Point3D Max {
get { return max; }
set { max = value; }
}
public bool Contains(BoundingBox box) {
bool contains =
min.X <= box.min.X && max.X >= box.max.X &&
min.Y <= box.min.Y && max.Y >= box.max.Y &&
min.Z <= box.min.Z && max.Z >= box.max.Z;
return contains;
}
public bool Contains(Point3D point) {
return Contains(new BoundingBox(point));
}
}

Answer 21

Esto se basa en la respuesta de Gareth Ree. También devuelve la superposición de los segmentos de línea si lo hacen. Codificado en C ++, V es una clase vectorial simple. Donde el producto cruzado de dos vectores en 2D devuelve un solo escalar. Fue probado y pasado por el sistema de prueba automática de mi escuela.

//Required input point must be colinear with the line
bool on_segment(const V& p, const LineSegment& l)
{
//If a point is on the line, the sum of the vectors formed by the point to the line endpoints must be equal
V va = p - l.pa;
V vb = p - l.pb;
R ma = va.magnitude();
R mb = vb.magnitude();
R ml = (l.pb - l.pa).magnitude();
R s = ma + mb;
bool r = s <= ml + epsilon;
return r;
}
//Compute using vector math
// Returns 0 points if the lines do not intersect or overlap
// Returns 1 point if the lines intersect
// Returns 2 points if the lines overlap, contain the points where overlapping start starts and stop
std::vector<V> intersect(const LineSegment& la, const LineSegment& lb)
{
std::vector<V> r;
//http://.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
V oa, ob, da, db; //Origin and direction vectors
R sa, sb; //Scalar values
oa = la.pa;
da = la.pb - la.pa;
ob = lb.pa;
db = lb.pb - lb.pa;
if (da.cross(db) == 0 && (ob - oa).cross(da) == 0) //If colinear
{
if (on_segment(lb.pa, la) && on_segment(lb.pb, la))
{
r.push_back(lb.pa);
r.push_back(lb.pb);
dprintf("colinear, overlapping/n");
return r;
}
if (on_segment(la.pa, lb) && on_segment(la.pb, lb))
{
r.push_back(la.pa);
r.push_back(la.pb);
dprintf("colinear, overlapping/n");
return r;
}
if (on_segment(la.pa, lb))
r.push_back(la.pa);
if (on_segment(la.pb, lb))
r.push_back(la.pb);
if (on_segment(lb.pa, la))
r.push_back(lb.pa);
if (on_segment(lb.pb, la))
r.push_back(lb.pb);
if (r.size() == 0)
dprintf("colinear, non-overlapping/n");
else
dprintf("colinear, overlapping/n");
return r;
}
if (da.cross(db) == 0 && (ob - oa).cross(da) != 0)
{
dprintf("parallel non-intersecting/n");
return r;
}
//Math trick db cross db == 0, which is a single scalar in 2D.
//Crossing both sides with vector db gives:
sa = (ob - oa).cross(db) / da.cross(db);
//Crossing both sides with vector da gives
sb = (oa - ob).cross(da) / db.cross(da);
if (0 <= sa && sa <= 1 && 0 <= sb && sb <= 1)
{
dprintf("intersecting/n");
r.push_back(oa + da * sa);
return r;
}
dprintf("non-intersecting, non-parallel, non-colinear, non-overlapping/n");
return r;
}

Answer 22

Muchas respuestas han envuelto todos los cálculos en una sola función. Si necesita calcular las pendientes de línea, las intersecciones en y, o las intersecciones en x para usar en cualquier otra parte de su código, hará esos cálculos de manera redundante. He separado las funciones respectivas, he usado nombres de variables obvios y he comentado mi código para que sea más fácil de seguir. Necesitaba saber si las líneas se cruzan infinitamente más allá de sus puntos finales, por lo que en JavaScript:

http://jsfiddle.net/skibulk/evmqq00u/

var point_a = {x:0, y:10},
point_b = {x:12, y:12},
point_c = {x:10, y:0},
point_d = {x:0, y:0},
slope_ab = slope(point_a, point_b),
slope_bc = slope(point_b, point_c),
slope_cd = slope(point_c, point_d),
slope_da = slope(point_d, point_a),
yint_ab = y_intercept(point_a, slope_ab),
yint_bc = y_intercept(point_b, slope_bc),
yint_cd = y_intercept(point_c, slope_cd),
yint_da = y_intercept(point_d, slope_da),
xint_ab = x_intercept(point_a, slope_ab, yint_ab),
xint_bc = x_intercept(point_b, slope_bc, yint_bc),
xint_cd = x_intercept(point_c, slope_cd, yint_cd),
xint_da = x_intercept(point_d, slope_da, yint_da),
point_aa = intersect(slope_da, yint_da, xint_da, slope_ab, yint_ab, xint_ab),
point_bb = intersect(slope_ab, yint_ab, xint_ab, slope_bc, yint_bc, xint_bc),
point_cc = intersect(slope_bc, yint_bc, xint_bc, slope_cd, yint_cd, xint_cd),
point_dd = intersect(slope_cd, yint_cd, xint_cd, slope_da, yint_da, xint_da);
console.log(point_a, point_b, point_c, point_d);
console.log(slope_ab, slope_bc, slope_cd, slope_da);
console.log(yint_ab, yint_bc, yint_cd, yint_da);
console.log(xint_ab, xint_bc, xint_cd, xint_da);
console.log(point_aa, point_bb, point_cc, point_dd);
function slope(point_a, point_b) {
var i = (point_b.y - point_a.y) / (point_b.x - point_a.x);
if (i === -Infinity) return Infinity;
if (i === -0) return 0;
return i;
}
function y_intercept(point, slope) {
// Horizontal Line
if (slope == 0) return point.y;
// Vertical Line
if (slope == Infinity)
{
// THE Y-Axis
if (point.x == 0) return Infinity;
// No Intercept
return null;
}
// Angled Line
return point.y - (slope * point.x);
}
function x_intercept(point, slope, yint) {
// Vertical Line
if (slope == Infinity) return point.x;
// Horizontal Line
if (slope == 0)
{
// THE X-Axis
if (point.y == 0) return Infinity;
// No Intercept
return null;
}
// Angled Line
return -yint / slope;
}
// Intersection of two infinite lines
function intersect(slope_a, yint_a, xint_a, slope_b, yint_b, xint_b) {
if (slope_a == slope_b)
{
// Equal Lines
if (yint_a == yint_b && xint_a == xint_b) return Infinity;
// Parallel Lines
return null;
}
// First Line Vertical
if (slope_a == Infinity)
{
return {
x: xint_a,
y: (slope_b * xint_a) + yint_b
};
}
// Second Line Vertical
if (slope_b == Infinity)
{
return {
x: xint_b,
y: (slope_a * xint_b) + yint_a
};
}
// Not Equal, Not Parallel, Not Vertical
var i = (yint_b - yint_a) / (slope_a - slope_b);
return {
x: i,
y: (slope_a * i) + yint_a
};
}

Answer 23

Parece que hay un cierto interés en la respuesta de Gavin para la cual Cortijon propuso una versión de javascript en los comments y iMalc proporcionó una versión con un poco menos de cálculos . Algunos han señalado deficiencias con varias propuestas de código y otros han comentado sobre la eficiencia de algunas propuestas de código.

El algoritmo proporcionado por iMalc a través de la respuesta de Gavin es el que estoy usando actualmente en un proyecto javascript y solo quería proporcionar una versión limpia aquí si puede ayudar a alguien.

// Some variables for reuse, others may do this differently
var p0x, p1x, p2x, p3x, ix,
p0y, p1y, p2y, p3y, iy,
collisionDetected;
// do stuff, call other functions, set endpoints...
// note: for my purpose I use |t| < |d| as opposed to
// |t| <= |d| which is equivalent to 0 <= t < 1 rather than
// 0 <= t <= 1 as in Gavin''s answer - results may vary
var lineSegmentIntersection = function(){
var d, dx1, dx2, dx3, dy1, dy2, dy3, s, t;
dx1 = p1x - p0x; dy1 = p1y - p0y;
dx2 = p3x - p2x; dy2 = p3y - p2y;
dx3 = p0x - p2x; dy3 = p0y - p2y;
collisionDetected = 0;
d = dx1 * dy2 - dx2 * dy1;
if(d !== 0){
s = dx1 * dy3 - dx3 * dy1;
if((s <= 0 && d < 0 && s >= d) || (s >= 0 && d > 0 && s <= d)){
t = dx2 * dy3 - dx3 * dy2;
if((t <= 0 && d < 0 && t > d) || (t >= 0 && d > 0 && t < d)){
t = t / d;
collisionDetected = 1;
ix = p0x + t * dx1;
iy = p0y + t * dy1;
}
}
}
};

Answer 24

Porté la respuesta anterior de Kris a JavaScript. Después de probar numerosas respuestas diferentes, proporcionó los puntos correctos. Pensé que me estaba volviendo loca porque no estaba obteniendo los puntos que necesitaba.

function getLineLineCollision(p0, p1, p2, p3) {
var s1, s2;
s1 = {x: p1.x - p0.x, y: p1.y - p0.y};
s2 = {x: p3.x - p2.x, y: p3.y - p2.y};
var s10_x = p1.x - p0.x;
var s10_y = p1.y - p0.y;
var s32_x = p3.x - p2.x;
var s32_y = p3.y - p2.y;
var denom = s10_x * s32_y - s32_x * s10_y;
if(denom == 0) {
return false;
}
var denom_positive = denom > 0;
var s02_x = p0.x - p2.x;
var s02_y = p0.y - p2.y;
var s_numer = s10_x * s02_y - s10_y * s02_x;
if((s_numer < 0) == denom_positive) {
return false;
}
var t_numer = s32_x * s02_y - s32_y * s02_x;
if((t_numer < 0) == denom_positive) {
return false;
}
if((s_numer > denom) == denom_positive || (t_numer > denom) == denom_positive) {
return false;
}
var t = t_numer / denom;
var p = {x: p0.x + (t * s10_x), y: p0.y + (t * s10_y)};
return p;
}

Answer 25

Probé algunas de estas respuestas, pero no funcionaron para mí (lo siento chicos); Después de un poco más de búsqueda neta encontré this .

Con una pequeña modificación en su código ahora tengo esta función que devolverá el punto de intersección o si no se encuentra una intersección, devolverá -1, -1.

 Public Function intercetion(ByVal ax As Integer, ByVal ay As Integer, ByVal bx As Integer, ByVal by As Integer, ByVal cx As Integer, ByVal cy As Integer, ByVal dx As Integer, ByVal dy As Integer) As Point
''// Determines the intersection point of the line segment defined by points A and B
''// with the line segment defined by points C and D.
''//
''// Returns YES if the intersection point was found, and stores that point in X,Y.
''// Returns NO if there is no determinable intersection point, in which case X,Y will
''// be unmodified.
Dim distAB, theCos, theSin, newX, ABpos As Double
''// Fail if either line segment is zero-length.
If ax = bx And ay = by Or cx = dx And cy = dy Then Return New Point(-1, -1)
''// Fail if the segments share an end-point.
If ax = cx And ay = cy Or bx = cx And by = cy Or ax = dx And ay = dy Or bx = dx And by = dy Then Return New Point(-1, -1)
''// (1) Translate the system so that point A is on the origin.
bx -= ax
by -= ay
cx -= ax
cy -= ay
dx -= ax
dy -= ay
''// Discover the length of segment A-B.
distAB = Math.Sqrt(bx * bx + by * by)
''// (2) Rotate the system so that point B is on the positive X axis.
theCos = bx / distAB
theSin = by / distAB
newX = cx * theCos + cy * theSin
cy = cy * theCos - cx * theSin
cx = newX
newX = dx * theCos + dy * theSin
dy = dy * theCos - dx * theSin
dx = newX
''// Fail if segment C-D doesn''t cross line A-B.
If cy < 0 And dy < 0 Or cy >= 0 And dy >= 0 Then Return New Point(-1, -1)
''// (3) Discover the position of the intersection point along line A-B.
ABpos = dx + (cx - dx) * dy / (dy - cy)
''// Fail if segment C-D crosses line A-B outside of segment A-B.
If ABpos < 0 Or ABpos > distAB Then Return New Point(-1, -1)
''// (4) Apply the discovered position to line A-B in the original coordinate system.
''*X=Ax+ABpos*theCos
''*Y=Ay+ABpos*theSin
''// Success.
Return New Point(ax + ABpos * theCos, ay + ABpos * theSin)
End Function

Answer 26

Probé muchas maneras y luego decidí escribir la mía. Asi que aqui esta:

bool IsBetween (float x, float b1, float b2)
{
return ( ((x >= (b1 - 0.1f)) &&
(x <= (b2 + 0.1f))) ||
((x >= (b2 - 0.1f)) &&
(x <= (b1 + 0.1f))));
}
bool IsSegmentsColliding( POINTFLOAT lineA,
POINTFLOAT lineB,
POINTFLOAT line2A,
POINTFLOAT line2B)
{
float deltaX1 = lineB.x - lineA.x;
float deltaX2 = line2B.x - line2A.x;
float deltaY1 = lineB.y - lineA.y;
float deltaY2 = line2B.y - line2A.y;
if (abs(deltaX1) < 0.01f &&
abs(deltaX2) < 0.01f) // Both are vertical lines
return false;
if (abs((deltaY1 / deltaX1) -
(deltaY2 / deltaX2)) < 0.001f) // Two parallel line
return false;
float xCol = ( ( (deltaX1 * deltaX2) *
(line2A.y - lineA.y)) -
(line2A.x * deltaY2 * deltaX1) +
(lineA.x * deltaY1 * deltaX2)) /
((deltaY1 * deltaX2) - (deltaY2 * deltaX1));
float yCol = 0;
if (deltaX1 < 0.01f) // L1 is a vertical line
yCol = ((xCol * deltaY2) +
(line2A.y * deltaX2) -
(line2A.x * deltaY2)) / deltaX2;
else // L1 is acceptable
yCol = ((xCol * deltaY1) +
(lineA.y * deltaX1) -
(lineA.x * deltaY1)) / deltaX1;
bool isCol = IsBetween(xCol, lineA.x, lineB.x) &&
IsBetween(yCol, lineA.y, lineB.y) &&
IsBetween(xCol, line2A.x, line2B.x) &&
IsBetween(yCol, line2A.y, line2B.y);
return isCol;
}

Basado en estas dos fórmulas: (Las simplifiqué a partir de la ecuación de líneas y otras fórmulas)

Answer 27

Si cada lado del rectángulo es un segmento de línea, y la parte dibujada por el usuario es un segmento de línea, entonces debe verificar que el segmento dibujado por el usuario tenga intersección con los cuatro segmentos de línea lateral. Este debe ser un ejercicio bastante simple dados los puntos de inicio y final de cada segmento.