¿Simplificación de polígonos sin pérdidas?

Question

¿Existe un algoritmo estándar/recomendado para simplificar un polígono sin reducir ninguno de sus límites originales?

Ahora mismo estoy usando TopologyPreservingSimplifer dentro del STC y me encuentro con problemas más adelante en mi aplicación cuando encuentro polígonos con "pérdidas". Idealmente, me gustaría producir polígonos simplificados que son más pequeños que el casco convexo, pero siguen siendo un superconjunto de mi polígono original.

Actualización:

Al final he dado con un algoritmo imperfecto que coloca una "envoltura" alrededor del polígono de entrada, lo encoge hasta que el exceso de áreas no supera un porcentaje del área total de la entrada, y luego ejecuta un simplificador de líneas con un umbral mucho más fino para eliminar cualquier punto redundante a lo largo de las líneas rectas. Depende al 100% de los datos, pero estoy viendo alrededor de un 80% de compresión de vértices con un mínimo de áreas de exceso. Todos los comentarios son bienvenidos:

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

}

Answer 1

Podría simplemente unirse con el polígono original después de la simplificación.

Answer 2

Si el TopologyPreservingSimplifer se basa en el algoritmo de Douglas-Peucker, como se dice en vividsolutions (creadores del STC), no generalmente cambiar las áreas de los polígonos. Cada polígono debe Sin embargo, tienen secuencias resultantes de pequeñas ganancias y pérdidas (que se equilibran en general).

Si se centra en un solo polígono, o en un pequeño grupo de polígonos, y les permite expandirse pero no reducirse (a expensas de sus vecinos), entonces está introduciendo un sesgo en su análisis.

adenda

Por lo tanto, creo que su opción original, el TopologyPreservingSimplifer, es la solución correcta.

Answer 3

Mi plugin de qgis/módulo de python permite simplificar las geometrías por "contracción" (sólo contracción) o sólo expansión:

https://github.com/albertferras/simplipy https://plugins.qgis.org/plugins/simplipy/