Algoritmo de Búsqueda de Forma Cuadrilátera

Se pueden completar aproximadamente cuatro líneas para formar un cuadrilátero si no se imponen restricciones a los ángulos, etc.

Imagen con cuadriláteros potencialmente incorrectos:

Probablemente no quieras incluir cuadriláteros como el amarillo que se muestra en mi ejemplo. Debe tener restricciones en los ángulos, tamaño mínimo/máximo, relación de aspecto y el grado de finalización permitido. Si el 90 por ciento de las líneas tiene que ser añadido con el fin de formar un cuadrilátero completo esto sería probablemente no sea un buen candidato.

Me temo que tendrá que probar todas las combinaciones posibles de líneas y aplicar una heurística en ellas para darles puntos. Muchos puntos para ángulos cercanos a 90 grados (si lo que desea son rectángulos), para integridad, para relaciones de aspecto cercanas a la esperada, etc.

ACTUALIZACIÓN

Usar un sistema de puntos tiene ventajas sobre simplemente aplicar reglas estrictas.

• Un sistema de puntos le permite evaluar la calidad de los cuadriláteros y tomar el mejor o rechazar un cuadrilátero por completo.
• La buena calidad de una propiedad puede ayudar a superar la mala calidad de otra.
• Le permite dar diferentes pesos a diferentes propiedades.

Digamos que tienes una regla estricta (en pseudo código):

(angles == 90 +/- 10 degrees) && (line_completeness>50%)

Esto funcionaría, sin embargo puede conducir a situaciones como angles == 90 +/- 1 degree) && (line_completeness == 45%). De acuerdo con las reglas este cuadrilátero no pasaría debido a la pobre integridad de la línea; sin embargo, la calidad de los ángulos es excepcional, todavía por lo que es un muy buen candidato.

Es mejor dar puntos. Digamos 20 puntos para un ángulo de exactamente 90 grados, cayendo a 0 puntos para un ángulo de 90 + / -15 grados y 10 puntos para líneas completas hacia 0 puntos para líneas completas solo en un 25%, por ejemplo. Esto hace que los ángulos sean más importantes que la integridad de la línea y también crea condiciones más suaves para un problema que no tiene reglas absolutas.

No uso C# por lo que tendrás que traducir el código. El siguiente código está en Java. Lo probé con el caso de prueba incluido. Aún no se como agregar archivos adjuntos a stackoverflow, así que estoy incluyendo el código real aquí.

Hay cuatro clases (ShapeFinder, Línea, Punto y Cuadrilátero) y una clase de prueba (ShapeFinderTest):

Clase ShapeFinder:

package stackoverflow;

import java.util.ArrayList;
import java.util.List;

public class ShapeFinder {

  private List<Line> lines;
  private List<Quadrilateral> allQuadrilaterals;

  /*
   * I am assuming your segments are in a list of arrays:
   * [{{x1,y1,},{x2,y2}}, {{x1,y1,},{x2,y2}}, {{x1,y1,},{x2,y2}}]
   * You can change this.
   *
   * So basically you call ShapeFinder with a list of your line segments.
   */
  public ShapeFinder(List<Double[][]> allSegments) {
    lines = new ArrayList<Line>(allSegments.size());
    allQuadrilaterals = new ArrayList<Quadrilateral>();
    for (Double[][] segment : allSegments) {
      addSlopeInterceptForm(segment);
    }
  }

  /**
   * You call this function to compute all possible quadrilaterals for you.
   */
  public List<Quadrilateral> completeQuadrilaterals() {
    for (int w = 0; w < lines.size(); w++) {
      for (int x = w + 1; x < lines.size(); x++) {
        for (int y = x + 1; y < lines.size(); y++) {
          for (int z = y + 1; z < lines.size(); z++) {
            addQuadrilateral(w, x, y, z);
          }
        }
      }
    }
    return allQuadrilaterals;
  }

  //assume {{x1,y1,},{x2,y2}}
  private void addSlopeInterceptForm(Double[][] s) {
    double x1 = s[0][0];
    double y1 = s[0][1];
    double x2 = s[1][0];
    double y2 = s[1][1];
    double m = (y1 - y2) / (x1 - x2);
    double b = y2 - m * x2;

    if (isInfinityOrNaN(m)) {
      m = Double.NaN;
      b = x1;
    }

    lines.add(new Line(m, b));
  }

  /*
   * Given four lines, this function creates a quadrilateral if possible
   */
  private void addQuadrilateral(int w, int x, int y, int z) {
    Point wx = intersect(w, x);
    Point wy = intersect(w, y);
    Point wz = intersect(w, z);
    Point xy = intersect(x, y);
    Point xz = intersect(x, z);
    Point yz = intersect(y, z);

    if (notNull(wx) && notNull(xy) && notNull(yz) && notNull(wz) && isNull(wy) && isNull(xz)) {
      allQuadrilaterals.add(new Quadrilateral(wx, xy, yz, wz));
    }
  }

  private Point intersect(int c, int d) {
    double m1 = lines.get(c).slope;
    double b1 = lines.get(c).intercept;
    double m2 = lines.get(d).slope;
    double b2 = lines.get(d).intercept;

    double xCor, yCor;
    if ((isInfinityOrNaN(m1) && !isInfinityOrNaN(m2)) || (!isInfinityOrNaN(m1) && isInfinityOrNaN(m2))) {
      xCor = isInfinityOrNaN(m1) ? b1 : b2;
      yCor = isInfinityOrNaN(m1) ? m2 * xCor + b2 : m1 * xCor + b1;;
    } else {
      xCor = (b2 - b1) / (m1 - m2);
      yCor = m1 * xCor + b1;
    }

    if (isInfinityOrNaN(xCor) || isInfinityOrNaN(yCor)) {
      return null;
    }
    return new Point(xCor, yCor);
  }

  private boolean isInfinityOrNaN(double d){
    return Double.isInfinite(d)||Double.isNaN(d);
  }

  private boolean notNull(Point p) {
    return null != p;
  }

  private boolean isNull(Point p) {
    return null == p;
  }
}

Clase de línea:

package stackoverflow;

public class Line {

  double slope;
  double intercept;

  public Line(double slope, double intercept) {
    this.slope = slope;
    this.intercept = intercept;
  }
}

Clase de punto:

package stackoverflow;

class Point {

  double xCor;
  double yCor;

  public Point(double xCor, double yCor) {
    this.xCor = xCor;
    this.yCor = yCor;
  }

  public String toString(){
    return "("+xCor+","+yCor+")";
  }
}

Cuadrilátero clase:

package stackoverflow;

public class Quadrilateral {

  private Point w, x, y, z;

  public Quadrilateral(Point w, Point x, Point y, Point z) {
    this.w = w;
    this.x = x;
    this.y = y;
    this.z = z;
  }

  public String toString() {
    return "[" + w.toString() + ", " + x.toString() + ", " + y.toString() + ", " + z.toString() + "]";
  }
}

PRUEBA UNITARIA:

package stackoverflow;

import java.util.ArrayList;
import java.util.List;
import org.junit.Test;

public class ShapeFinderTest {

  @Test
  public void testCompleteQuadrilaterals() {
    List<Double[][]> lines = new ArrayList<>();
    lines.add(new Double[][]{{2., 5.}, {6., 5.}});
    lines.add(new Double[][]{{2., 1.}, {2., 5.}});
    lines.add(new Double[][]{{2., 1.}, {6., 1.}});
    lines.add(new Double[][]{{6., 5.}, {6., 1.}});
    lines.add(new Double[][]{{0., 0.}, {5., 1.}});
    lines.add(new Double[][]{{5., 5.}, {10., 25.}});
    ShapeFinder instance = new ShapeFinder(lines);
    List<Quadrilateral> result = instance.completeQuadrilaterals();

    for (Quadrilateral q : result) {
      System.out.println(q.toString());
    }
  }
}

De los ejemplos, asumo que la pregunta está más a lo largo de las líneas de Encontrar todos los cuadriláteros que tienen una línea contenida completamente dentro de cada uno de sus lados. Esto no está del todo claro en la explicación proporcionada.

A continuación se muestra un pseudocódigo razonablemente fácil de implementar. Ahora solo para crear una estructura de datos eficiente para evitar la complejidad O (N^4). Tal vez ordenar las líneas por posición o gradiente.

I,j,k, l son los siguientes:

   l
 |---|
j|   |k
 |---|
   i

extendIntersect es simplemente una función eso extiende las 2 líneas hasta el infinito (o hasta los límites que elija) y devuelve el punto donde se cruzan, fácil de hacer matemáticamente.

onLine devuelve true si un punto se encuentra en una línea.

onSameSide devuelve true si ambos puntos se encuentran en el mismo lado de una línea

for (Line i = lines[0]:lines[lineCount])
  for (Line j = lines[1]:lines[lineCount])
    Point ijIntersect = extendIntersect(i, j)
    if (ijIntersect == NULL || onLine(ijIntersect, i) || onLine(ijIntersect, j))
      continue;
    for (Line k = lines[2]:lines[lineCount])
      Point ikIntersect = extendIntersect(i, k)
      if (ikIntersect == NULL || onLine(ikIntersect, i) || onLine(ikIntersect, k) ||
          onSameSide(ijIntersect, ikIntersect, i)) continue
      for (Line l = lines[3]:lines[lineCount])
        Point jlIntersect = extendIntersect(j, l)
        Point klIntersect = extendIntersect(k, l)
        if (jlIntersect == NULL || onLine(jlIntersect, j) || onLine(jlIntersect, l) ||
            klIntersect == NULL || onLine(klIntersect, k) || onLine(klIntersect, l) ||
            onSameSide(jlIntersect, ijIntersect, j) ||
            onSameSide(klIntersect, ikIntersect, k)) continue
        printQuad(ijIntersect, ikIntersect, klIntersect, jlIntersect)

Algún tipo de comprobación de errores como Drew Noakes sugirió también podría ser una buena idea.