将自相交的Path2D算法拆分为多个不自相交路径的方法？

Question

将自相交的Path2D算法拆分为多个不自相交路径的方法？

javaalgorithmgeometrypathgeometry

6

我需要消除形状中的自相交。该形状由一组点构成，因此该形状的所有线段都是直线。（仅为直线，没有曲线和弧线）

之前，我尝试从这些点创建Path2D，从中构建Area，然后使用其PathIterator创建了几个Path2D，这些Path2D 某种程度上是前一个路径的子路径，以便自相交被消除。但是对于某些路径，这种方法不起作用-自相交仍然存在。

那么，您能否指点我在哪里可以找到好的算法来执行类似的操作？ 编辑：我在任何地方都没有找到有用的信息，因此我编写了自己的算法。请参见回答。

- Rogach

一个单独的三次贝塞尔曲线可能会自相交，因此在一般情况下，您需要将贝塞尔曲线细分为两个部分。尝试寻找“贝塞尔曲线细分”或“de Casteljau算法”的良好解释。 - Peter Taylor

@Peter Taylor - 不，正如我所说，没有贝塞尔曲线。只有直线。 - Rogach

我已经成功地使用了“区域（Area）”，从未遇到您所描述的问题。您能否提供一个导致“区域”自相交的路径示例？ - finnw

有点大。但等一下，我会把它发布到Pastebin上。 - Rogach

http://pastebin.com/gjQkxhUv - 一个路径，以及我用来拆分它的方法。 - Rogach

3个回答

1

我收藏了你的问题/答案，以防我自己需要实现类似的东西，但后来我找到了 GEOS 项目，它有一种简单的方法来实现这个。我正在从 Python/Django 调用 GEOS，但整个过程都是基于 JTS（Java Topology Suite），所以我建议从那里开始，并将以下 Python 视为伪代码。

基本上，UNION 操作会将一个线路分成简单连接的部分，如果它不是简单连接的（在这里解释），因此，将线路与其第一个点联合就可以得到我们需要的结果：

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

- Tom

1

如果Area对您不起作用，您可以尝试使用GLUtessellator将您的Shape分解为一组三角形，或者（使用GL_LINE_LOOP选项）只是边界边缘。

- finnw

顺便问一下，你能否发布使用Area进行分割的代码？也许我在我的程序中做错了什么。 - Rogach

@Rogach，我现在没有时间找一个示例，但我简要地查看了你的代码，发现可能有一个错误：你忽略了SEG_CLOSE。当你得到这个标志时，你应该关闭当前的循环（如果需要，在结尾添加第一个点的副本）。虽然这可能不是问题，因为SEG_CLOSE总是跟随SEG_MOVETO或迭代的结束。 - finnw

是的，那可能是个问题。但对于那个路径，“close”总是跟着“move”。不管怎样，我想我有一个很好的分割算法的想法。完成后我会在这个问题中发布它。 - Rogach

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rogach · Accepted Answer

因为我在网上找不到类似的内容，所以我编写了自己的算法。

它可能效率低下，但对于我来说足够快。

下面是算法：

/**
 * 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;
    }
}