alyst / spatialindexing.jl Goto Github PK

View Code? Open in Web Editor NEW

28.0 4.0 9.0 815 KB

Spatial data indexing in pure Julia (R*-trees etc)

License: MIT License

Julia 100.00%

r-tree spatial-indexing julia spatial-data r-star-tree

spatialindexing.jl's Introduction

SpatialIndexing.jl

Documentation:

SpatialIndexing package provides the tools for efficient in-memory indexing of spatial data in Julia.

Installation

using Pkg; Pkg.add("SpatialIndexing")

from Julia REPL.

Features

R-tree

R-tree organizes data into hierarchical structure and ensures that:

minimal bounding rectangles (MBRs) of the nodes (rectangles that encompass all data elements in the subtree) stay compact,
MBRs of the nodes from the same R-tree level have minimal overlap with each other.

The key benefit of R-tree is its ability to rebalance itself and maintain efficient structure while handling dynamic data (massive insertions and deletions).

SpatialIndexing provides RTree type that supports:

different R-tree variants (classic R-tree, R*-tree, linear and quadratic node splits)
insert!(tree, item), delete!(tree, item) for element-wise insertion and deletion
bulk-loading of data using Overlap-minimizing Top-down (OMT) approach (load!(tree, data))
subtract!(tree, reg) for removing data within specified region reg
findfirst(tree, reg, [id]), contained_in(tree, reg) and intersects_with(tree, reg) spatial queries

Simple Spatial Index

SimpleSpatialIndex stores all data elements in a vector. So, while insertion of new data takes constant time, the time of spatial searches grows linearly with the number of elements. This spatial index is intended as a reference implementation for benchmarking and not recommended for production usage.

TODO

Usage

TODO

examples folder contains spiral.jl and pareto.jl examples of using R-tree for storing spatial data.

References

A.Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching” Proc. 1984 ACM-SIGMOD Conference on Management of Data (1985), pp.47-57.
N. Beckmann, H.P. Kriegel, R. Schneider, B. Seeger, "The R*-tree: an efficient and robust access method for points and rectangles" Proc. 1990 ACM SIGMOD international conference on Management of data (1990), p.322
T. Lee and S. Lee, "OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree", CAiSE Short Paper Proceedings (2003) paper

spatialindexing.jl's People

Contributors

Stargazers

Watchers

Forkers

decardinb wookay tpatel0409 juliohm hs-ye longemen3000 tnwolf1 danielvandh simsurace

spatialindexing.jl's Issues

function Base.show(io::IO, tree::RTree) prints entire tree, crashes REPL

Hi team,

Wondering if we can discuss the behaviour of https://github.com/alyst/SpatialIndexing.jl/blob/master/src/rtree/show.jl

Specifically: the last line of the show() function, when we have large trees (200k+ nodes) and using this interactively, i have to remember to always suppress the output and never print the object in the REPL, or otherwise it will flood the REPL and i basically have to restart the julia session.

function Base.show(io::IO, tree::RTree)
    print(io, typeof(tree))
    print(io, "(variant="); print(io, tree.variant)
    print(io, ", tight_mbrs="); print(io, tree.tight_mbrs)
    print(io, ", nearmin_overlap="); print(io, tree.nearmin_overlap)
    print(io, ", fill_factor="); print(io, tree.fill_factor)
    print(io, ", split_factor="); print(io, tree.split_factor)
    print(io, ", reinsert_factor="); print(io, tree.reinsert_factor)

    print(io, ", leaf_capacity="); print(io, capacity(Leaf, tree))
    print(io, ", branch_capacity="); print(io, capacity(Branch, tree)); println(io, ")")
    print(io, length(tree)); print(io, " element(s) in "); print(io, height(tree));
    print(io, " level(s) ("); print(io, join(reverse(tree.nnodes_perlevel), ", ")); println(io, " node(s) per level):")
    # this line which recursively prints every branch/node
    _show(io, tree.root, recurse=true, indent=1)  end

Can we consider having changing this to print(io::IO, tree::RTree) and having show(io::IO, tree::RTree) without the final recursion call?

That will make working with the RTree interactively much easier, as users can control when they want to print the full tree.

Arrays for Tree building and querying

Can we make the building and query of the RTree to accept Arrays? Then maybe make the Point and Rect Struct internal? I have 10 million or even more query points (in Array) and I always have to convert them to Points via Tuple before querying. This leads to excessive memory allocations in my loop (over 200 k allocations).

It will be nice to have something similar to the API of LibSpatialIndex.jl for creating and querying RTree.

Insertion
LibSpatialIndex.insert!(rtree, 1, [0.,0.], [1.,1.])

Query
LibSpatialIndex.intersects(rtree, [1.,1.])

Add a LICENSE file

UndefVarError: enl_diff not defined when using RTree

I was messing around and ran into an undefined variable error when trying to make a RtreeLinear structure rather than the default. I was trying to follow the example pareto.jl with some modifications.

#works
using SpatialIndexing
const SI = SpatialIndexing

a = rand(3,100)

pts = Vector{SI.Point{Float64, 3}}()

for i in 1:100
push!(pts, SI.Point(tuple(reshape(a[:,i],(1,3))...)))
end

julia> seq_tree2 = RTree{Float64, 3}(Int, String, leaf_capacity = 20, branch_capacity = 20,variant = SI.RTreeLinear)

RTree{Float64,3,SpatialElem{Float64,3,Int64,String}}(SpatialIndexing.RTreeLinear, true, 6, 0.7, 0.4, 0.3, SpatialIndexing.Leaf{Float64,3,SpatialElem{Float64,3,Int64,String}}(nothing, SpatialIndexing.Rect{Float64,3}((NaN, NaN, NaN), (NaN, NaN, NaN)), SpatialElem{Float64,3,Int64,String}[]), 0, [1], 0, 0, 0, 0, SpatialIndexing.NodePool{SpatialIndexing.Branch{Float64,3,SpatialElem{Float64,3,Int64,String}},SpatialIndexing.Branch{Float64,3,SpatialElem{Float64,3,Int64,String}}}(SpatialIndexing.Branch{Float64,3,SpatialElem{Float64,3,Int64,String}}[], 100, 20), SpatialIndexing.NodePool{SpatialIndexing.Branch{Float64,3,SpatialElem{Float64,3,Int64,String}},SpatialIndexing.Leaf{Float64,3,SpatialElem{Float64,3,Int64,String}}}(SpatialIndexing.Branch{Float64,3,SpatialElem{Float64,3,Int64,String}}[], 100, 20), SpatialIndexing.NodePool{SpatialIndexing.Leaf{Float64,3,SpatialElem{Float64,3,Int64,String}},SpatialElem{Float64,3,Int64,String}}(SpatialIndexing.Leaf{Float64,3,SpatialElem{Float64,3,Int64,String}}[], 100, 20))

#error here
julia> for (i, pt) in enumerate(pts)
           insert!(seq_tree2, pt, i, string(i))
       end
ERROR: UndefVarError: enl_diff not defined
Stacktrace:
 [1] _split!_rtree(::SpatialIndexing.Leaf{Float64,3,SpatialElem{Float64,3,Int64,String}}, ::RTree{Float64,3,SpatialElem{Float64,3,Int64,String}}) at /home/crgxcf/.julia/packages/SpatialIndexing/y5jrZ/src/rtree/split.jl:137
 [2] _split!(::SpatialIndexing.Leaf{Float64,3,SpatialElem{Float64,3,Int64,String}}, ::RTree{Float64,3,SpatialElem{Float64,3,Int64,String}}) at /home/crgxcf/.julia/packages/SpatialIndexing/y5jrZ/src/rtree/split.jl:244
 [3] _insert!_fullnode(::SpatialIndexing.Leaf{Float64,3,SpatialElem{Float64,3,Int64,String}}, ::SpatialElem{Float64,3,Int64,String}, ::SpatialIndexing.SubtreeContext{Float64,3,SpatialElem{Float64,3,Int64,String},Nothing}) at /home/crgxcf/.julia/packages/SpatialIndexing/y5jrZ/src/rtree/insert.jl:208
 [4] _insert!(::SpatialIndexing.Leaf{Float64,3,SpatialElem{Float64,3,Int64,String}}, ::SpatialElem{Float64,3,Int64,String}, ::SpatialIndexing.SubtreeContext{Float64,3,SpatialElem{Float64,3,Int64,String},Nothing}) at /home/crgxcf/.julia/packages/SpatialIndexing/y5jrZ/src/rtree/insert.jl:44
 [5] _insert!(::SpatialIndexing.SubtreeContext{Float64,3,SpatialElem{Float64,3,Int64,String},Nothing}, ::SpatialElem{Float64,3,Int64,String}, ::Int64) at /home/crgxcf/.julia/packages/SpatialIndexing/y5jrZ/src/rtree/insert.jl:52
 [6] _insert!(::RTree{Float64,3,SpatialElem{Float64,3,Int64,String}}, ::SpatialElem{Float64,3,Int64,String}, ::Int64) at /home/crgxcf/.julia/packages/SpatialIndexing/y5jrZ/src/rtree/insert.jl:55
 [7] insert! at /home/crgxcf/.julia/packages/SpatialIndexing/y5jrZ/src/rtree/insert.jl:11 [inlined]
 [8] insert!(::RTree{Float64,3,SpatialElem{Float64,3,Int64,String}}, ::SpatialIndexing.Point{Float64,3}, ::Int64, ::String) at /home/crgxcf/.julia/packages/SpatialIndexing/y5jrZ/src/rtree/insert.jl:21
 [9] top-level scope at ./REPL[7]:2

The relevant section of the code in split.jl is the only match for enl_diff

            max_cost_diff = -Inf
            sel_cost1 = sel_cost2 = NaN
            sel_child_ix = 0
            i = findfirst(available)
            while i !== nothing
                child_mbr = mbr(node[i])
                enl1 = area(combine(mbr(n1), child_mbr)) - area1
                enl2 = area(combine(mbr(n2), child_mbr)) - area2
                enl_delta = abs(enl1 - enl2)

                if enl_diff > max_enl_diff
                    max_cost_diff = enl_diff
                    sel_enl1 = enl1
                    sel_enl2 = enl2
                    sel_child_ix = i
                    (variant(tree) != RTreeQuadratic) && break
                end

Is enl_diff supposed to be enl_delta from the line above?

Help with usage

This package seems super well-written 👏🏽 thanks for the making it available.

I am having some difficulty understanding the arguments of the RTree constructor, even after reading the examples as suggested in the README. Could you please elaborate on the K and V arguments?

RTree{T,N}(::Type{V}; kwargs...) where {T,N,V} =    RTree{T,N,SpatialElem{T,N,Nothing,V}}(; kwargs...)
RTree{T,N}(::Type{K}, ::Type{V}; kwargs...) where {T,N,K,V} =    RTree{T,N,SpatialElem{T,N,K,V}}(; kwargs...)

Does "intersects_with" returns the sorted results ?

Couldn't traceback from the code if the method "intersects_with" in the query, returns the results in the sorted order in the distance of the query region from the objects in the tree ?

TagBot trigger issue

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

If you'd like for me to do this for you, comment TagBot fix on this issue.
I'll open a PR within a few hours, please be patient!

Update to Project.toml

Would a PR be welcome to update from REQUIRE to Project.toml? Julia's new package manager is superb and it would be nice to update this accordingly. BTW, I love the fact that you managed to write such a useful package without any extra dependency 🥇