views:

1795

answers:

5

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?

A: 

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.

Mark Bessey
A: 

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 :)

Eric Wendelin
Thanks - I really don't have the resources to duplicate so much of what the Google API provides for free.
Herb Caudill
+7  A: 

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

PiedPiper
Thanks, this is what I needed. I've adapted a C# implementation of D-P I found on CodeProject - seems to work pretty well.
Herb Caudill
+2  A: 

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.

Bravax
A: 

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
Daniel Beardsley
Out of curiosity, why not go with Douglas-Peucker? At first glance your algorithm seems considerably less efficient. It also aims for a fixed number of points, rather than a given tolerance - so how would you apply it to a large number of shapes of differing complexity?
Herb Caudill
You know... I might try implementing that soon. This part of my app gets run pretty infrequently, but looking at it again, it does look like a better method. Thanks.
Daniel Beardsley