Алгоритм разделения самопересекающихся Path2D на несколько непересекающихся путей? - PullRequest
Новая
       38

Алгоритм разделения самопересекающихся Path2D на несколько непересекающихся путей?

5 голосов
/ 31 января 2011

Мне нужно избавиться от самопересечений в форме. Форма построена из массива точек, поэтому все сегменты этой формы являются линиями. ( только линии, без кривых и дуг)

Ранее я пытался создать Path2D из этих точек, построить из него Area, а затем с помощью PathIterator я создал несколько Path2D, которые так или иначе были подпутями предыдущего пути, и поэтому самопересечения ушел. Но это не работает для некоторых путей - самопересечения все еще остаются там.

Так не могли бы вы указать мне место, где я могу найти хороший алгоритм для подобных вещей?

Редактировать: Я не нашел ничего полезного, поэтому я написал свой собственный алгоритм. Смотрите ответы.

Ответы [ 3 ]

1 голос
/ 31 января 2011

Итак, поскольку я не смог найти ничего подобного в Интернете, я написал свой собственный алгоритм.

Это может быть безумно неэффективно, но работает достаточно быстро для меня.

Вот так: 

/**
 * 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;
    }
}
1 голос
/ 28 февраля 2011

Я отметил ваш вопрос / ответ на тот случай, если мне нужно было реализовать что-то подобное самостоятельно, но затем я нашел проект GEOS , который имеет простой способ добиться этого. Я звоню в GEOS из Python / Django, но все это основано на JTS (Java Topology Suite) , поэтому я бы начал с него и рассматривал следующий Python как псевдо-код.

По сути, операция UNION разбивает линию на просто соединенные части, если она не просто подключена (объяснено здесь ), поэтому UNION объединяет строку с ее первой точкой, что нам нужно: 

line  = LineString(list_of_lines_x_y_coordinates)
# union with first point splits into MultiLineString containing segments
segments = line.union(line[0])
1 голос
/ 31 января 2011

Если Area не работает для вас, вы можете попробовать использовать GLUtessellator для разложения вашего Shape на набор треугольников или (используя опцию GL_LINE_LOOP) только граничные ребра.

...