¿Algoritmo para dividir Path2D ininterrollado en varios caminos no ininterreccionados?

Question

Necesito deshacerme de las auto-intermedias en forma. La forma se construye a partir de una variedad de puntos, por lo que todos los segmentos de esa forma son líneas. (solamente líneas, sin curvas y arcos)

Anteriormente, intenté crear Path2D desde esos puntos, construir un área a partir de él y luego, usando su patterador, creé varios Path2DS, que de alguna manera eran subpatas de ruta anterior, por lo que se habían ido las intermediciones. Pero esto no funciona para algunos caminos: las intermediarias aún permanecen allí.

Entonces, ¿podrías señalarme algún lugar donde pueda encontrar un buen algoritmo para hacer algo similar?

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

Answer 1

Si Area no funciona para usted, podría intentar usar un GlutaSelator para descomponer tu Shape en un conjunto de triángulos, o (usando el GL_LINE_LOOP opción) solo los bordes límite.

Answer 2

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

Puede ser increíblemente 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

Marcé su pregunta/respuesta en caso de que tuviera que implementar algo similar, pero luego encontré el Geos Proyecto que tiene una forma simple de lograr esto. Estoy llamando a Geos de Python/Django, pero todo se basa en JTS (Java Topology Suite) Así que comenzaría allí y trataría a la siguiente pitón como psedo-código.

Básicamente, la operación de la Unión dividirá una línea en piezas simplemente conectadas si no está simplemente conectada (explicada aquí), por lo que unir la línea con su primer punto hace lo que necesitamos:

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