felt / tippecanoe

Build vector tilesets from large collections of GeoJSON features.
BSD 2-Clause "Simplified" License
987 stars 84 forks source link

Add `--generate-variable-depth-tile-pyramid` option #251

Closed e-n-f closed 3 months ago

e-n-f commented 3 months ago

--generate-variable-depth-tile-pyramid

When this option is specified, Tippecanoe will attempt to generate high-resolution, unsimplified tiles that are suitable for overzooming to all higher zoom levels, and, if successful, will not generate any child tiles for those tiles. The attempt is made only if the size of the serialized data for the tile suggests that it is likely to succeed.

The zoom pyramid will not be truncated below any tiles that drop or coalesce or cluster features, or that have point features that are still being excluded below their basezoom.

This is a generalization of the "fillzoom" concept that has long been used elsewhere to avoid generating high-zoom tiles in the middle of the oceans, but stopping tiling at any point where a tile is complete enough rather than only when tiles are entirely covered by a polygon at a certain specific zoom level.

Such tilesets will look strange if you try to view them directly, since many tiles will be missing at high zoom levels, and many lower-zoom tiles will have excessively complex geometries. Instead, the tile server must cooperate by finding parent tiles to overzoom from and simplifying their geometries appropriately.

The number of successfully truncated tile pyramids is recorded in the truncated_zooms field in the strategies metadata. Unsuccessful attempts are included in the detail_reduced count.

tippecanoe-overzoom

The changes to tippecanoe-overzoom are meant for use in such a tile server. This PR adds --line-simplification and --tiny-polygon-size options to tippecanoe-overzoom to enable it to perform, at tile-serving time, the geometry simplification and "polygon dust" operations that are normally done during tiling.

The distance_from_line, douglas_peucker, and reduce_tiny_poly functions are moved to clip.cpp to make them accessible to overzoom.cpp.

--no-simplification-of-shared-nodes

The locations of corner vertices are now stored as simple x,y pairs instead of quadkeys to reduce encoding time, and there is a bloom filter to avoid doing the binary search for most non-corners.

tiling task dispatch

At the start of each zoom level, Tippecanoe previously made a static allocation of the child tile data generated during the previous zoom level to the tiling threads, sometimes resulting in other tiling threads waiting idly while a single "long pole" finished its work. The threads now read their tasks from a single work queue, generally resulting in better CPU utilization.

dropping and coalescing

The tile size limit previously took into account inflation from --retain-points-multiplier, but the feature limit did not, leading to slow convergence when tiles were flagged as too big because of their feature count. The maximum feature count is now scaled in the same way.

The --drop-densest and --coalesce-densest options previously iterated using 90% of the estimate, often taking a long time to converge. They now use 80% of the estimate instead.

strategies

The strategies metadata field previously overreported the number of features dropped or coalesced when it took multiple tries to get a zoom level to work. The numbers reported are now for the final version of the zoom level.

compiler warnings

There are several minor changes to fix type conversion warnings reported by G++.