search

systemed / tilemaker

Make OpenStreetMap vector tiles without the stack
https://tilemaker.org/
Other
1.4k stars 226 forks source link

Faster polygon combining #681

Closed systemed closed 4 months ago

systemed commented 4 months ago

The combine_polygons_below option significantly slows tile generation (#270). In #383 we moved to faster code but it's still not especially fast.

This PR further improves it by using a neat bit of code from https://github.com/boostorg/geometry/discussions/947#discussioncomment-5820218. It also successfully merges more adjoining polygons. Newer Boost has merge_elements but we can't rely on users having that yet.

It also removes a bit of template-y indirection by replacing CheckNextObjectAndMerge and MergeIntersecting with a simple while loop.

For Reims using my 2014 Mac mini:

No combine_polygons_below: 12s

Screenshot 2024-02-16 at 10 40 20

Using combine_polygons_below, current master: 122s

Screenshot 2024-02-16 at 10 40 11

Using combine_polygons_below, this PR: 80s

Screenshot 2024-02-16 at 13 38 48

There's clearly still room for improvement (maybe using an rtree to quickly identify polygons that intersect, and only unioning those?) but this is a worthwhile step forward.