Simplification du polygone sans perte?

8

Existe-t-il un algorithme standard / recommandé pour simplifier un polygone sans rétrécir aucune de ses limites d'origine?

En ce moment, j'utilise TopologyPreservingSimplifer dans JTS et je rencontre des problèmes plus tard dans mon application lorsque je rencontre des polygones "avec perte". Idéalement, j'aimerais produire des polygones simplifiés qui sont plus petits que la coque convexe mais qui restent un surensemble de mon polygone d'origine.

simplifié

Mise à jour:

J'ai finalement trouvé un algorithme certes imparfait qui place un "wrapper" autour du polygone d'entrée, le rétrécit jusqu'à ce qu'aucune zone excédentaire ne dépasse un pourcentage de la surface totale de l'entrée, puis exécute un simplificateur de ligne avec un seuil beaucoup plus fin pour éliminer tout point redondant en ligne droite. 100% dépendant des données, mais je vois environ 80% de compression des sommets avec un minimum de zones en excès. Tous les commentaires / commentaires appréciés:

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
la source
5
1. Pourquoi appeleriez-vous cela une simplification sans perte ? Je pense que si vous simplifiez une frontière, vous perdez des détails. 2. Vous pourriez simplifier les limites et avoir des zones sans perte , mais cela briserait votre critère de ne pas réduire les limites. 3. Pourquoi souhaitez-vous permettre aux frontières de s'étendre et non de rétrécir? Ou est-ce que je comprends mal quelque chose?
Martin F
1
Mes données représentent des frontières politiques. Je suis d'accord avec une petite extension de la zone d'origine si cela aide à réduire le nombre de sommets. Je veux éviter d'abattre les gens de la zone d'origine. Vous avez raison, je suis intéressé par la simplification de la zone sans perte .
user1538028

Réponses:

6

Vous pouvez simplement l'union avec le polygone d'origine après la simplification.

flitmonkey
la source
1
Bien que cela fonctionne, il pourrait être pire que le polygone d'origine!
whuber
Cela peut-il être pire? Je ne peux pas penser à un exemple qui est pire - devinez qu'il pourrait y en avoir un cependant. En général, ce sera une simplification limitée par la coque convexe.
flitmonkey
1
Cela dépend de l'algorithme utilisé par le "simplificateur de topologie". Certains simplificateurs peuvent ne conserver aucun des sommets le long d'un arc, donc l'union de la version simplifiée avec l'original aura nécessairement plus de sommets que l'original. Ainsi, afin de savoir si votre recommandation est utile ou contraire, il faudrait comprendre les détails de la simplification.
whuber
4
Cela peut être une bonne réponse à la question "exacte" posée, mais je ne suis pas sûr que la bonne question soit posée ou pour les bonnes raisons.
Martin F
1

Si le TopologyPreservingSimplifer est basé sur l'algorithme Douglas-Peucker, comme il est dit chez vividsolutions (créateurs de JTS), il ne changera généralement pas les zones de polygones. Cependant, chaque polygone doit avoir des séquences résultantes de gains et de pertes minimes (équilibrage global).

Si vous vous concentrez sur un seul polygone ou sur un petit groupe de polygones et que vous leur permettez de s'étendre mais pas de rétrécir (au détriment de leurs voisins), vous introduisez un biais dans votre analyse.

Addenda

Ainsi, je crois que votre choix d'origine, le TopologyPreservingSimplifer, est la bonne solution.

Martin F
la source
Ce sont de bons commentaires - mais ils se lisent comme des commentaires au lieu d'une réponse à la question. Si vous essayez peut-être (un peu avec circonspection) de proposer Douglas-Peucker comme solution, veuillez envisager de faire cette recommandation un peu plus clairement.
whuber
1
@whuber, je n'essayais certainement pas d'être circonspect et j'ai ajouté une conclusion selon vos conseils - même après la mise à jour d'OP qui n'ajoute rien à ma compréhension du problème ou du raisonnement.
Martin F