2

I've been using Mapshaper to simplify some very complex polygons (boundaries of countries). The goal is to create relatively simple polygons which can be used to determine whether a given lat/lon point is inside a given country. It's OK if I (somewhat rarely) wind up with a false positive, but it's not OK to ever wind up with a false negative.

Using the standard Mapshaper simplification tools, I wind up with a polygon that isn't always covering 100% of the territory covered by the original polygon. That's a problem. Is there any tool/technique that exists to create a simplified polygon that will fully enclose all the territory the original polygon covered?

Update:

To clarify: While I'll be processing one country at a time, I will be querying against a collection of countries to find which of them contains a given point. My intention is that the processed polygons will sometimes overlap, such that points right by the border between two countries will often fall in both of those countries according to the polygons. This is OK, and expected.

Improve this question
3
  • 1
    I don't think you're going to be able to do this. If you simplify China's boundary to make you have no false negative, you'll end up with false negatives in the surrounding countries.
    – mkennedy
    Nov 10, 2016 at 19:27
  • @mkennedy see the update for clarification.
    – DanM
    Nov 10, 2016 at 19:59
  • If you can change your accepted answer it should be rafd's. Much cleaner, more native and likely to give better results in the long run if others want to repeat the process.
    – Phil G
    Nov 21, 2017 at 9:25

3 Answers 3

Reset to default
4

To avoid the issue of "the convex hull of China contains almost all of Mongolia", you could make use of a concave hull.

For example, here's the difference between ST_ConcaveHull and ST_ConvexHull in PostGIS (taken from here):

Visual comparison of ST_ConcaveHull ST_ConvexHull

In PostGIS, ST_ConcaveHull takes a target_percent parameter, which effectively adjusts how far into the cavities it will go (a lower value will result in a smaller overall area, but takes more time). The resource at 1 suggests using 0.99 as a starting point for most situations.

Improve this answer
2
  • This should be the accepted answer - a "cannot see the forest for the trees" situation for not even looking at the concave hull in my case.
    – Phil G
    Nov 21, 2017 at 9:24
  • Be aware that ST_ConcaveHull operates only on the vertices of the input, and so is not guaranteed to fully enclose an input polygon.
    – dr_jts
    Apr 14 at 18:30
1

Any GIS tool that is able to create a "Convex Hull" should do the trick, albeit this will possibly generalise the input too much (as confirmed by the OP). A convex hull aims to find the smallest convex envelope containing all points of the original input shape (see wikipedia).

UPDATE (to reflect the clarification):

Another way of approaching this would be to create a buffer of the polygon and generalising (simplifying) the buffered output.

enter image description here

In the image the grey area is our initial input polygon. The green line represents a simplified version of this area, leaving parts of the original input uncovered.

The black area represents a buffer which extends the polygon on all sides by a certain distance. Simplifying this buffered polygon results in the red line and thus in a simplified polygon that wholly covers the original input.

Most GIS software (including the free QGIS) will allow you to do this readily. The complexity of the input polygon and the level of generalisation will dictate how large the buffer needs to be.

Improve this answer
6
  • 1
    Unfortunately a convex hull is definitely not going to work -- for example, the convex hull of China contains almost all of Mongolia. I'm not completely sure I understand the second suggestion -- by "generalizing" are you just referring to reducing the number of points? Because in that case we wind up in many cases not covering all the area that the original polygon covered. Or is there something more to the suggestion that I'm missing?
    – DanM
    Nov 10, 2016 at 19:09
  • By adding a buffer to the input polygon first (i.e. extending it outwards), the resulting generalisation is less likely to encroach on the original polygon. I'll extend my answer to cover more detail on that if I find some time later this evening. Could you please edit your original question to cover whether multiple neighbouring countries would be used at the same time? If so, this changes the possible solutions drastically. From your wording it appears only one country at a time would be used and the country is known.
    – Phil G
    Nov 10, 2016 at 19:27
  • @DanM Edited and clarified to reflect your updates
    – Phil G
    Nov 10, 2016 at 20:17
  • I like this idea. It doesn't guarantee that I won't lose any territory in the simplified polygon, but hopefully in practice it'll work well.
    – DanM
    Nov 10, 2016 at 20:21
  • It will take a fair bit of experimentation to get the right values and theoretically you could script an approach that repeats the steps: Create buffer around polygon -> Simplify-> Check whether input within output -> If not: repeat and increment buffer This would allow you to find the "optimum" settings.
    – Phil G
    Nov 10, 2016 at 21:15
1

It is now possible to do this with the JTS Topology Suite using the new PolygonHull class.

Outer Hull

Improve this answer

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.