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.

Sign up for GitHub

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

Jump to bottom

Space filling curve based spatial index #22

Open
daniel-j-h opened this issue Jul 24, 2021 · 2 comments
Open

Space filling curve based spatial index #22

daniel-j-h opened this issue Jul 24, 2021 · 2 comments

Comments

@daniel-j-h
Copy link
Member

daniel-j-h commented Jul 24, 2021 •
edited
Loading

For

we are implementing space filling curves anyway. By now we have a z-order / morton code encoding function.

There are ways to search the space filling curve directly, meaning we won't need e.g. an rtree as a spatial index.

Explore if this is feasible and what the characteristics are.

Note: there's a chapter about searching space filling curves in Foundations of Multidimensional and Metric Data Structures which I have a copy around here. Probably good idea to re-read and look into the papers they reference.

Read
@daniel-j-h
Copy link
Member Author

The search space pruning idea visualized; from the paper

Multidimensional Range Search in Dynamically Balanced Trees, H. Tropf, H. Herzog, 1981

zorder-search

@daniel-j-h
Copy link
Member Author

By now we have a z-order space filling curve

https://github.com/tinygraph/tinygraph/blob/7047d80631c5b41244c9fcc6c7ee77aed80828a0/tinygraph-zorder.h

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@daniel-j-h