Today I coded up a little toy application. It limits the number of vertices displayed according to zoom level. Very simple. Its the pre-game to tiled vector datasets.
Winners: NetTopologySuite and SharpMap. They let me write this in under 80 lines of code.
Losers: Me! I skipped out on rock-climbing, a movie, and beer to write this.
August 24, 2007 at 5:33 am |
How does this line simplification (Douglas-Peucker??) handle the topological relationships between lines/polygons. In my experience, unless you want gaps between your adjacent polygons, lines intersecting at different points, etc. you need to do this within a topological data model (such as ArcInfo coverages or GRASS vectors). Does NetTopologySuite handle this?
August 24, 2007 at 5:44 am |
My experience is that in most cases its faster just to render all the vertices than to try and simplify them first (well unless you do this once, and reuse the results over and over). What is your experience on this?
Furthermore Matt raises and important issue. You want to ensure that the neighbouring polygons all get the same simplification, so you don’t risk getting holes or overlaps along their adjecent edges.
August 24, 2007 at 6:09 am |
This was generated with NTS’s “TopologyPreservingSimplifier.” It’s a Douglas-Peucker variant. See http://www.jump-project.org/docs/jts/1.6/api/com/vividsolutions/jts/simplify/TopologyPreservingSimplifier.html for slightly better info. It sounds like this simplifier works with multipolygon geometries. My test code would definitely have issues with adjacent polys from different features.
With my current dataset its a non-issue, but I definitely hear your point. I’d love for someone to point me at a point-culling simplifier that maintains topology across an entire dataset. I’ve found a paper or two on the idea, but I’m clueless when it comes to classic GIS implementations.
August 24, 2007 at 3:15 pm |
As for rendering all the vertices at once, keep in mind I’m trying to send this info over the internet. The dataset that the test feature (Death Valley) comes from is 21mB. My solution will hopefully address both download speed, and to a lesser extent, rendering speed.
The algorithms invovled in computing simplified geometries are definitely *slower* than standard map drawing. The “secret sauce” is doing this work up front, and allowing re-use via pre-computed tiles or zoom-levels.
August 25, 2007 at 11:13 pm |
Bill, Matt and Pete,
Some observations from my own experience.
A few things need to be separated.
1. Network efficiency;
2. Scale based rendering;
3. Data use
Let me tackle the first.
1. Network efficiency
I wrote a VB6 library for accessing Oracle Spatial (available on my website). The software this was written for (www.intragis.com.au) determined the language (VB6). The application runs on a separate server to the database. Because the data that is being rendered is quite dense (from a vertex perspective) – as so much data is nowadays – AND the data was being used a quite small scales, investigation was made on dynamic vertex simplification. Where the data was pulled across the network raw, simplified by the application and rendered, there was a small improvement in performance. I can’t recall the metrics (it was measured) but let’s say it was around 5% improvement. When we pushed the simplification back on to the database server (something I was not overly fond of doing) via “behind the scenes” change to the SQL to use Oracle’s MDSYS.SDO_UTIL.SIMPLIFY() function, performance improved substantially. Again, can’t remember the numbers but let’s say it was around 20-33%. The savings were in the shape of the network traffic (the library allows a user to set all aspects of the network packet in terms of features/buffer sizes etc) but mainly that the client was converting smaller shapes into the required format in memory, not having to coordinate thin the data, and speed improvements in rendering.
Finally, the VB6 client library was modified to throw away collapsed elements that were not of the original geometric type. Thus, if a multipart polygon became and Oracle collection we threw away linear and point elements as we found them only extracting polygons.
Summary: If, Bill, you are sending the data across the internet and can coordinate thin before delivering to the client to render then you should find the same savings.
2. Scale Dependent Rendering
The data that we rendered is quite dense as it is large scale (precise) polygon data. Speed issues hit when the data is viewed at increasing small scales. This was tackled through clever setting of the coordinate thinning tolerance and via another trick in not returning objects whose maximum MBR was less than the current pixel size (in meters).
My recollection of the way the application sets its vertext tolerance setting is based on the size of the actual pixel in real-world units (meters). As I understand it the polygons being rendered do not, visually, pull apart.
Wrt the MBR trick I must state that this should not be done if one is querying the data; it should only be done when rendering. This trick comes into its own as the render scale becomes small (say 1:100,000) when the data scale is large (eg 1:10,000). For example, cadastral polygons of house block scale would become sub-pixel when viewed at city scale. So why bother returning them and rendering them? Some tests I did at a client site (not the VB6 site) showed that this trick was returning up to 30% less polygons at the most extreme scale. Again, giving great disk, network and render savings across the whole render “pipeline”.
3. Data Use
Finally, if you can get away with not using a “TopologyPreservingSimplifier” by clever use of tolerance settings one should do this because I would expect such a “TopologyPreservingSimplifier” would be more computationally expensive. Also, since the use of the data is for rendering (a throw away “result set”) then why punish the “render pipeline” with such an overhead? Now, if the use of the data is for some other data integrity purposes or for use in a data overlay with larger scale data to compute some sort of statistic, then of course one would use a “TopologyPreservingSimplifier”.
I would be careful, Matt, in comparing what this article is doing with ArcInfo. Remember, ArcInfo polygon coverages do not contain independent polygons. A polygon is the thing that results when the polygon arc list (PAL) has been walked and the nodes/lines collected together to create the object. So, any ArcInfo simplification automatically works against shared linear segments which guarantees that polygons do not pull apart or cross.
A bit long and rambling, but I hope this helps.
regards
Simon Greener
August 26, 2007 at 1:32 am |
Simon, I definitely appreciate your feedback. I’m in agreement with just about everything you said, but I’ll keep running with the commentary.
1) Network efficiency: Vector simplication is only part of the reason that vector tileset can save bandwidth. Tilesets have a built-in spatial index, and can be cached by browsers. While raster tilesets only acheive increase performance when panning data, vectors tilesets should also increase performance while zooming.
2) Scale-dependent rendering: I am definitely going to coordinate pixel size with level-of-detail / simplication tolerance. In my example imagery I have over-exagerated the simplification to show the concept.
3) Data Use: I’m not entirely worried about the simplification algorithm. The purpose is to create the best simplication I can, given two conditions: it must only cull vertices (not add them, etc), and it must do so according to a real-world tolerance distance (according to #2). Speed is not an issue, as this data will be pre-computed at various zoom levels / simplification tolerances.
August 29, 2007 at 5:52 pm |
The post title doesn’t have a “vs.” in it, like you promised.
February 1, 2008 at 6:11 pm |
[...] Vector Delivery – Part 3 It looks like the boys at Microsoft Research implemented my idea: tiled vectors. Their demo makes on thing obvious, however. Douglas-Peucker just doesn’t cut it for [...]
February 1, 2008 at 10:37 pm |
[...] Thorp’s great idea becomes a Microsoft Research Project. Bill notes: Their demo makes one thing obvious, however. [...]
September 9, 2008 at 6:51 pm |
Some one have the code to simplify with sharpmap and NTS?
tanks