8

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.

simplified

Update:

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. All feedback/comments appreciated:

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

}

  • 5
    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? – Martin F Oct 29 '13 at 21:22
  • 1
    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. – user1538028 Oct 30 '13 at 20:52
6

You could simply union with the original polygon after simplification.

  • 1
    Although this works, it might be worse than the original polygon! – whuber Oct 26 '13 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. – flitmonkey Oct 27 '13 at 19:43
  • 1
    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. – whuber Oct 28 '13 at 13:56
  • 4
    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. – Martin F Oct 30 '13 at 22:03
1

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.

addendum

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

  • These are good comments--but they read like comments instead of an answer to the question. If you are perhaps trying (somewhat circumspectly) to propose Douglas-Peucker as the solution, please consider making that recommendation a little more clearly. – whuber Nov 8 '13 at 18:12
  • 1
    @whuber, i was definitely not trying to be circumspect and added a conclusion as per your advice -- even after OP's update which adds nothing to my understanding to the problem or reasoning. – Martin F Nov 9 '13 at 4:12
0

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.