Shamos-Hoey algorithm for checking the self-intersection of a closed shape

Question

I implemented the Shamos-Hoey algorithm to check if a closed shape is self-intersected. Is this algorithm ok in terms of performance?

public boolean isSelfIntersected() {
    Set<Line2D> plines = new HashSet<Line2D>();
    for (Path2D ps : this.getPath()) {
        PathIterator p_it = ps.getPathIterator(null, /*flatness*/ 1);
        List<Line2D> estPath = new ArrayList<Line2D>();
        while (!p_it.isDone()) {
            p_it.next();
            double[] coords = new double[6];
            int s = p_it.currentSegment(coords);
            if (s == PathIterator.SEG_LINETO) {
                if (estPath.size() != 0) {
                    Point2D pp = estPath.get(estPath.size() - 1).getP2();
                    estPath.add(new Line2D.Double(pp, new Point2D.Double(coords[0],coords[1])));
                } else {
                    estPath.add(new Line2D.Double(new Point2D.Double(), new Point2D.Double(coords[0],coords[1])));
                }
            }
        }
        for (Line2D lq : estPath) {
            plines.add(tweakLine(lq));
        }
    }
    return ShamosHoeyAlgorithm(plines);

}

/**
 * Moves first point of the line by 0.0000001 of it's length.
 * @return
 */
static Line2D tweakLine(Line2D l) {
    Line2D ql = new Line2D.Double(
            l.getX1() + 0.0000001*(l.getX2() - l.getX1()),
            l.getY1() + 0.0000001*(l.getY2() - l.getY1()),
            l.getX2() - 0.0000001*(l.getX2() - l.getX1()),
            l.getY2() - 0.0000001*(l.getY2() - l.getY1()));
    return ql;
}

public class ShamosHoeyAlgorithm {

    public static boolean ShamosHoeyAlgorithm(Collection<Line2D> lines) {
        List<AlgEvent> events = new ArrayList<AlgEvent>(lines.size() * 2);
        for (Line2D li : lines) {
            if (li.getX1() < li.getX2()) {
                Line2D l = new Line2D.Double(li.getP1(), li.getP2());
                events.add(new AlgEvent(l, true));
                events.add(new AlgEvent(l, false));
            } else if (li.getX1() > li.getX2()) {
                Line2D l = new Line2D.Double(li.getP2(), li.getP1());
                events.add(new AlgEvent(l, true));
                events.add(new AlgEvent(l, false));
            } else {
                if (li.getY1() < li.getY2()) {
                    Line2D l = new Line2D.Double(li.getP1(), li.getP2());
                    events.add(new AlgEvent(l, true));
                    events.add(new AlgEvent(l, false));
                } else if (li.getY1() > li.getY2()) {
                    Line2D l = new Line2D.Double(li.getP2(), li.getP1());
                    events.add(new AlgEvent(l, true));
                    events.add(new AlgEvent(l, false));
                } else {
                    return true;
                }
            }
        }
        Collections.sort(events, new AlgEvtComparator());
        TreeSet<Line2D> sl = new TreeSet<Line2D>(new LineComparator());
        for (AlgEvent e : events) {
            if (e.isStart) {
                Line2D nl = e.line;
                Line2D above = sl.higher(nl);
                if (above != null) {
                    if (above.intersectsLine(nl)) {
                        return true;
                    }
                }
                Line2D below = sl.lower(nl);
                if (below != null) {
                    if (below.intersectsLine(nl)) {
                        return true;
                    }
                }
                sl.add(nl);
            } else {
                Line2D nl = e.line;
                Line2D above = sl.higher(nl);
                Line2D below = sl.lower(nl);
                sl.remove(nl);
                if (above != null && below != null) {
                    if (above.intersectsLine(below)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    static class AlgEvent {

        public Line2D line;
        public boolean isStart;

        AlgEvent(Line2D l, boolean isStart) {
            line = l;
            this.isStart = isStart;
        }

        Point2D getPoint() {
            return (isStart) ? line.getP1() : line.getP2();
        }

        double getX() {
            return (isStart) ? line.getX1() : line.getX2();
        }

        double getY() {
            return (isStart) ? line.getY1() : line.getY2();
        }

        @Override
        public String toString() {
            return "start =  " + isStart + ", point = " + this.getPoint() + ", line = " + line.getP1() + " : " + line.getP2();
        }

    }

    static class AlgEvtComparator implements Comparator<AlgEvent> {

        public int compare(AlgEvent o1, AlgEvent o2) {
            if (o1.getX() < o2.getX()) {
                return -1;
            } else if (o1.getX() > o2.getX()) {
                return 1;
            } else {
                if (o1.getY() < o2.getY()) {
                    return -1;
                } else {
                    return 1;
                }
            }
        }

    }

    /**
     * Class to compare lines, to ensure above-below order.
     */
    static class LineComparator implements Comparator<Line2D> {

        public int compare(Line2D o1, Line2D o2) {
            if (o1.getY1() < o2.getY1()) {
                return -1;
            } else if (o1.getY1() > o2.getY2()) {
                return 1;
            } else {
                if (o1.getY2() < o2.getY2()) {
                    return -1;
                } else if (o1.getY2() > o2.getY2()) {
                    return 1;
                } else {
                    return 0;
                }
            }
        }

    }

}

Answer 1

The question of whether your code is performant enough is something your profiler can better answer for you. But from looking through the code above I notice quite a bit of duplication along with some rather deeply nested if's which you should try to refactor. Take this for example:

        if (li.getX1() < li.getX2()) {
            Line2D l = new Line2D.Double(li.getP1(), li.getP2());
            events.add(new AlgEvent(l, true));
            events.add(new AlgEvent(l, false));
        } else if (li.getX1() > li.getX2()) {
            Line2D l = new Line2D.Double(li.getP2(), li.getP1());
            events.add(new AlgEvent(l, true));
            events.add(new AlgEvent(l, false));
        } else {
            if (li.getY1() < li.getY2()) {
                Line2D l = new Line2D.Double(li.getP1(), li.getP2());
                events.add(new AlgEvent(l, true));
                events.add(new AlgEvent(l, false));
            } else if (li.getY1() > li.getY2()) {
                Line2D l = new Line2D.Double(li.getP2(), li.getP1());
                events.add(new AlgEvent(l, true));
                events.add(new AlgEvent(l, false));
            } else
          // ...

The two statements events.add(new AlgEvent(l, true)); and events.add(new AlgEvent(l, false)); are being repeated 4 times here!

Your line compare method here:

static class LineComparator implements Comparator<Line2D> {
    public int compare(Line2D o1, Line2D o2) {
        if (o1.getY1() < o2.getY1()) {
            return -1;
        } else if (o1.getY1() > o2.getY2()) {
       // ...
}

can be shorted by taking advantage of logical short-circuit and the ternary operator. So something like this might be easier to read:

    public int compare(Line2D o1, Line2D o2)
    {
        /* I'm not too familiar with java but can
           the equals method be used here to check
           if the lines are equal?
         */
        // if( o1.equals(o2) ) return 0;

        return (o1.getY1() < o2.getY1() || 
                o1.getY2() < o2.getY2()) ? -1 :
               (o1.getY1() > o2.getY2() ||
                o1.getY2() > o2.getY2()) ? 1 : 0;
    }

You can apply the same idea to AlgEvtComparator's compare method. One other thing I noticed in your line compare method, the checks' aren't exactly symmetrical. You have o1.Y1 comparing to o2.Y2 while all the others are checking Y1 to Y1 or Y2 to Y2. Was that really intended? I think this deserves a comment.

I'm guessing Line2D is a class you have defined somewhere. You might want to see if you're abstracting its usage enough or if an 'in-between' class is needed. The following code looks like it's leaking stuffing behind Line2D's interface:

if (estPath.size() != 0) {
  Point2D pp = estPath.get(estPath.size() - 1).getP2();
  estPath.add(new Line2D.Double(pp, new Point2D.Double(coords[0],coords[1])));
} else {
  estPath.add(new Line2D.Double(new Point2D.Double(), new Point2D.Double(coords[0],coords[1])));
}

Answer 2

Performance aside, I think your LineComparator is incorrect(!) as it compares the points where the sweepline initially ran into the segments. The sweepline has swept on in the meanwhile and therefore, while the ordering of the segments on the sweepline has not changed, the actual location of their intersections with the sweepline has moved and you need to account for this when trying to figure out where to insert a new segment in the sweepline.

When the vertical sweepline encounters segment number 5, it shouldn't compare its intersection point with 5 with the grey intersectionpoints of 1, 2, 3, and 4. If it does that, it'll insert 5 at the top. It needs to compare its intersection point with 5 with its current red intersection points with segments 1, 2, 3, and 4 and insert number 5 right in the middle.