Simplified (or smooth) polygons that contain the original detailed polygon

Question

I have a detailed 2D polygon (representing a geographic area) that is defined by a very large set of vertices. I'm looking for an algorithm that will simplify and smooth the polygon, (reducing the number of vertices) with the constraint that the area of the resulting polygon must contain all the vertices of the detailed polygon.

For context, here's an example of the edge of one complex polygon:

My research:

• I found the Ramer–Douglas–Peucker algorithm which will reduce the number of vertices - but the resulting polygon will not contain all of the original polygon's vertices. See this article Ramer-Douglas-Peucker on Wikipedia

• I considered expanding the polygon (I believe this is also known as outward polygon offsetting). I found these questions: Expanding a polygon (convex only) and Inflating a polygon. But I don't think this will substantially reduce the detail of my polygon.

Thanks for any advice you can give me!

Discordancy

I'm confused by this sentence - "I'm looking for an algorithm that will simplify and smooth the polygon, (reducing the number of vertices) with the constraint that the resulting polygon must contain all the vertices of the detailed polygon.". How do you reduce the number of vertices, yet retain them all? – Rogerrogerio

I mean the resulting polygon should have fewer vertices, but the area it defines must contain all vertices that were in the detailed polygon. Thanks. – Discordancy

Is performance an issue here? – Lechner

Performance is one issue; I will plot these polygons on a map along with other data. Fewer vertices will make the map more responsive. The other issue is aesthetics, where a smoother polygon (or city perimeter in this case) will look cleaner. – Discordancy

Should the final vertex set be part of the original set, or can you fake up a set of "new" and different vertices? – Lechner

If the new polygon had entirely different vertices to the detailed polygon, that would be okay, provided the edges of the new polygon aren't too far from the original edges. e.g. I don't want a convex hull, or a giant circle containing the original polygon. – Discordancy

@Discordancy Ha! that "freedom" makes the problem much more difficult! :D – Lechner

@belisarius - totally agree. This one has me stumped. – Discordancy

What platform/software would you prefer to work with? – Dagnydago

@radek - Ha, open source javascript or python would be perfect! ;o) But realistically, I just need to understand the algorithm so we can code it. – Discordancy

If you need to do it once then illustrator is a good option. – Psilomelane

Answer 1

Edit

As of 2013, most links below are not functional anymore. However, I've found the cited paper, algorithm included, still available at this (very slow) server.

---

Here you can find a project dealing exactly with your issues. Although it works primarily with an area "filled" by points, you can set it to work with a "perimeter" type definition as yours.

It uses a k-nearest neighbors approach for calculating the region.

Samples:

Here you can request a copy of the paper.

Seemingly they planned to offer an online service for requesting calculations, but I didn't test it, and probably it isn't running.

HTH!

Lechner

Thanks. This looks very promising. I'd like to implement this myself, so will have to see if I can get that paper. Plan to work on this Saturday - will keep you posted – Discordancy

@Discordancy If you have an ACM user, I think you can get the paper there. Also I'm sure you should be able to find related papers elsewhere on the net if the authors don't answer your request. Good luck! – Lechner

Answer 2

I think Visvalingam’s algorithm can be adapted for this purpose - by skipping removal of triangles that would reduce the area.

Valse

Answer 3

I had a very similar problem : I needed an inflating simplification of polygons.

I did a simple algorithm, by removing concav point (this will increase the polygon size) or removing convex edge (between 2 convex points) and prolongating adjacent edges. In any case, doing one of those 2 possibilities will remove one point on the polygon.

I choosed to removed the point or the edge that leads to smallest area variation. You can repeat this process, until the simplification is ok for you (for example no more than 200 points).

The 2 main difficulties were to obtain fast algorithm (by avoiding to compute vertex/edge removal variation twice and maintaining possibilities sorted) and to avoid inserting self-intersection in the process (not very easy to do and to explain but possible with limited computational complexity).

In fact, after looking more closely it is a similar idea than the one of Visvalingam with adaptation for edge removal.

Cardinal

Answer 4

That's an interesting problem! I never tried anything like this, but here's an idea off the top of my head... apologies if it makes no sense or wouldn't work :)

1. Calculate a convex hull, that might be way too big / imprecise
2. Divide the hull into N slices, for example joining each one of the hull's vertices to the center
3. Calculate the intersection of your object with each slice
4. Repeat recursively for each intersection (calculating the intersection's hull, etc)

Each level of recursion should give a better approximation.... when you reached a satisfying level, merge all the hulls from that level to get the final polygon.

Does that sound like it could do the job?

Understrapper

Thanks! I don't think I understand points (3) or (4) correctly. But even so, if I have a convex hull, and take some intersection (with the original polygon) to make it concave.. when you make it convex again in step (4) - don't you end up with the same convex hull you started with? – Discordancy

Here's what I had in mind: docs.google.com/drawings/…. It seems that after 1 level we get more detail with the result becoming concave, but I'm not sure what happens if we repeat step 3 and 4 by slicing up each little hull. – Understrapper

This would also probably work best if you have a small staggered lines (smoothed out by creating hulls) and major extrusions (refined by slicing the hulls). I'm not sure about the results on the screenshot you added. – Understrapper

Perhaps concave hull would be better option than convex? gis.stackexchange.com/questions/1200/… – Dagnydago

@radek - Yes, that concave hull looks promising. Will be working on this Saturday - will let you know what works. – Discordancy

@Discordancy - Did you ever figure out an answer? I have a related question @ gis.stackexchange.com/questions/31354/… – Biotic

Answer 5

I've written a simple modification of Douglas-Peucker that might be helpful to anyone having this problem in the future: https://github.com/prakol16/rdp-expansion-only

It's identical to DP except that it pushes a line segment outwards a bit if the points that it would remove are outside the polygon. This guarantees that the resulting simplified polygon contains all the original polygon, but it has almost the same number of line segments as the original DP algorithm and is usually reasonably good at approximating the original shape.

Mezzorilievo

Answer 6

To some degree I'm not sure what you are trying to do but it seems you have two very good answers. One is Ramer–Douglas–Peucker (DP) and the other is computing the alpha shape (also called a Concave Hull, non-convex hull, etc.). I found a more recent paper describing alpha shapes and linked it below.

I personally think DP with polygon expansion is the way to go. I'm not sure why you think it won't substantially reduce the number of vertices. With DP you supply a factor and you can make it anything you want to the point where you end up with a triangle no matter what your input. Picking this factor can be hard but in your case I think it's the best method. You should be able to determine the factor based on the size of the largest bit of detail you want to go away. You can do this with direct testing or by calculating it from your source data.

http://www.it.uu.se/edu/course/homepage/projektTDB/ht13/project10/Project-10-report.pdf

Nunuance