5

シェイプ内の自己交差を取り除く必要があります。形状は点の配列から構成されるため、その形状のすべてのセグメントは線です。(直線のみ、曲線と円弧なし)

以前、そのポイントから Path2D を作成し、そこから Area を構築しようとしました。次に、その PathIterator を使用して、前のパスのサブパスであるいくつかの Path2D を作成したため、自己交差がなくなりました。しかし、これは一部のパスでは機能しません。自己交差はまだ残っています。

では、同様のことを行うための優れたアルゴリズムを見つけることができる場所を教えていただけますか?

編集:どこにも役立つものが見つからなかったので、独自のアルゴリズムを作成しました。答えを見てください。

4

3 に答える 3

1

Areaがうまくいかない場合は、 GLUtessellatorShapeを使用して、三角形のセットに分解するか、（GL_LINE_LOOPオプションを使用して）境界エッジのみに分解してみてください。

于 2011-01-31T12:48:00.813 に答える
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])
于 2011-02-28T09:34:55.413 に答える
1

それで、ウェブ上でこのようなものを見つけることができなかったので、私は独自のアルゴリズムを書きました。

それは非常に効果がないかもしれませんが、私にとっては十分に速く機能します.

ここに行きます：

/**
 * 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;
    }
}
于 2011-01-31T15:02:50.183 に答える