¿Algoritmo para dividir el Path2D autointersectado en varias rutas no autointersecables?

Question

Necesito deshacerme de las autointersecciones en una forma. La forma se construye a partir de una matriz de puntos, por lo que todos los segmentos de esa forma son líneas. (sólo líneas, no hay curvas y arcos)

Anteriormente, he tratado de crear Path2D de que los puntos, construir un espacio de ella, y luego usando su PathIterator creé varios Path2Ds, que alguna manera fueron subtrazados de los anteriores camino, y entonces auto-intersecciones se habían ido. Pero esto no está funcionando en algunos caminos: las autointersecciones aún permanecen allí.

¿Podría indicarme algún lugar donde pueda encontrar un buen algoritmo para hacer algo similar?

Editar: No he encontrado nada útil en ninguna parte, así que escribí mi propio algoritmo. Ver las respuestas

Answer 1

Si Area no funciona para usted, usted podría tratar de usar un GLUtessellator para descomponer sus Shape en un conjunto de triángulos, o (usando la opción GL_LINE_LOOP) sólo los bordes de contorno.

Answer 2

Entonces, como no pude encontrar nada como esto en la web, escribí mi propio algoritmo.

Puede ser insanamente ineficaz, pero funciona lo suficientemente rápido para mí.

aquí va:

/** 
* Takes a polygon, defined by a list of lines, and splits it into several 
* paths on points of intersection. If non-self-intersected path is passed in, 
* the same path is returned. 
* @param path 
* @return 
*/ 
public static List<List<Line2D>> splitPath(List<Line2D> lines) { 
    List<List<Line2D>> splitted = new ArrayList<List<Line2D>>(); 
    // find intersections. 
    loop1: 
    for (Line2D l1 : lines) { 
     for (Line2D l2 : lines) { 
      if (l1 == l2) continue; 
      Point2D intr; 
      if ((intr = linesIntersect(l1, l2)) != null) { 
       // creating two splitted subpaths 
       int i1 = lines.indexOf(l1); 
       int i2 = lines.indexOf(l2); 

       List<Line2D> subpath1 = new ArrayList<Line2D>(); 
       subpath1.addAll(lines.subList(0, i1)); 
       subpath1.add(new Line2D.Double(l1.getP1(), intr)); 
       subpath1.add(new Line2D.Double(intr, l2.getP2())); 
       subpath1.addAll(lines.subList(i2 + 1, lines.size())); 
       splitted.addAll(splitPath(subpath1)); 

       List<Line2D> subpath2 = new ArrayList<Line2D>(); 
       subpath2.add(new Line2D.Double(intr, l1.getP2())); 
       subpath2.addAll(lines.subList(i1 + 1, i2)); 
       subpath2.add(new Line2D.Double(l2.getP1(), intr)); 
       splitted.addAll(splitPath(subpath2)); 
       break loop1; 
      } 
     } 
    } 
    if (splitted.size() > 0) { 
     return splitted; 
    } else { 
     return Collections.singletonList(lines); 
    } 
} 

/** 
* Returns point of intersection of this line segments. 
* @param l1 
* @param l2 
* @return 
*/ 
public static Point2D linesIntersect(Line2D l1, Line2D l2) { 
    if (l1.getP1().equals(l2.getP2()) || l1.getP2().equals(l2.getP1())) return null; 
    Point2D inter = lineIntersection(l1, l2); 
    if (inter == null) return null; 
    double infS = HEADER.infS; 
    double x = inter.getX(); 
    if (((l1.getX1() > l1.getX2()) ? (x + infS > l1.getX2() && x - infS < l1.getX1()) : (x - infS < l1.getX2() && x + infS > l1.getX1())) && 
      ((l2.getX1() > l2.getX2()) ? (x + infS > l2.getX2() && x - infS < l2.getX1()) : (x - infS < l2.getX2() && x + infS > l2.getX1()))) { 
     return inter; 
    } else { 
     return null; 
    } 
} 

/** 
* Returns point of lines intersection, or null if they are parallel. 
* @param l1 
* @param l2 
* @return 
*/ 
public static Point2D lineIntersection(Line2D l1, Line2D l2) { 
    double a1 = l1.getY2() - l1.getY1(); 
    double b1 = l1.getX1() - l1.getX2(); 
    double c1 = a1*l1.getX1() + b1*l1.getY1(); 
    double a2 = l2.getY2() - l2.getY1(); 
    double b2 = l2.getX1() - l2.getX2(); 
    double c2 = a2*l2.getX1() + b2*l2.getY1(); 
    double det = a1*b2 - a2*b1; 
    if (det != 0) { 
     double x = (b2*c1 - b1*c2)/det; 
     double y = (a1*c2 - a2*c1)/det; 
     return new Point2D.Double(x, y); 
    } else { 
     // lines are parallel 
     return null; 
    } 
} 

Answer 3

que ha agregado un marcador a su pregunta/respuesta en caso de que tuviera que aplicar algo similar a mí mismo, pero luego me encontré con el proyecto GEOS que tiene una forma sencilla de lograr esto. Estoy llamando a GEOS desde Python/Django, pero todo se basa en JTS (Java Topology Suite), así que comenzaría allí y trataría el siguiente Python como código psuedo.

Básicamente, la operación UNION será dividir una línea en partes simplemente conectados si no es simplemente conexa (explicado here), por lo unificante la línea con su primer punto no lo necesitamos:

line = LineString(list_of_lines_x_y_coordinates) 
# union with first point splits into MultiLineString containing segments 
segments = line.union(line[0])