Finding good starting points for Douglas-Peucker algorithm for closed polygons

Question

I am trying to reduce a polygon's vertexes using Douglas-Peucker algorithm - which works quite fine for lines and paths.

My problem is that the polygons I want to optimize are closed. When choosing 2 random adjacent points the optimization works well - except for the start and end point - since they are fixed and can't be optimized.

Is there a good way to choose a starting point?

Answer 1

I would just choose one point randomly (e.g.: The "first" point in the list of all points) and find the furthest point. That is similar to the ordinary steps of the algorithm when searching for the furthest point from a line segment.

Answer 2

I might be completely misinterpreting the problem here, but it sounds like you just want to adapt the Douglas-Peucker algorithm (http://en.wikipedia.org/wiki/Ramer–Douglas–Peucker_algorithm) to polygons. And the only reason you can't just treat your polygon as a line with the start point and end point the same is because the algorithm requires you to have those two points be distinct.

So I'd recommend picking two arbitrary points on your polygon that are far apart, and then running the Douglas-Peucker algorithm twice, once for the path between your points that goes clockwise, and once for the path between your points that goes counterclockwise.

Your arbitrary points are guaranteed to be in the final solution, but otherwise its as close as you can get to the line approximation of the algorithm.

If this doesn't suffice, you should search for LOD, or Level Of Detail, since thats what this problem is generally called in computer graphics, though you'll probably hit a bunch of pages about solving the problem for polyhedrons with rather complex tree structures, which may or may not be what you're looking for.