Шамос-Хоя алгоритм проверки самопересечения замкнутой формы


Я реализовал Шамос-Хоя алгоритм, чтобы проверить, если закрытая форма является самопересекающимся. Этот алгоритм хорошо с точки зрения производительности?

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

    }

}


3448
16
задан 20 января 2011 в 05:01 Источник Поделиться
Комментарии