Consistent feature thinning between tiles

[e-n-f]

To address the highly visible tile boundaries between automatically thinned out tiles, I think the answer is probably that if a feature is dropped from one tile, it must be dropped from every tile, so that the density transitions happen at the edges of features, not of tiles. The plan:

• Add a feature sequence number to the serialization format (also for Add a flag to inhibit sorting #37) so that features can be related between tiles
• For each zoom level, preflight the tile sizes. For each tile that is too big, instead of just skipping a fraction of features, explicitly choose which ones will be dropped, and add them to a list.
• Then do a second pass over that zoom level, actually writing the tiles, and dropping all the features that need to be dropped, for whatever tile they appear in

The downside: this will only help for features that actually correspond to a reasonably long trip. If each feature is just a single segment, it's hardly better than dropping at the tile boundaries, and will just have a fringed transition instead of a sharp edge.

The preflighting also unfortunately makes parallelization more complicated, since the list of features to be dropped has to be consistent between threads.

cc @lxbarth @tmcw

[e-n-f]

Probably more manageable if I still do fractional dropping and only track the features that cross tile boundaries explicitly?

[e-n-f]

What it looks like at z10 applied to tl_2010_06037_roads (with all metadata preserved) from TIGER. Still very visible differences between tiles. I hope this is just because roads in TIGER are so much shorter and more distinct than tracks from GPS.

[e-n-f]

Most worrisome part is the sparse regions at the edges, where roads are apparently getting thinned from both sides. Maybe when thinning a tile it needs to consider all tracks in that tile, not just ones that haven't already been eliminated by a neighbor.

[e-n-f]

Hmm, no, not just a TIGER problem: there are very visible bands at the edges of many GPS tiles. Debugging now.

[e-n-f]

Fixed the major bug and now it is fairly smooth. The gradients from a dense tile into a sparse one are still more visible than I want at moderate zooms (8 to 11 or so) but the abrupt seams are gone at high zooms.

[e-n-f]

Example of the low-zooms problem: the Skobbler corpus at z5. Germany is so dense that England falls off to nothing at the Prime Meridian.

I think the answer is probably to choose features to keep within each tile so that the features are distributed as evenly as possible by spatial index rather than by index-sorted sequence number.

[e-n-f]

At least within a 200K track (~10%) sample of the Skobbler tracks, that seems to be working out pretty well.

After discussion with @virginiayung I'm using the spatial-index distance between feature bounding box centers to measure frequency within each tile, sorting the frequencies, and cutting off a percentile of frequencies at the top end proportional to the fraction of features that need to be dropped.

There's still enough going on in low-frequency rural Germany that the high-frequency tracks in the east half of London completely vanish, but that's probably better than having a dense spot with a big empty area around it. Maybe giving short tracks a boost over long ones would keep a little more of it around.

Trying again now with a larger sample. Some of these drop rates are pretty crazy: with the full 2013 Skobbler tracks, tile 4/8/5, which covers most of Europe, only retains 0.26% of its original features.

[e-n-f]

Hmm, this is still not really solved. In the complete 2013 Skobbler tracks at z4, you can still see a dramatic drop in density in eastern England and southern Denmark because the data in 4/8/5 is thinned so much more than its neighbors.

Maybe the rule needs to be that no tile can retain more than, say, a 50% greater fraction than its immediate neighbors retain.

[e-n-f]

Dropping a uniform fraction across the whole world would make for many very sparse tiles in sparse areas, but maybe it would work to have the frequency cutoff be uniform?

[e-n-f]

A single worldwide frequency cutoff works well for low zoom levels, even though it means that the map is highly biased toward routes that carry long trips.

It loses a lot of detail in most tiles at high zooms, though. There must be some good way to get local near-uniformity without requiring global uniformity.

[lxbarth]

It loses a lot of detail in most tiles at high zooms, though. There must be some good way to get local near-uniformity without requiring global uniformity.

Changing the aggressiveness of the algorithm by zoom level?

[e-n-f]

Maybe that is the thing to do. Cutting out a midrange band of frequencies, as I tried today, instead of only cutting high frequencies doesn't seem to help. Even if being nonuniform at the high zooms only works because the tracks tend to be longer than a tile is wide, it still works, so I'll try easing into it.

[e-n-f]

This works now with --drop-densest-as-needed and --drop-fraction-as-needed.