Algorithm to split self-intersected Path2D into several not self-intersected paths?

Question

I need to get rid of self-intersections in a shape. Shape is constructed from an array of points, so all segments of that shape are lines. (only lines, no curves and arcs)

Previously, I tried to create Path2D from that points, construct an Area from it, and then using its PathIterator I created several Path2Ds, which somehow were subpaths of previous path, and so self-intersetions were gone. But this isn't working for some paths - self-intersections still remain there.

So could you point me to some place where I can find good algorithm to do similar thing?

Edit: I haven't found anything useful anywhere, so I written my own algorithm. See the answers.

A single cubic Bézier can self-intersect, so in the general case you'll going to need to subdivide a Bézier into two. Try looking for a good explanation of "Bézier curve subdivision" or "de Casteljau's algorithm". — Peter Taylor, Jan 31 '11 at 10:40
@Peter Taylor - No, as I said, there are no bezier curves. Only lines. — Rogach, Jan 31 '11 at 10:46
I have done this successfully using an `Area` and never seen the problem that you describe. Can you post an example of a path that results in an `Area` with self-intersections? — finnw, Jan 31 '11 at 12:34
It is a bit big. But wait a minute, I'll post it to pastebin. — Rogach, Jan 31 '11 at 12:44
http://pastebin.com/gjQkxhUv - a path, and a method I used to split it. — Rogach, Jan 31 '11 at 12:49

score 2 · Answer 1 · answered Jan 31 '11 at 15:02

So, since I was unable to find anything like this on the web, I written my own algorithm.

It may be insanely ineffective, but it works fast enough for me.

Here it goes:

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

I have been looking at this issue too - I suspect you algorithm does not handle secondary intersections (If there is an intersection between subpath1 and subpath2 — tofarr, Feb 23 '11 at 16:46
Yes, I missed that. I'll think of a better algorithm. Thanks for noticing! — Rogach, Mar 02 '11 at 17:27

finnw · Accepted Answer · 2011-01-31T12:57:39.560

1

If Area is not working for you, you could try using a GLUtessellator to decompose your Shape into a set of triangles, or (using the GL_LINE_LOOP option) just the boundary edges.

edited Jan 31 '11 at 12:57

answered Jan 31 '11 at 12:48

finnw

47,861
24
143
221

By the way, could you post your code for splitting using Area? Maybe I'm doing something wrong in my program. – Rogach Jan 31 '11 at 13:13
@Rogach, I don't have time to find a sample right now but I looked at your code briefly and I noticed one possible bug: you ignore `SEG_CLOSE`. When you get that flag you should close the current loop (adding a copy of the first point to the end if necessary.) That may not be the problem though as `SEG_CLOSE` is always followed by `SEG_MOVETO` or by the end of the iteration. – finnw Jan 31 '11 at 13:17
Yes, that may be a problem. But for that path, "close" was always followed by "move". Anyway, I think I have good idea for splitting algorithm. I'll post it in this question when I'm done. – Rogach Jan 31 '11 at 13:58

score 1 · Answer 3 · answered Feb 28 '11 at 09:34

I bookmarked your question/answer in case I had to implement something similar myself, but then I found the GEOS project which has a simple way of achieving this. I'm calling GEOS from Python/Django, but the whole thing is based on JTS (Java Topology Suite) so I'd start there and treat the following Python as psuedo-code.

Basically, the UNION operation will split a line into simply connected parts if it is not simply connected (explained here), so UNIONing the line with it's first point does what we need:

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

Algorithm to split self-intersected Path2D into several not self-intersected paths?

3 Answers3

Linked