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

8

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

En este momento estoy usando TopologyPreservingSimplifer dentro de JTS y me encuentro con problemas más adelante en mi aplicación cuando me encuentro con polígonos "con pérdida". Idealmente, me gustaría producir polígonos simplificados que sean más pequeños que el casco convexo pero que sigan siendo un superconjunto de mi polígono original.

simplificado

Actualizar:

Eventualmente se me ocurrió un algoritmo ciertamente imperfecto que coloca un "envoltorio" alrededor del polígono de entrada, lo encoge hasta que las áreas excedentes no excedan un porcentaje del área total de la entrada, luego ejecuta un simplificador de línea con un umbral mucho más fino para eliminar cualquier punto redundante a lo largo de líneas rectas. 100% dependiente de los datos, pero veo un 80% de compresión de vértices con un mínimo de áreas en exceso. Todos los comentarios / comentarios apreciados:

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

}

usuario1538028
fuente
55
1. ¿Por qué lo llamarías simplificación sin pérdidas ? Creo que si estás simplificando un límite, estás perdiendo detalles. 2. Podría simplificar los límites y tener áreas sin pérdidas , pero eso rompería su criterio de no reducir los límites. 3. ¿Por qué desea permitir que los límites se expandan y no se reduzcan? ¿O no entiendo algo?
Martin F
1
Mis datos representan límites políticos. Estoy de acuerdo con una pequeña extensión del área original si ayuda a reducir el conteo de vértices. Quiero evitar el sacrificio de personas del área original. Su correcta, estoy interesado en la simplificación del área sin pérdida .
user1538028

Respuestas:

6

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

flitmonkey
fuente
1
Aunque esto funciona, ¡podría ser peor que el polígono original!
whuber
Puede ser peor? No puedo pensar en un ejemplo que sea peor, supongo que podría haber uno. En general, será una simplificación limitada por el casco convexo.
flitmonkey
1
Depende del algoritmo utilizado por el "simplificador de topología". Es posible que algunos simplificadores no conserven ninguno de los vértices a lo largo de un arco, por lo que la unión de la versión simplificada con el original necesariamente tendrá más vértices que el original. Por lo tanto, para saber si su recomendación es útil o lo contrario, uno necesitaría comprender los detalles de la simplificación.
whuber
44
Esta puede ser una buena respuesta a la pregunta "exacta" que se hace, pero no estoy seguro de que se haga la pregunta correcta o por las razones correctas.
Martin F
1

Si TopologyPreservingSimplifer se basa en el algoritmo Douglas-Peucker, como se dice en vividsolutions (creadores de JTS), generalmente no cambiará las áreas de polígonos. Sin embargo, cada polígono debe tener secuencias resultantes de pequeñas ganancias y pérdidas (equilibrándose en general).

Si se está centrando 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 sesgo en su análisis.

apéndice

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

Martin F
fuente
Estos son buenos comentarios, pero se leen como comentarios en lugar de una respuesta a la pregunta. Si tal vez está intentando (algo circunspecto) proponer Douglas-Peucker como la solución, considere hacer esa recomendación un poco más clara.
whuber
1
@whuber, definitivamente no estaba tratando de ser circunspecto y agregué una conclusión según su consejo, incluso después de la actualización de OP que no agrega nada a mi comprensión del problema o razonamiento.
Martin F