将自相交Path2D分成几个非自相交路径的算法？
我需要摆脱形状中的自相交。 形状由点arrays构成，因此该形状的所有段都是线。 （ 只有线条，没有曲线和弧线）
以前，我尝试从那些点创建Path2D，从中构造一个Area，然后使用它的PathIterator我创建了几个Path2D，它们不知何故是前一个路径的子路径，因此自相交消失了。 但这对某些路径不起作用 – 自我交叉仍然存在。
所以你能指点我能在哪些地方找到做类似事情的好算法吗？
编辑：我在任何地方都找不到任何有用的东西，所以我编写了自己的算法。 看到答案。
如果Area不适合您，您可以尝试使用GLUtessellator将Shape分解为一组三角形，或者（使用GL_LINE_LOOP选项）仅将边界边缘分解。
所以，由于我无法在网上找到这样的东西，我编写了自己的算法。
它可能是疯狂无效的，但它对我来说足够快。
它来了：
/** * 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> splitPath(List lines) { List> splitted = new ArrayList>(); // 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 subpath1 = new ArrayList (); 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 subpath2 = new ArrayList (); 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; } }
我给你的问题/答案添加了书签，以防我必须自己实现类似的东西，但后来我找到了GEOS项目，它有一个简单的方法来实现这一点。 我正在使用Python / Django调用GEOS，但整个过程基于JTS（Java拓扑套件），所以我从那里开始将以下Python视为伪代码。
基本上，UNION操作会将一条线分成简单连接的部分，如果它不是简单地连接（ 在这里解释），那么用它的第一点UNIONing线就可以满足我们的需要：
line = LineString(list_of_lines_x_y_coordinates) # union with first point splits into MultiLineString containing segments segments = line.union(line[0])