subconjunto coincidente de dos segmentos de línea coincidentes

Question

Esta pregunta se relaciona con:

• How do I determine the intersection point of two lines in GDI+? (gran explicación del álgebra, pero sin código)
• How do you detect where two line segments intersect? (respuesta aceptada actualmente no trabaje)

Pero tenga en cuenta que un sub-problema interesante se pasa por alto por completo en la mayoría de las soluciones que simplemente devuelven nulo para el caso coincidente, aunque hay tres sub-casos:

coincidente
• pero no se superponen
• sólo puntos de contacto y coincidente
• solapamiento/línea coincidente subsegmento

Por ejemplo, podemos diseñar una función de C# como esto:

public static PointF[] Intersection(PointF a1, PointF a2, PointF b1, PointF b2) 

donde (a1, a2) es un segmento de línea y (b1, b2) es otro.

Esta función debería cubrir todos los casos extraños que la mayoría de las implementaciones o explicaciones pasan por alto. Con el fin de dar cuenta de la rareza de líneas coincidentes, la función podría devolver una matriz de PointF de:

• cero puntos resultado (o nulo) si las líneas son paralelas o no se cruzan (líneas infinitas se cruzan pero segmentos de línea son disjuntos, o líneas son paralelo)
• un punto resultado (que contiene la ubicación intersección) si intersecan o si son coincidente en un punto
• dos puntos de resultados (para los superposición de parte de los segmentos de línea), si las dos líneas son coincidente

Answer 1

Parece que tiene su solución, que es genial. Tengo algunas sugerencias para mejorarlo.

El método tiene un gran problema de usabilidad, ya que es muy confuso comprender (1) qué significan los parámetros entrantes, y (2) qué significan los resultados que salen. Ambos son pequeños rompecabezas que debes averiguar si quieres usar el método.

Me inclinaría más a utilizar el sistema de tipos para que quede mucho más claro qué hace este método.

Comenzaría por definir un tipo, quizás una estructura, particularmente si iba a ser inmutable, llamada LineSegment. Un LineSegment consta de dos estructuras PointF que representan el punto final.

En segundo lugar, definiría un tipo base abstracto "Locus" y los tipos derivados EmptyLocus, PointLocus, LineSegmentLocus y quizás UnionLocus si necesita representar el locus que es la unión de dos o más loci. Un locus vacío es solo un singleton, un locus de punto es solo un punto, y así sucesivamente.

Ahora su firma del método se vuelve mucho más claro:

static Locus Intersect(LineSegment l1, LineSegment l2) 

Este método tiene dos segmentos de línea y calcula el lugar geométrico de puntos que es su intersección - ya sea vacía, un único punto, o un segmento de línea.

Tenga en cuenta que puede generalizar este método. Calcular la intersección de un segmento de línea con un segmento de línea es complicado, pero calcular la intersección de un segmento de línea con un punto, o un punto con un punto, o cualquier cosa con el lugar vacío es fácil. Y no es difícil extender la intersección a uniones arbitrarias de loci. Por lo tanto, en realidad se podría escribir:

static Locus Intersect(Locus l1, Locus l2) 

Y bueno, ahora queda claro que se cruzan podría ser un método de extensión en el locus:

static Locus Intersect(this Locus l1, Locus l2) 

Añadir una conversión implícita de PointF a PointLocus y segmento a LineSegmentLocus , y se puede decir cosas como

var point = new PointF(whatever); 
var lineseg = new LineSegment(somepoint, someotherpoint); 
var intersection = lineseg.Intersect(point); 
if (intersection is EmptyLocus) ... 

de pozos mediante el sistema de tipos pueden mejorar enormemente la legibilidad de un programa.

Answer 2

// port of this JavaScript code with some changes: 
    // http://www.kevlindev.com/gui/math/intersection/Intersection.js 
    // found here: 
    // http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/563240#563240 

public class Intersector 
{ 
    static double MyEpsilon = 0.00001; 

    private static float[] OverlapIntervals(float ub1, float ub2) 
    { 
     float l = Math.Min(ub1, ub2); 
     float r = Math.Max(ub1, ub2); 
     float A = Math.Max(0, l); 
     float B = Math.Min(1, r); 
     if (A > B) // no intersection 
      return new float[] { }; 
     else if (A == B) 
      return new float[] { A }; 
     else // if (A < B) 
      return new float[] { A, B }; 
    } 

    // IMPORTANT: a1 and a2 cannot be the same, e.g. a1--a2 is a true segment, not a point 
    // b1/b2 may be the same (b1--b2 is a point) 
    private static PointF[] OneD_Intersection(PointF a1, PointF a2, PointF b1, PointF b2) 
    { 
     //float ua1 = 0.0f; // by definition 
     //float ua2 = 1.0f; // by definition 
     float ub1, ub2; 

     float denomx = a2.X - a1.X; 
     float denomy = a2.Y - a1.Y; 

     if (Math.Abs(denomx) > Math.Abs(denomy)) 
     { 
      ub1 = (b1.X - a1.X)/denomx; 
      ub2 = (b2.X - a1.X)/denomx; 
     } 
     else 
     { 
      ub1 = (b1.Y - a1.Y)/denomy; 
      ub2 = (b2.Y - a1.Y)/denomy; 
     } 

     List<PointF> ret = new List<PointF>(); 
     float[] interval = OverlapIntervals(ub1, ub2); 
     foreach (float f in interval) 
     { 
      float x = a2.X * f + a1.X * (1.0f - f); 
      float y = a2.Y * f + a1.Y * (1.0f - f); 
      PointF p = new PointF(x, y); 
      ret.Add(p); 
     } 
     return ret.ToArray(); 
    } 

    private static bool PointOnLine(PointF p, PointF a1, PointF a2) 
    { 
     float dummyU = 0.0f; 
     double d = DistFromSeg(p, a1, a2, MyEpsilon, ref dummyU); 
     return d < MyEpsilon; 
    } 

    private static double DistFromSeg(PointF p, PointF q0, PointF q1, double radius, ref float u) 
    { 
     // formula here: 
     //http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html 
     // where x0,y0 = p 
     //  x1,y1 = q0 
     //  x2,y2 = q1 
     double dx21 = q1.X - q0.X; 
     double dy21 = q1.Y - q0.Y; 
     double dx10 = q0.X - p.X; 
     double dy10 = q0.Y - p.Y; 
     double segLength = Math.Sqrt(dx21 * dx21 + dy21 * dy21); 
     if (segLength < MyEpsilon) 
      throw new Exception("Expected line segment, not point."); 
     double num = Math.Abs(dx21 * dy10 - dx10 * dy21); 
     double d = num/segLength; 
     return d; 
    } 

    // this is the general case. Really really general 
    public static PointF[] Intersection(PointF a1, PointF a2, PointF b1, PointF b2) 
    { 
     if (a1.Equals(a2) && b1.Equals(b2)) 
     { 
      // both "segments" are points, return either point 
      if (a1.Equals(b1)) 
       return new PointF[] { a1 }; 
      else // both "segments" are different points, return empty set 
       return new PointF[] { }; 
     } 
     else if (b1.Equals(b2)) // b is a point, a is a segment 
     { 
      if (PointOnLine(b1, a1, a2)) 
       return new PointF[] { b1 }; 
      else 
       return new PointF[] { }; 
     } 
     else if (a1.Equals(a2)) // a is a point, b is a segment 
     { 
      if (PointOnLine(a1, b1, b2)) 
       return new PointF[] { a1 }; 
      else 
       return new PointF[] { }; 
     } 

     // at this point we know both a and b are actual segments 

     float ua_t = (b2.X - b1.X) * (a1.Y - b1.Y) - (b2.Y - b1.Y) * (a1.X - b1.X); 
     float ub_t = (a2.X - a1.X) * (a1.Y - b1.Y) - (a2.Y - a1.Y) * (a1.X - b1.X); 
     float u_b = (b2.Y - b1.Y) * (a2.X - a1.X) - (b2.X - b1.X) * (a2.Y - a1.Y); 

     // Infinite lines intersect somewhere 
     if (!(-MyEpsilon < u_b && u_b < MyEpsilon)) // e.g. u_b != 0.0 
     { 
      float ua = ua_t/u_b; 
      float ub = ub_t/u_b; 
      if (0.0f <= ua && ua <= 1.0f && 0.0f <= ub && ub <= 1.0f) 
      { 
       // Intersection 
       return new PointF[] { 
        new PointF(a1.X + ua * (a2.X - a1.X), 
         a1.Y + ua * (a2.Y - a1.Y)) }; 
      } 
      else 
      { 
       // No Intersection 
       return new PointF[] { }; 
      } 
     } 
     else // lines (not just segments) are parallel or the same line 
     { 
      // Coincident 
      // find the common overlapping section of the lines 
      // first find the distance (squared) from one point (a1) to each point 
      if ((-MyEpsilon < ua_t && ua_t < MyEpsilon) 
       || (-MyEpsilon < ub_t && ub_t < MyEpsilon)) 
      { 
       if (a1.Equals(a2)) // danger! 
        return OneD_Intersection(b1, b2, a1, a2); 
       else // safe 
        return OneD_Intersection(a1, a2, b1, b2); 
      } 
      else 
      { 
       // Parallel 
       return new PointF[] { }; 
      } 
     } 
    } 


} 

Aquí es el código de prueba:

public class IntersectTest 
    { 
     public static void PrintPoints(PointF[] pf) 
     { 
      if (pf == null || pf.Length < 1) 
       System.Console.WriteLine("Doesn't intersect"); 
      else if (pf.Length == 1) 
      { 
       System.Console.WriteLine(pf[0]); 
      } 
      else if (pf.Length == 2) 
      { 
       System.Console.WriteLine(pf[0] + " -- " + pf[1]); 
      } 
     } 

     public static void TestIntersect(PointF a1, PointF a2, PointF b1, PointF b2) 
     { 
      System.Console.WriteLine("----------------------------------------------------------"); 
      System.Console.WriteLine("Does  " + a1 + " -- " + a2); 
      System.Console.WriteLine("intersect " + b1 + " -- " + b2 + " and if so, where?"); 
      System.Console.WriteLine(""); 
      PointF[] result = Intersect.Intersection(a1, a2, b1, b2); 
      PrintPoints(result); 
     } 

     public static void Main() 
     { 
      System.Console.WriteLine("----------------------------------------------------------"); 
      System.Console.WriteLine("line segments intersect"); 
      TestIntersect(new PointF(0, 0), 
          new PointF(100, 100), 
          new PointF(100, 0), 
          new PointF(0, 100)); 
      TestIntersect(new PointF(5, 17), 
          new PointF(100, 100), 
          new PointF(100, 29), 
          new PointF(8, 100)); 
      System.Console.WriteLine("----------------------------------------------------------"); 
      System.Console.WriteLine(""); 

      System.Console.WriteLine("----------------------------------------------------------"); 
      System.Console.WriteLine("just touching points and lines cross"); 
      TestIntersect(new PointF(0, 0), 
          new PointF(25, 25), 
          new PointF(25, 25), 
          new PointF(100, 75)); 
      System.Console.WriteLine("----------------------------------------------------------"); 
      System.Console.WriteLine(""); 

      System.Console.WriteLine("----------------------------------------------------------"); 
      System.Console.WriteLine("parallel"); 
      TestIntersect(new PointF(0, 0), 
          new PointF(0, 100), 
          new PointF(100, 0), 
          new PointF(100, 100)); 
      System.Console.WriteLine("----------------------------------------------------------"); 
      System.Console.WriteLine(""); 

      System.Console.WriteLine("----"); 
      System.Console.WriteLine("lines cross but segments don't intersect"); 
      TestIntersect(new PointF(50, 50), 
          new PointF(100, 100), 
          new PointF(0, 25), 
          new PointF(25, 0)); 
      System.Console.WriteLine("----------------------------------------------------------"); 
      System.Console.WriteLine(""); 

      System.Console.WriteLine("----------------------------------------------------------"); 
      System.Console.WriteLine("coincident but do not overlap!"); 
      TestIntersect(new PointF(0, 0), 
          new PointF(25, 25), 
          new PointF(75, 75), 
          new PointF(100, 100)); 
      System.Console.WriteLine("----------------------------------------------------------"); 
      System.Console.WriteLine(""); 

      System.Console.WriteLine("----------------------------------------------------------"); 
      System.Console.WriteLine("touching points and coincident!"); 
      TestIntersect(new PointF(0, 0), 
          new PointF(25, 25), 
          new PointF(25, 25), 
          new PointF(100, 100)); 
      System.Console.WriteLine("----------------------------------------------------------"); 
      System.Console.WriteLine(""); 

      System.Console.WriteLine("----------------------------------------------------------"); 
      System.Console.WriteLine("overlap/coincident"); 
      TestIntersect(new PointF(0, 0), 
          new PointF(75, 75), 
          new PointF(25, 25), 
          new PointF(100, 100)); 
      TestIntersect(new PointF(0, 0), 
          new PointF(100, 100), 
          new PointF(0, 0), 
          new PointF(100, 100)); 
      System.Console.WriteLine("----------------------------------------------------------"); 
      System.Console.WriteLine(""); 

      while (!System.Console.KeyAvailable) { } 
     } 

    } 

y aquí es la salida:

 
---------------------------------------------------------- 
line segments intersect 
---------------------------------------------------------- 
Does  {X=0, Y=0} -- {X=100, Y=100} 
intersect {X=100, Y=0} -- {X=0, Y=100} and if so, where? 

{X=50, Y=50} 
---------------------------------------------------------- 
Does  {X=5, Y=17} -- {X=100, Y=100} 
intersect {X=100, Y=29} -- {X=8, Y=100} and if so, where? 

{X=56.85001, Y=62.30054} 
---------------------------------------------------------- 

---------------------------------------------------------- 
just touching points and lines cross 
---------------------------------------------------------- 
Does  {X=0, Y=0} -- {X=25, Y=25} 
intersect {X=25, Y=25} -- {X=100, Y=75} and if so, where? 

{X=25, Y=25} 
---------------------------------------------------------- 

---------------------------------------------------------- 
parallel 
---------------------------------------------------------- 
Does  {X=0, Y=0} -- {X=0, Y=100} 
intersect {X=100, Y=0} -- {X=100, Y=100} and if so, where? 

Doesn't intersect 
---------------------------------------------------------- 

---- 
lines cross but segments don't intersect 
---------------------------------------------------------- 
Does  {X=50, Y=50} -- {X=100, Y=100} 
intersect {X=0, Y=25} -- {X=25, Y=0} and if so, where? 

Doesn't intersect 
---------------------------------------------------------- 

---------------------------------------------------------- 
coincident but do not overlap! 
---------------------------------------------------------- 
Does  {X=0, Y=0} -- {X=25, Y=25} 
intersect {X=75, Y=75} -- {X=100, Y=100} and if so, where? 

Doesn't intersect 
---------------------------------------------------------- 

---------------------------------------------------------- 
touching points and coincident! 
---------------------------------------------------------- 
Does  {X=0, Y=0} -- {X=25, Y=25} 
intersect {X=25, Y=25} -- {X=100, Y=100} and if so, where? 

{X=25, Y=25} 
---------------------------------------------------------- 

---------------------------------------------------------- 
overlap/coincident 
---------------------------------------------------------- 
Does  {X=0, Y=0} -- {X=75, Y=75} 
intersect {X=25, Y=25} -- {X=100, Y=100} and if so, where? 

{X=25, Y=25} -- {X=75, Y=75} 
---------------------------------------------------------- 
Does  {X=0, Y=0} -- {X=100, Y=100} 
intersect {X=0, Y=0} -- {X=100, Y=100} and if so, where? 

{X=0, Y=0} -- {X=100, Y=100} 
---------------------------------------------------------- 

Answer 3

Esto es realmente muy simple. Si tiene dos líneas, puede encontrar dos ecuaciones en la forma de y = mx + b. Por ejemplo:

y = 2x + 5 
y = x - 3 

Por lo tanto, las dos líneas se cruzan cuando y1 = y2 en las mismas coordenadas x, así que ...

2x + 5 = x - 3 
x + 5 = -3 
x = -8 

Cuando x = -8 y1 = y2 y que ha encontrado el Punto de intersección. Esto debería ser muy trivial para traducir en código. Si no hay punto de intersección, la pendiente m de cada línea será igual, en cuyo caso ni siquiera tendrá que realizar el cálculo.

Answer 4

@Jared, gran pregunta y excelente respuesta.

El problema se puede simplificar representando la posición de un punto a lo largo de una línea en función de un único parámetro, como se explica en las preguntas más frecuentes CGA here de Joseph O 'Rourke.

Sea r un parámetro para indicar ubicación de P a lo largo de la línea que contiene AB, con el siguiente significado:

 r=0  P = A 
     r=1  P = B 
     r<0  P is on the backward extension of AB 
     r>1  P is on the forward extension of AB 
     0<r<1 P is interior to AB 

Pensando a lo largo de esas líneas, para cualquier punto C (CX, CY) calculamos r de la siguiente manera:

double deltax = bx - ax; 
double deltay = by - ay; 
double l2 = deltax * deltax + deltay * deltay; 
double r = (ay - cy) * (ay - by) - (ax - cx) * (bx - ax)/l2; 

Esto debería hacer más fácil el cálculo del segmento de superposición.

Tenga en cuenta que evitamos tomar raíces cuadradas porque solo se requiere el cuadrado de la longitud.