Bill Thorp’s great idea becomes a Microsoft Research Project. Bill notes:
Their demo makes one thing obvious, however. Douglas-Peucker just doesn’t cut it for topologies. This becomes a non-issue with a pixel-level of detail, but just looks bad in their demo. Their implementation doesn’t seem to preserve existing points between zooms; it’s probably just as efficient this way.
Read about it and then view the demo. When you think about the performance here of the polyline data set with 50,000 segments in it you really start to see why this is impressive. Vish has even more thoughts on the project.
3 Comments
This was the same issue I pointed out to the VE folks with their vector support – when they announced GeoRSS support, I was immediately past points and on to vectors, same with KML – and found that they appear to drop vertices indiscriminately. Perhaps an “drop every nth vertex” algorithm. But the problem noted was exactly as described, not always the same corners getting lopped off, and so on – with adjoining polygons, it results in strange and inconsistent gaps and overlaps.
It’s got nothing to do with topology, of course, because GeoRSS, KML and similar vector formats do not have any topology to know that they in fact have any relationship or common segments with the adjoining features. On the other hand, an approach that takes a consistent approach with respect to angular relationships, to preserve critical detail, is more likely to give more desirable results…
I certainly threw the Douglas Peucker notion at Microsoft several months back, when I saw the flaky vector results I was getting – so far they have only responded with the option to turn off generalization and a suggestion they might look at it sometime.
The demo works smoothly for me in FF, but crashes my IE6. Anyone else have the same result? For now, I’m happy enough to stick my mapserver generated raster overlays, but a system for handling large amounts of vector data would be great.
Unless you are really careful to treat the topologically identical segments as identical and process them the same.. you get the visual horror story in that demo… Being topological in many cases is something people will know – even though the data doesn’t have its topology stored with it we “know” those adjacent polys are supposed to be the same. D-P is well pretty damn slow on the fly which may be why they have “hem an hawed” about using it. My google maps extension GeoXml does use D-P either on the fly or with pre-encoded vector data but errs on the side of not simplifying far enough… relevant page is parsing gml and using D-P on the fly. http://www.dyasdesigns.com/geoxml/gmlusa.htm