Conectar dos segmentos de línea

Question

Dados dos segmentos de línea 2D, A y B, ¿cómo calculo la longitud del segmento de línea 2D más corto, C, que conecta A y B?

Answer 1

considerar sus dos líneas de los segmentos a y B a ser representado por dos puntos cada uno (en Fortran!):

línea a representada por A1 (x, y), A2 (x, y)

Línea B representada por B1 (x, y) B2 (x, y)

Primero compruebe si las dos líneas se cruzan usando este algoritmo.

Si se cruzan, entonces la distancia entre las dos líneas es cero, y el segmento de línea que las une es el punto de intersección.

Si no se intersecan, utilice este método: http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/ para calcular la distancia más corta entre:

1. punto A1 y la línea B
2. punto A2 y la línea B
3. Point B1 y la línea Un B2
4. Punto y línea A

La más corta de esos cuatro segmentos de línea es tu respuesta.

Answer 2

This page tiene información que usted puede estar buscando.

Answer 3

Gernot Hoffmann papel (algoritmo y código de Pascal):

http://www.fho-emden.de/~hoffmann/xsegdist03072004.pdf

Answer 4

Consejo rápido: si desea comparar las distancias basado en puntos, no es necesario hacer las raíces cuadradas.

E.g. para ver si P-a-Q es una distancia menor que Q-a-R, sólo echa (pseudocódigo):

square(P.x-Q.x) + square(P.y-Q.y) < square(Q.x-R.x) + square(Q.y-R.y) 

Answer 5

This page tiene una buena descripción corta para encontrar la distancia más corta entre dos líneas, aunque @ Strager de enlace incluye algún código

Answer 6

Afterlife dijo: "Primero compruebe si las dos líneas se cruzan usando este algoritmo", pero no indicó a qué algoritmo se refería. Obviamente, es la intersección de la línea segmentos no las líneas extendidas lo que importa; cualquier segmento de línea no paralelo (excluyendo los puntos finales coincidentes que no definen una línea) se intersectará, pero la distancia entre los segmentos de línea no será necesariamente cero. Así que supongo que quiso decir "segmentos de línea" en lugar de "líneas" allí.

El enlace que Afterlife dio es un enfoque muy elegante para encontrar el punto más cercano de una línea (o segmento de línea, o rayo) a otro punto arbitrario. Esto funciona para encontrar la distancia desde cada punto final al otro segmento de línea (restringir el parámetro calculado u a ser no menos de 0 para un segmento de línea o rayo y no ser más de 1 para un segmento de línea), pero no lo hace maneje la posibilidad de que un punto interior en un segmento de línea esté más cerca que cualquiera de los extremos ya que en realidad se cruzan, por lo que se requiere un control adicional sobre la intersección.

En cuanto al algoritmo para determinar la intersección del segmento de línea, un enfoque sería encontrar la intersección de las líneas extendidas (si es paralelo, entonces) y determinar si ese punto está dentro de ambos segmentos de línea, tales como al tomar el producto de puntos de los vectores desde el punto de intersección, T, a los dos puntos finales:

((Tx - A1x) * (Tx - A2x)) + ((Ty - A1y) ​​* (Ty - A2y))

Si esto es negativo (o "cero"), entonces T está entre A1 y A2 (o en un punto final). Verifique de manera similar para el otro segmento de línea. Si cualquiera fue mayor que "cero", los segmentos de línea no se intersectan. Por supuesto, esto depende de encontrar primero la intersección de las líneas extendidas, lo que puede requerir expresar cada línea como una ecuación y resolver el sistema mediante reducción gaussiana (etc.).

Pero puede haber una manera más directa sin tener que resolver el punto de intersección, tomando el producto cruzado de los vectores (B1-A1) y (B2-A1) y el producto cruzado de los vectores (B1 -A2) y (B2-A2). Si estos productos cruzados están en la misma dirección, entonces A1 y A2 están en el mismo lado de la línea B; si están en direcciones opuestas, entonces están en lados opuestos de la línea B (y si es 0, entonces uno o ambos son en línea B). De forma similar, compruebe los productos cruzados de los vectores (A1-B1) y (A2-B1) y de (A1-B2) y (A2-B2). Si cualquiera de estos productos cruzados es "cero", o si los puntos finales de ambos segmentos de línea caen en lados opuestos de la otra línea, entonces los segmentos de línea mismos deben cruzarse, de lo contrario no se cruzan.

Por supuesto, necesita una fórmula práctica para calcular un producto cruzado de dos vectores a partir de sus coordenadas. O si pudieras determinar los ángulos (siendo positivo o negativo), no necesitarías el producto cruzado real, ya que es la dirección de los ángulos entre los vectores lo que realmente nos importa (o el seno del ángulo, realmente) . Pero creo que la fórmula para el producto cruzado (en 2-D) es simplemente:

Cross (V1, V2) = (V1x * V2Y) - (V2x * V1Y)

Este es el eje z componente del vector de producto cruzado 3-D (donde los componentes xey deben ser cero, porque los vectores iniciales están en el plano z = 0), por lo que simplemente puede mirar el signo (o "cero").

Por lo tanto, podría utilizar uno de estos dos métodos para verificar la intersección del segmento de línea en el algoritmo Afterlife describe (haciendo referencia al enlace).

Answer 7

Utilizando la idea general de los algoritmos Afterlife's y Rob Parker's anteriores, esta es una versión C++ de un conjunto de métodos para obtener la distancia mínima entre 2 segmentos 2D arbitrarios. Esto manejará segmentos superpuestos, segmentos paralelos, segmentos intersecantes y no intersecantes. Además, usa varios valores epsilon para proteger contra la imprecisión de punto flotante. Finalmente, además de devolver la distancia mínima, este algoritmo le dará el punto en el segmento 1 más cercano al segmento 2 (que también es el punto de intersección si los segmentos se cruzan). Sería bastante trivial también devolver el punto de [P3, P4] cercana a [P1, P2] si así lo desean, pero voy a dejar que como ejercicio para el lector :)

// minimum distance (squared) between vertices, i.e. minimum segment length (squared) 
#define EPSILON_MIN_VERTEX_DISTANCE_SQUARED 0.00000001 

// An arbitrary tiny epsilon. If you use float instead of double, you'll probably want to change this to something like 1E-7f 
#define EPSILON_TINY 1.0E-14 

// Arbitrary general epsilon. Useful for places where you need more "slop" than EPSILON_TINY (which is most places). 
// If you use float instead of double, you'll likely want to change this to something like 1.192092896E-04 
#define EPSILON_GENERAL 1.192092896E-07 

bool AreValuesEqual(double val1, double val2, double tolerance) 
{ 
    if (val1 >= (val2 - tolerance) && val1 <= (val2 + tolerance)) 
    { 
     return true; 
    } 

    return false; 
} 


double PointToPointDistanceSquared(double p1x, double p1y, double p2x, double p2y) 
{ 
    double dx = p2x - p1x; 
    double dy = p2y - p1y; 
    return (dx * dx) + (dy * dy); 
} 


double PointSegmentDistanceSquared(double px, double py, 
            double p1x, double p1y, 
            double p2x, double p2y, 
            double& t, 
            double& qx, double& qy) 
{ 
    double dx = p2x - p1x; 
    double dy = p2y - p1y; 
    double dp1x = px - p1x; 
    double dp1y = py - p1y; 
    const double segLenSquared = (dx * dx) + (dy * dy); 
    if (AreValuesEqual(segLenSquared, 0.0, EPSILON_MIN_VERTEX_DISTANCE_SQUARED)) 
    { 
     // segment is a point. 
     qx = p1x; 
     qy = p1y; 
     t = 0.0; 
     return ((dp1x * dp1x) + (dp1y * dp1y)); 
    } 
    else 
    { 
     t = ((dp1x * dx) + (dp1y * dy))/segLenSquared; 
     if (t <= EPSILON_TINY) 
     { 
      // intersects at or to the "left" of first segment vertex (p1x, p1y). If t is approximately 0.0, then 
      // intersection is at p1. If t is less than that, then there is no intersection (i.e. p is not within 
      // the 'bounds' of the segment) 
      if (t >= -EPSILON_TINY) 
      { 
       // intersects at 1st segment vertex 
       t = 0.0; 
      } 
      // set our 'intersection' point to p1. 
      qx = p1x; 
      qy = p1y; 
      // Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if 
      // we were doing PointLineDistanceSquared, then qx would be (p1x + (t * dx)) and qy would be (p1y + (t * dy)). 
     } 
     else if (t >= (1.0 - EPSILON_TINY)) 
     { 
      // intersects at or to the "right" of second segment vertex (p2x, p2y). If t is approximately 1.0, then 
      // intersection is at p2. If t is greater than that, then there is no intersection (i.e. p is not within 
      // the 'bounds' of the segment) 
      if (t <= (1.0 + EPSILON_TINY)) 
      { 
       // intersects at 2nd segment vertex 
       t = 1.0; 
      } 
      qx = p2x; 
      qy = p2y; 
      // Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if 
      // we were doing PointLineDistanceSquared, then qx would be (p1x + (t * dx)) and qy would be (p1y + (t * dy)). 
     } 
     else 
     { 
      // The projection of the point to the point on the segment that is perpendicular succeeded and the point 
      // is 'within' the bounds of the segment. Set the intersection point as that projected point. 
      qx = ((1.0 - t) * p1x) + (t * p2x); 
      qy = ((1.0 - t) * p1y) + (t * p2y); 
      // for debugging 
      //ASSERT(AreValuesEqual(qx, p1x + (t * dx), EPSILON_TINY)); 
      //ASSERT(AreValuesEqual(qy, p1y + (t * dy), EPSILON_TINY)); 
     } 
     // return the squared distance from p to the intersection point. 
     double dpqx = px - qx; 
     double dpqy = py - qy; 
     return ((dpqx * dpqx) + (dpqy * dpqy)); 
    } 
} 


double SegmentSegmentDistanceSquared( double p1x, double p1y, 
             double p2x, double p2y, 
             double p3x, double p3y, 
             double p4x, double p4y, 
             double& qx, double& qy) 
{ 
    // check to make sure both segments are long enough (i.e. verts are farther apart than minimum allowed vert distance). 
    // If 1 or both segments are shorter than this min length, treat them as a single point. 
    double segLen12Squared = PointToPointDistanceSquared(p1x, p1y, p2x, p2y); 
    double segLen34Squared = PointToPointDistanceSquared(p3x, p3y, p4x, p4y); 
    double t = 0.0; 
    double minDist2 = 1E+38; 
    if (segLen12Squared <= EPSILON_MIN_VERTEX_DISTANCE_SQUARED) 
    { 
     qx = p1x; 
     qy = p1y; 
     if (segLen34Squared <= EPSILON_MIN_VERTEX_DISTANCE_SQUARED) 
     { 
      // point to point 
      minDist2 = PointToPointDistanceSquared(p1x, p1y, p3x, p3y); 
     } 
     else 
     { 
      // point - seg 
      minDist2 = PointSegmentDistanceSquared(p1x, p1y, p3x, p3y, p4x, p4y); 
     } 
     return minDist2; 
    } 
    else if (segLen34Squared <= EPSILON_MIN_VERTEX_DISTANCE_SQUARED) 
    { 
     // seg - point 
     minDist2 = PointSegmentDistanceSquared(p3x, p3y, p1x, p1y, p2x, p2y, t, qx, qy); 
     return minDist2; 
    } 

    // if you have a point class and/or methods to do cross products, you can use those here. 
    // This is what we're actually doing: 
    // Point2D delta43(p4x - p3x, p4y - p3y); // dir of p3 -> p4 
    // Point2D delta12(p1x - p2x, p1y - p2y); // dir of p2 -> p1 
    // double d = delta12.Cross2D(delta43); 
    double d = ((p4y - p3y) * (p1x - p2x)) - ((p1y - p2y) * (p4x - p3x)); 
    bool bParallel = AreValuesEqual(d, 0.0, EPSILON_GENERAL); 

    if (!bParallel) 
    { 
     // segments are not parallel. Check for intersection. 
     // Point2D delta42(p4x - p2x, p4y - p2y); // dir of p2 -> p4 
     // t = 1.0 - (delta42.Cross2D(delta43)/d); 
     t = 1.0 - ((((p4y - p3y) * (p4x - p2x)) - ((p4y - p2y) * (p4x - p3x)))/d); 
     double seg12TEps = sqrt(EPSILON_MIN_VERTEX_DISTANCE_SQUARED/segLen12Squared); 
     if (t >= -seg12TEps && t <= (1.0 + seg12TEps)) 
     { 
      // inside [p1,p2]. Segments may intersect. 
      // double s = 1.0 - (delta12.Cross2D(delta42)/d); 
      double s = 1.0 - ((((p4y - p2y) * (p1x - p2x)) - ((p1y - p2y) * (p4x - p2x)))/d); 
      double seg34TEps = sqrt(EPSILON_MIN_VERTEX_DISTANCE_SQUARED/segLen34Squared); 
      if (s >= -seg34TEps && s <= (1.0 + seg34TEps)) 
      { 
       // segments intersect! 
       minDist2 = 0.0; 
       qx = ((1.0 - t) * p1x) + (t * p2x); 
       qy = ((1.0 - t) * p1y) + (t * p2y); 
       // for debugging 
       //double qsx = ((1.0 - s) * p3x) + (s * p4x); 
       //double qsy = ((1.0 - s) * p3y) + (s * p4y); 
       //ASSERT(AreValuesEqual(qx, qsx, EPSILON_MIN_VERTEX_DISTANCE_SQUARED)); 
       //ASSERT(AreValuesEqual(qy, qsy, EPSILON_MIN_VERTEX_DISTANCE_SQUARED)); 
       return minDist2; 
      } 
     } 
    } 

    // Segments do not intersect. Find closest point and return dist. No other way at this 
    // point except to just brute-force check each segment end-point vs opposite segment. The 
    // minimum distance of those 4 tests is the closest point. 
    double tmpQx, tmpQy, tmpD2; 
    minDist2 = PointSegmentDistanceSquared(p3x, p3y, p1x, p1y, p2x, p2y, t, qx, qy); 
    tmpD2 = PointSegmentDistanceSquared(p4x, p4y, p1x, p1y, p2x, p2y, t, tmpQx, tmpQy); 
    if (tmpD2 < minDist2) 
    { 
     qx = tmpQx; 
     qy = tmpQy; 
     minDist2 = tmpD2; 
    } 
    tmpD2 = PointSegmentDistanceSquared(p1x, p1y, p3x, p3y, p4x, p4y, t, tmpQx, tmpQy); 
    if (tmpD2 < minDist2) 
    { 
     qx = p1x; 
     qy = p1y; 
     minDist2 = tmpD2; 
    } 
    tmpD2 = PointSegmentDistanceSquared(p2x, p2y, p3x, p3y, p4x, p4y, t, tmpQx, tmpQy); 
    if (tmpD2 < minDist2) 
    { 
     qx = p2x; 
     qy = p2y; 
     minDist2 = tmpD2; 
    } 

    return minDist2; 
}