How to simplify (reduce number of points) in KML?
-
08-07-2019 - |
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:
What would be a good strategy for rendering these as markers instead of overlays once I'm beyond a certain zoom level?
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?
Solution
For your second question: you need the Douglas-Peucker Generalization Algorithm
OTHER TIPS
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.
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.
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 :)
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.
- Calculate the area of every possible triangle
T[1..n-1]
in the set. - Choose the triangle
T[i]
with the smallest area - Remove the point
P[i]
to essentially flatten the triangle - Recalculate the area of the affected triangles
T[n-1], T[n+1]
- Go To Step #2 if the number of points >
Max