10

So, the title is a little awkward. I'll give some background, and then ask my question.

Background: I work as a web GIS application developer, but in my spare time I've been playing with map rendering and improving data interchange formats. I work only in 2D space.

One interesting issue I've encountered is that when you're rendering a polygon at a small scale (zoomed way out), many of the vertices are redundant. An extreme case would be that you have a polygon with 500,000 vertices that only takes up a single pixel. If you're sending this data to the browser, it would make sense to omit ~499,999 of those vertices. One way we achieve that is by rendering an image on a server and and sending it as a PNG: voila, it's a point. Sometimes, though, we want data sent to the browser where it can be rendered with SVG (or canvas, or webgl) so that it can be interactive.

The problem: It turns out that, using modern geographic data sets, it's very easy to overload SVG's rendering abilities. In an effort to cope with those limitations, I'm trying to figure out how to visually losslessly reduce a data set for a given scale and map extent (and, if necessary, for a known map pixel width and height).

I got a great reduction in data size just using the Douglas-Peucker algorithm, and I believe I was able to get it to keep the polygons true to within one pixel. Unfortunately, Douglas-Peucker doesn't preserve topology, so it changed how borders between polygons got rendered. I couldn't readily find other algorithms to try out and adapt to the purpose, but I don't have much CS/algorithm background and might not recognize them if I saw them.

canisrufus
  • 1,091
  • 7
  • 17
  • 1
    Google for "Topologically Consistent Douglas-Peucker" and you will find some links to abstracts of some articles. Unfortunately, you have to pay for the full articles I saw. – Doc Brown Apr 04 '12 at 18:52
  • @DocBrown **Thank you!** [Questia](http://www.questia.com/googleScholar.qst?docId=5001892504) even seems to have a free trial. – canisrufus Apr 04 '12 at 19:31

1 Answers1

3

What you are looking for is 2d level of detail algorithms.

There is much documented about this on google if you search for those highlighted terms.

This question on stackoverflow has the information you are looking for on 2D Level of Detail rendering.

Community
  • 1
  • +1 for the very pertinent vocabulary. It looks like I'm actually using a level-of-detail approach, but need a polygon simplification algorithm that suits my needs. [Found a neat overview for 3d ones.](http://webdocs.cs.ualberta.ca/~anup/Courses/604_3DTV/Presentation_files/Polygon_Simplification/luebke01developers.pdf) I believe I've actually worked out a suitable simplification strategy, although I haven't had time to code it. – canisrufus Apr 05 '12 at 13:13