How to simplify (reduce number of points) in KML?

Question

I have a similar problem to this post. I need to display up to 1000 polygons on an embedded Google map. The polygons are in a SQL database, and I can render each one as a single KML file on the fly using a custom HttpHandler (in ASP.NET), like this http://alpha.foresttransparency.org/concession.1.kml .

Even on my (very fast) development machine, it takes a while to load up even a couple dozen shapes. So two questions, really:

1. What would be a good strategy for rendering these as markers instead of overlays once I'm beyond a certain zoom level?

2. Is there a publicly available algorithm for simplifying a polygon (reducing the number of points) so that I'm not showing more points than make sense at a certain zoom level?

Answer 1

I don't know much aobut KML, but I think the usual solution to question #2 involves iterating over the points, and deleting any line segments under a certain size. This will cause some "unfortunate" effects in some cases, but it's relatively fast and easy to do.

Answer 2

I would recommend 2 things: - Calculate and combine polygons that are touching. This involves a LOT of processing and hard math, but I've done it so I know it's possible. - Create your own overlay instead of using KML in PNG format, while you combine them in the previous suggestion. You'll have to create a LOT of PNGs but it is blazing fast on the client.

Good luck :)

Answer 3

For your second question: you need the Douglas-Peucker Generalization Algorithm

Answer 4

For your first question, could you calculate the area of a particular polygon, and relate each zoom level to a particular minimum area, so as you zoom in or out polygon's disappear and markers appear depending on the zoom level.

For the second question, I'd use Mark Bessey's suggestion.

Answer 5

I needed a solution to your #2 question a little bit ago and after looking at a few of the available line-simplification algorithms, I created my own.

The process is simple and it seems to work well, though it can be a bit slow if you don't implement it correctly:

P[0..n] is your array of points Let T[n] be defined as the triangle formed by points P[n-1], P[n], P[n+1] Max is the number of points you are trying to reduce this line to.

1. Calculate the area of every possible triangle T[1..n-1] in the set.
2. Choose the triangle T[i] with the smallest area
3. Remove the point P[i] to essentially flatten the triangle
4. Recalculate the area of the affected triangles T[n-1], T[n+1]
5. Go To Step #2 if the number of points > Max