Minimize Polygon Vertices

Question

What is a good algorithm for reducing the number of vertices in a polygon without changing the way it looks very much?

Input: A polygon, represented as a list of points, with way too many verticies: raw input from the mouse, for example.

Output: A polygon with much fewer verticies that still looks a lot like the original: something usable for collision detection, for example (not necessarily convex).

Edit: The solution to this would be similar to finding a multi-segmented line of best fit on a graph. It's called Segmented Least Squares in my algorithms book.

Edit2: The Douglas Peucker Algorithm is what I really want.

Answer 1

Edit: Oh look, Simplifying Polygons

You mentioned collision detection. You could go really simple and calculate a bounding convex hull around it.

If you cared about the concave areas, you can calculate a concave hull by taking the centroid of your polygon, and choosing a point to start. From the starting point rotate around the centroid, finding each vertex you want to keep, and assigning that as the next vertex in the bounding hull. The complexity of the algorithm would come in how you determined which vertices to keep, but I'm sure you thought of that already. You can throw all your vertices into buckets based on their location relative to the centroid. When a bucket gets more than an arbitrary number of vertices full, you can split it. Then take the mean of the vertices in that bucket as the vertex to use in your bounding hull. Or, forget the buckets, and when you're moving around the centroid, only choose a point if its more than a given distance from the last point.

Actually, you could probably just use all the vertices in your polygon as "cloud of points" and calculate the concave hull around that. I'll look for an algorithm link. Worst case on this would be a completely convex polygon.

Another alternative is to start with a bounding rectangle. For each vertex on the rectangle, find the distance from the point to the polygon. For the farthest vertex, split it into two more vertices and move them in some. Repeat until some proportion of either vertices or area is met. I'd have to think about the details of this one a little more.

If you care about the polygon actually looking similar, even in the case of a self-intersecting polygon, then another approach would be required, but it doesn't sound like thats necessary since you asked about collision detection.

This post has some details about the convex hull part.