2D Level of Detail (LOD) algorithm

Question

I have been scouting around the net for an algorithm that enables you to create level of detail (LOD) representations of 2D polygons, but am unable to find ANY decent reference. Maybe I am using the wrong search terms, but all search results are for 3D LOD algorithms, which, I guess, cannot(?) really be applied in 2D.

I am sure that before the onslaught of 3D graphics, many people would have worked on 2D LOD algorithms. Any clues or pointers to where I can get more information? Thanks!

Answer 1

Aside from the obvious dumbest algorithm which would be to take every Nth vertex from the polygon (reducing the number of vertices by N), here is an idea inspired by some 3D algorithms.

Usually, in 3D, what is required is to remove the faces that contribute less to the overall volume. To do this, we try to simplify the "flattest" areas of the model.

Now in 2D, you could translate this to "simplify the segments that have the smallest angle between them. A first naïve implementation could be:

1. Compute all angles between the segments Si and Si+1 of the polygon
2. Take all the angles below a given threshold (or take the M smallest angles)
3. Simplify the segments we identified in 2. (replace [Pi, Pi+1] and [Pi+1, Pi+2] by [Pi, Pi+2])
4. Repeat from 1. until we have sufficiently reduced our polygon

Of course, this is not optimal but it should be a good trade of between quality and speed. Instead of the angle, you could take the minimal distance between the middle point of two segments (Pi+1) and the potentially simplified segment ([Pi, Pi+2])

Edit:

Another algorithm I would try if I did not need too much performance:

1. Consider the original polygon vertices as the control points of a Catmull-Rom spline
2. Tesselate this spline at the desired number of points

Finally, I found some source code for you on that link: http://motiondraw.com/md/as_samples/t/LineGeneralization/demo.html, as well as the associated algorithms: http://www.geom.unimelb.edu.au/gisweb/LGmodule/LGSimplification.htm

Answer 2

Search for Douglas-Peucker algorithm which is used to simplify polylines, but may be extended to support polygons. It is what I have used. There are also topologically stable extensions if you need that.