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.
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;
}
}}
Réponses:
Vous pouvez simplement l'union avec le polygone d'origine après la simplification.
la source
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.
la source
Mon module plugin / python qgis vous permet de simplifier les géométries par "contrat" (rétrécissement uniquement) ou expansion uniquement:
https://github.com/albertferras/simplipy https://plugins.qgis.org/plugins/simplipy/
la source