Verlustfreie Polygonvereinfachung?

8

Gibt es einen Standard- / empfohlenen Algorithmus zum Vereinfachen eines Polygons, ohne seine ursprünglichen Grenzen zu verkleinern?

Im Moment verwende ich TopologyPreservingSimplifer in JTS und stoße später in meiner Anwendung auf Probleme, wenn ich auf "verlustbehaftete" Polygone stoße. Idealerweise möchte ich vereinfachte Polygone erzeugen, die kleiner als die konvexe Hülle sind, aber eine Obermenge meines ursprünglichen Polygons bleiben.

vereinfacht

Aktualisieren:

Ich habe schließlich einen zugegebenermaßen unvollkommenen Algorithmus entwickelt, der einen "Wrapper" um das Eingabepolygon legt, ihn verkleinert, bis keine überschüssigen Flächen einen Prozentsatz der Gesamtfläche der Eingabe überschreiten, und dann einen Linienvereinfacher mit einem viel feineren Schwellenwert zum Entfernen ausführt redundante Punkte entlang gerader Linien. 100% datenabhängig, aber ich sehe ungefähr 80% Scheitelpunktkomprimierung mit minimalen überschüssigen Bereichen. Alle Rückmeldungen / Kommentare sind willkommen:

public class LosslessPolygonSimplifier {
protected final static Logger logger = Logger.getLogger(LosslessPolygonSimplifier.class.getName());

public static Polygon simplify(Polygon input) {
    final double AREA_THRESHOLD = 0.005; // allow excesses up to half a percent of total original area
    final double LINE_THRESHOLD = 0.0001; // fine threshold to strip straight lines
    try {
        if (!input.isSimple()) {
            logger.warning("Attempting to simplify complex polygon!");
        }
        Polygon simple = simplifyInternal(input, AREA_THRESHOLD, LINE_THRESHOLD);
        return simple;
    }
    catch (Exception e) {
        logger.log(Level.WARNING, "Failed to simplify. Resorting to convex hull.\n " + input.toText(), e);
        try {
            // worst case scenario - fall back to convex hull
            // probably a result of a bow-tie LINESTRING that doubles back on itself due to precision loss?
            return (Polygon) input.convexHull();
        }
        catch (Exception e2) {
            // Is this even possible? Polygons that cross the anti-meridian?
            logger.log(Level.SEVERE, "Failed to simplify to convex hull: " + input.toText(), e2);
            return input; // Garbage In, Garbage Out
        }
    }
}

// TODO avoid creating triangles on long straight edges
public static Polygon simplifyInternal(Polygon original, double areaThreshold, double lineThreshold) {
    GeometryFactory gf = new GeometryFactory();
    Geometry excesses, excess, keepTotal, keepA, keepB, chA, chB, keep = null, elim = null;
    Polygon simplified = null, wrapper = (Polygon) original.convexHull();
    try {
        boolean done = false;
        while (!done) {
            done = true;
            excesses = wrapper.difference(original);
            for (int i = 0; i < excesses.getNumGeometries(); i++) {
                excess = excesses.getGeometryN(i);
                if (excess.getArea() / original.getArea() > areaThreshold) {
                    done = false; // excess too big - try to split then shrink
                    keepTotal = excess.intersection(original);
                    keepA = gf.createGeometryCollection(null);
                    keepB = gf.createGeometryCollection(null);
                    for (int j = 0; j < keepTotal.getNumGeometries(); j++) {
                        if (j < keepTotal.getNumGeometries() / 2) {
                            keepA = keepA.union(keepTotal.getGeometryN(j));
                        }
                        else {
                            keepB = keepB.union(keepTotal.getGeometryN(j));
                        }
                    }
                    chA = keepA.convexHull();
                    chB = keepB.convexHull();
                    keep = gf.createMultiPolygon(null);
                    if (chA instanceof Polygon) {
                        keep = keep.union(chA);
                    }
                    if (chB instanceof Polygon) {
                        keep = keep.union(chB);
                    }
                    elim = excess.difference(keep);
                    wrapper = (Polygon) wrapper.difference(elim);
                }
            }
        }
        new Assert(wrapper.getArea() >= original.getArea());
        new Assert(wrapper.getArea() <= original.convexHull().getArea());
        simplified = (Polygon) com.vividsolutions.jts.simplify.TopologyPreservingSimplifier.simplify(wrapper, lineThreshold);
        new Assert(simplified.getNumPoints() <= original.getNumPoints());
        new Assert(simplified.getNumInteriorRing() == 0);
        new Assert(simplified.isSimple());
        return simplified;
    }
    catch (Exception e) {
        if (original.isSimple()) {
            StringBuilder sb = new StringBuilder();
            sb.append("Failed to simplify non-complex polygon!");
            sb.append("\noriginal: " + original.toText());
            sb.append("\nwrapper: " + (null == wrapper ? "" : wrapper.toText()));
            sb.append("\nsimplified: " + (null == simplified ? "" : simplified.toText()));
            sb.append("\nkeep: " + (null == keep ? "" : keep.toText()));
            sb.append("\nelim: " + (null == elim ? "" : elim.toText()));
            logger.log(Level.SEVERE, sb.toString());
        }
        throw e;
    }
}

}}

user1538028
quelle
5
1. Warum würden Sie es verlustfreie Vereinfachung nennen? Ich denke, wenn Sie eine Grenze vereinfachen, verlieren Sie Details. 2. Sie könnten Grenzen vereinfachen und verlustfreie Bereiche haben , aber das würde Ihr Kriterium brechen, Grenzen nicht zu verkleinern. 3. Warum möchten Sie zulassen, dass Grenzen erweitert und nicht verkleinert werden? Oder verstehe ich etwas falsch?
Martin F
1
Meine Daten repräsentieren politische Grenzen. Ich bin mit einer kleinen Erweiterung des ursprünglichen Bereichs einverstanden, wenn dies dazu beiträgt, die Anzahl der Scheitelpunkte zu senken. Ich möchte vermeiden, Menschen aus dem ursprünglichen Gebiet auszusondern. Ihr Recht, ich bin an einer verlustfreien Bereichsvereinfachung interessiert .
Benutzer1538028

Antworten:

6

Sie können nach der Vereinfachung einfach mit dem ursprünglichen Polygon verbinden.

Flitmonkey
quelle
1
Obwohl dies funktioniert, könnte es schlimmer sein als das ursprüngliche Polygon!
whuber
Kann es schlimmer sein? Ich kann mir kein schlimmeres Beispiel vorstellen - ich denke, es könnte eines geben. Im Allgemeinen wird es jedoch eine Vereinfachung sein, die durch die konvexe Hülle begrenzt wird.
Flitmonkey
1
Dies hängt vom Algorithmus ab, der vom "Topologie-Vereinfacher" verwendet wird. Einige Vereinfacher behalten möglicherweise keinen der Scheitelpunkte entlang eines Bogens bei, sodass die Vereinigung der vereinfachten Version mit dem Original notwendigerweise mehr Scheitelpunkte als das Original aufweist. Um zu wissen, ob Ihre Empfehlung nützlich ist oder das Gegenteil, müsste man die Details der Vereinfachung verstehen.
whuber
4
Dies mag eine gute Antwort auf die "genaue" Frage sein, aber ich bin nicht sicher, ob die richtige Frage gestellt wird oder aus den richtigen Gründen.
Martin F
1

Wenn der TopologyPreservingSimplifer auf dem Douglas-Peucker-Algorithmus basiert, wie bei vividsolutions (Ersteller von JTS) angegeben, werden Polygonbereiche im Allgemeinen nicht geändert. Jedes Polygon muss jedoch resultierende Sequenzen winziger Gewinne und Verluste aufweisen (Ausgleich insgesamt).

Wenn Sie sich auf ein einzelnes Polygon oder eine kleine Gruppe von Polygonen konzentrieren und zulassen, dass diese sich ausdehnen, aber nicht verkleinern (auf Kosten ihrer Nachbarn), führen Sie Verzerrungen in Ihre Analyse ein.

Nachtrag

Daher glaube ich, dass Ihre ursprüngliche Wahl, der TopologyPreservingSimplifer, die richtige Lösung ist.

Martin F.
quelle
Dies sind gute Kommentare - aber sie lesen sich wie Kommentare anstelle einer Antwort auf die Frage. Wenn Sie vielleicht (etwas umsichtig) versuchen, Douglas-Peucker als Lösung vorzuschlagen, sollten Sie diese Empfehlung etwas klarer formulieren.
whuber
1
@whuber, ich habe definitiv nicht versucht, umsichtig zu sein und eine Schlussfolgerung gemäß Ihrem Rat hinzugefügt - auch nach dem Update von OP, das meinem Verständnis des Problems oder der Argumentation nichts hinzufügt.
Martin F