5

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!

Josh Lee
  • 171,072
  • 38
  • 269
  • 275
tathagata
  • 478
  • 3
  • 12
  • 1
    Interesting, perhaps looking for shape-simplification, image abstraction or even compression? What are the requirements for the LOD? As in will the image be shrunk? Is it for performance, for saving memory or emulating depth? – Julian Young Dec 16 '10 at 12:52
  • I am looking at improving the performance of an existing (legacy) algorithm. Essentially, I want a reasonable 'shrink-wrap' approximation of the polygon, where the major outer features are preserved, and internal details hidden away. +1 for the suggested keywords. Thanks! – tathagata Dec 17 '10 at 10:39

2 Answers2

4

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

Vincent Mimoun-Prat
  • 28,208
  • 16
  • 81
  • 124
  • Thanks for the suggestions. I think that I will be able to use a combination of the algorithms you suggested and the one suggested Juraj above to achieve something akin to what I want. +1. Unfortunately, I cannot mark both the answers as correct, so marking this one as correct, but the 'Douglas-Peucker algorithm' suggested by Juraj is equally good. – tathagata Dec 17 '10 at 10:47
  • Yep, I did not know about Ram Douglas Peucker algorithm, but I like it. Good thing with it is you can easily stop when you have reached your maximum number of points for instance. – Vincent Mimoun-Prat Dec 17 '10 at 11:39
4

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.

genpfault
  • 51,148
  • 11
  • 85
  • 139
Juraj Blaho
  • 13,301
  • 7
  • 50
  • 96
  • +1 for letting me know that about this cool algorithm. This might work but I have got to check it out in my context. And this is one thing I missed mentioning in the question, but I don't know how exactly to explain this in words, but see my comment to the main question above. – tathagata Dec 17 '10 at 10:34