# Seeking algorithm for Lossless Polygon Simplification

Is there a standard/recommended algorithm for simplifying a polygon without shrinking any of its original boundaries?

Right now I'm using TopologyPreservingSimplifer within JTS and running into problems later on in my application when I encounter "lossy" polygons. Ideally, I'd like to be producing simplified polygons that are smaller than the convex hull but remain a superset of my original polygon. I eventually came up with an admittedly imperfect algorithm that places a "wrapper" around the input polygon, shrinks it until no excess areas exceed a percentage of the total area of the input, then runs a line simplifier with a much finer threshold to strip out any redundant points along straight lines. 100% data dependent, but I'm seeing about 80% vertex compression with minimal excess areas.

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

}

• 1. Why would you call it lossless simplification? I think if you're simplifying a boundary, you're losing detail. 2. You could simplify boundaries and have lossless areas, but that would break your criterion of not shrinking boundaries. 3. Why do you wish to allow boundaries to expand and not shrink? Or do i misunderstand something? Oct 29, 2013 at 21:22
• My data represents political boundaries. I'm OK with a small extension of the original area if it helps to bring down the vertex count. I want to avoid culling people from the original area. Your correct, I'm interested in lossless area simplification. Oct 30, 2013 at 20:52
• For anyone looking for something in the future -- I wrote a small modification of RDP in python to solve this issue here: github.com/prakol16/rdp-expansion-only Sep 14, 2020 at 3:37

You could simply union with the original polygon after simplification.

• Although this works, it might be worse than the original polygon! Oct 26, 2013 at 15:50
• Can it be worse? I can't think of an example that is worse - guess that there might be one though. In general though it will be a simplification that is bounded by the convex hull. Oct 27, 2013 at 19:43
• It depends on the algorithm used by the "topology simplifier." Some simplifiers might not preserve any of the vertices along an arc, so the union of the simplified version with the original will necessarily have more vertices than the original. Thus, in order to know whether your recommendation is useful or the opposite, one would need to understand the details of the simplification. Oct 28, 2013 at 13:56
• This may be a good answer to the "exact" question being asked, but i'm not sure the right question is being asked or for the right reasons. Oct 30, 2013 at 22:03

If the TopologyPreservingSimplifer is based upon the Douglas-Peucker algorithm, as it says at vividsolutions (creators of JTS), it will not generally change polygon areas. Each polygon must, however, have resulting sequences of tiny gains and losses (balancing out overall).

If you are focusing on a single polygon, or a small group of polygons, and you allow them to expand but not not shrink (at the expense of their neighbors) then you are introducing bias into your analysis.

Thus, i believe your original choice, the TopologyPreservingSimplifer, is the correct solution.

My qgis plugin/python module allows you to simplify geometries by "contract" (shrink only) or expansion only: