Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

speed up special positive case of Intersects/FindIntersecting #8

Open
cldellow opened this issue Oct 5, 2024 · 0 comments
Open

speed up special positive case of Intersects/FindIntersecting #8

cldellow opened this issue Oct 5, 2024 · 0 comments

Comments

@cldellow
Copy link
Owner

cldellow commented Oct 5, 2024

systemed#765 does some magic for the special case where there are 0 intersections.

The motivating case was that very large polygons seemed to be indexed poorly by boost's r-tree.

But very large polygons likely also happen for political shapes like country/state/county/city boundaries.

In fact, Hiker Atlas's zindex export job calls FindIntersecting on 3 shape files: countries, states, and parks.

And indeed, the call to intersect with countries is the slowest, even though likely every call should be a hit.

Maybe there's room for some improvement here? If the layer is indexed, try to sniff a good "coarseness" for indexing, and then maintain a lazy special case index?

e.g. read the geometries and see what zoom level would work such that the median geometry can be expressed as a union of ~50-100 tiles. Then, on demand, if that tile covers exactly 1 shape, record it. Then, any future query can be satisfied by walking up the zoom hierarchy and looking for a match. If a match is found, we're done. Otherwise, proceed as we do today.

eg: say Canada can be covered by 100 z6 tiles. We'll choose z6 as our indexing coarseness. When we are asked to determine the intersection of a building with the country layer, we'll get the bounding box of the building -- which will likely fit entirely within a z16 tile, e.g. We'll translate the z16 tile to its z6 equivalent. If we've never done an intersects query of the z6 tile with the shape layer, we'll do that now. If the z6 tile is entirely contained within Canada, we'll remember that. We can now instantly answer queries like "does it intersect? is it covered?" and queries like "how much of the area is covered?" devolve to "what is the area of the object?"

This is a bit hand wavey, but I think there's likely soemthing here

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant