Shamos-Hoey-Algorithmus zur Überprüfung des Selbstschnittpunkts einer geschlossenen Form

3451
Rogach

Ich habe den Shamos-Hoey-Algorithmus implementiert, um zu prüfen, ob sich eine geschlossene Form selbst schneidet. Ist dieser Algorithmus in Bezug auf die Leistung in Ordnung?

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

    }

}
Antworten
17

2 Antworten auf die Frage

11
greatwolf

Die Frage, ob Ihr Code performant genug ist, kann Ihr Profiler für Sie besser beantworten. Aber wenn ich den Code durchblättere, bemerke ich ziemlich viel Duplizierung zusammen mit einigen ziemlich tief verschachtelten If's, die Sie versuchen sollten, umzuformen. Nehmen Sie dies zum Beispiel:

        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
          // ...

Die beiden Aussagen events.add(new AlgEvent(l, true));und events.add(new AlgEvent(l, false));werden hier 4 mal wiederholt!

Ihre Linienvergleichsmethode hier:

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()) {
       // ...
}

kann durch Ausnutzung des logischen Kurzschlusses und des ternären Operators kurzgeschlossen werden. So etwas könnte leichter zu lesen sein:

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

Sie können dieselbe Idee auf die Vergleichsmethode von AlgEvtComparator anwenden. Eine andere Sache, die mir bei Ihrer Zeilenvergleichsmethode aufgefallen ist, die Checks sind nicht genau symmetrisch. Sie haben o1.Y1 im Vergleich zu o2.Y2, während alle anderen Y1 zu Y1 oder Y2 zu Y2 prüfen. War das wirklich beabsichtigt? Ich denke, das verdient einen Kommentar.

Ich vermute, Line2D ist eine Klasse, die Sie irgendwo definiert haben. Vielleicht möchten Sie sehen, ob Sie die Verwendung genug abstrahieren oder ob eine Zwischenklasse erforderlich ist. Der folgende Code sieht so aus, als würde er hinter der Schnittstelle von Line2D herumlaufen:

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])));
}
Danke vielmals! Line2D ist nicht meine Klasse, es ist die Java-Kernklasse. Und dieser Komparator wurde aus Vorsatz so erstellt - einer der Punkte des Algorithmus ist, dass Linien nach ihren ersten Punkten geordnet werden müssen. Und Ihren Code für Komparatoren - ja, als ich ein Profil erstellt habe, habe ich gesehen, dass es Probleme mit Komparatoren gibt. Und nochmals vielen Dank! Rogach vor 9 Jahren 0
2
flup

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.

Erste Frage nach einem kurzen Blick: Erhalten Sie nicht nullpointer-Ausnahmen für die Nullwerte von rx und ry? flup vor 7 Jahren 0
Ja, ich werde definitiv Probleme mit vertikalen Linien bekommen. Ich schreibe diese Methode jetzt wieder um. Es stellt sich heraus, dass es nicht einfach ist, die Beziehung von oben nach unten richtig zu definieren;) Rogach vor 7 Jahren 0
Wussten Sie zum Beispiel, dass Line2D.equals () nur die Referenzgleichheit berücksichtigt? Ich habe es nicht getan, und ich habe fast eine Stunde gebraucht, um das Problem zu beheben :( Rogach vor 7 Jahren 0
Ich habe den Code aktualisiert. Die Methode 'compareLines ()' ist jetzt ein Gräuel, mit 50 Zeilen gewichtet - aber auf der guten Seite habe ich alle möglichen Eckfälle behandelt. Vielleicht wissen Sie, wie Sie es vereinfachen können? Rogach vor 7 Jahren 0
Himmel! Es kann zumindest mit etwas mehr Kommentar auskommen. flup vor 7 Jahren 0