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!

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!

Answer 2

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