4

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?

4 Answers 4

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.

2
  • The problem is: If I have a rectangular shape made up from several vertexes on the edges it might cut the edges - leaving a trapezoid shape instead of a rectangle. It might also lead to building the rectangle with 5 vertexes instead of one. Commented Jan 16, 2012 at 8:45
  • @Andreas Löw: That is the problem of Douglas-Peucker algorithm. It is not guaranted to be optimal. It is greedy and does not do any back-steps. You can try choosing all possible starting points and evaluate the result. But there are probably better algorithms if the shape is guaranteed to be rectangular. Commented Jan 16, 2012 at 8:49
1

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.

1

I did something similar in my javascript library where I found the two points that are farthest away from each other, and used those to optimize the polygon.

Here's the snippet I'm sure you can adapt to whatever language you're using:

function polygonPeuckerReduce(path, tolerance) {
    var points = [];
    if (path.length < 3) {
        return points.concat(path);
    } else {
        var widest = 0.0, startIndex = 0;
        // find the widest part of the polygon (only start index is necessary)
        for (var i = 0, l = path.length; i < l; i++) {
            var point = path[i];
            for (var j = i + 1; j < l; j++) {
                var distance = point.distanceTo(path[j]);
                if (distance > widest) {
                    startIndex = i;
                    widest = distance;
                }
            }
        }

        // re-order the points with the new starting point (faster method)
        points = path.splice(startIndex, path.length).concat(path);

        return PEUCKER_INTERNAL(points, tolerance); // the magic
    }
}
1

Another possibility is to scan through all sets of three sequential vertices and pick the two that are furthest from the lines joining their predecessor and successor vertices, i.e pick the two vertices belonging to the two largest corners in the original data set. Fix those two vertices, then apply Douglas-Peucker to the intervening vertices.

This can be noisy if all your points are closely spaced. In that case rather than simply consider successive sets of three vertices, you can work outward in both directions from each input vertex, using Douglas-Peucker to skip over unnecessary vertices in each direction. This will result in larger, more-widely-spaced triples. Again find the two vertices that are furthest from the lines joining the predecessor/successor vertices, fix those, and apply Douglas-Peucker to the intervening vertices.

Other variations are possible but this should give a better starting point than either "random" or "furthest apart" as described in other answers.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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