16
\$\begingroup\$

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

    }

}
\$\endgroup\$
11
\$\begingroup\$

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])));
}
\$\endgroup\$
  • \$\begingroup\$ Thanks a lot! Line2D is not my class, it is core Java class. And that comparator was made like this by intent - one of the points of algorithm is that lines need to be ordered by their first points. And your code for comparator - yes, when I profiled, I saw that there are problems exactly with comparators. And again, big Thanks! \$\endgroup\$ – Rogach Jan 21 '11 at 15:27
2
\$\begingroup\$

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.

illustration of the problem

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.

\$\endgroup\$
  • \$\begingroup\$ First question after quick look: Won't you get nullpointer exceptions for zero values of rx and ry? \$\endgroup\$ – flup Sep 22 '13 at 11:34
  • \$\begingroup\$ Yes, I most definitely will get problems with vertical lines. I'm rewriting that method again, right now. It turns out that defining that above-below relation properly is no easy task ;) \$\endgroup\$ – Rogach Sep 22 '13 at 15:42
  • \$\begingroup\$ For example, did you know that Line2D.equals() only takes into account reference equality? I did not, and it took me almost an hour to debug the issue :( \$\endgroup\$ – Rogach Sep 22 '13 at 16:17
  • \$\begingroup\$ I updated the code. The compareLines() method is now an abomination, weighting in at 50 lines - but on the bright side, I think I handled all possible corner cases in it. Maybe you know how to simplify it? \$\endgroup\$ – Rogach Sep 22 '13 at 16:22
  • \$\begingroup\$ Heavens! It can do with a bit more comment, at the very least. \$\endgroup\$ – flup Sep 22 '13 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.