kd-tree

Construct kdtree for sets of point and in addition sets of simplices: line segments, triangles. The kd-tree supports nearest neighbor queries.

In contrast to points, one simplex may be referenced in both sub-trees. A necessary assumption for efficient searches is that this occurs infrequently. This is typically the case for planar triangulations or 3d surface meshes.

Note

The kdtree on points is similar to but less efficient (no recursive partition of data possible) and less general (only Euclidean distance) than NearestNeighbors.jl.

Todo

Distance to sets of tetrahedra.

DistanceQueries.kdtree — Method
tree = kdtree(scmatrix(Val(2), rand(2,n))
              [; maxpoints = 10, maxdepth = 32])

Build kd-tree of points in x for dimension k=N, e.g.,

Note

The referenced points – and any other data (e.g., index arrays defining simplices) are not copied by the constructors! The implementation assumes that these data are not modified for the lifetime of a referencing kd-tree.

See also nearest

source
DistanceQueries.nearest — Method
tree = kdtree(points)
d, i = nearest(tree, y)

Compute nearest point to y for points contained in tree.

Returns a tuple (d, i) with scalar distance d::T, and point index i::Int.

See also kdtree

source
Base.parent — Function
ptree = parent(stree::SimplexTree)

Get kd-tree of points spanning simplices.

source
DistanceQueries.kdtree — Method
tree = kdtree(scmatrix(Val(N), x), simplicies::Vector{SVector{M, Int}})

Build kd-tree from simplices by insertion into hierarchy defined by kdtree(points;...).

source
DistanceQueries.kdtree — Method
tree = kdtree(pointstree, simplicies::Vector{SVector{M, Int}})

Build kd-tree from (M-1)-simplices by insertion into hierarchy defined by pointstree.

source
DistanceQueries.kdtree — Method
tree = kdtree(scmatrix(Val(N), x), scmatrix(Val(M), simplicies))

Build kd-tree from (M-1)-simplices by insertion into hierarchy defined by kdtree(scmatrix(Val{(N), points);...) (i.e., points in N dimensions).

source
DistanceQueries.nearest — Method
tree = kdtree(points, simplices)
d, i, λ = nearest(tree, y)

Compute nearest point to y in simplices contained in tree.

Returns a tuple (d, i, λ) with scalar distance d::T, simplex index i::Int, and barycentric coordinates λ::NTuple{M, T}.

See also kdtree

source
DistanceQueries.point — Function
x = point(tree:SimplexTree{N, M, T},
          i::Int, λ::NTuple{M, T}) :: SVector{N, T}
x = point(tree,SimplexTree,
          nn :: Tuple{T, Int, NTuple{M, T}}) :: SVector{N, T}

Compute point from simplex i and barycentric coordinates λ, which are also the components returned from nn = nearest(tree, y).

source
DistanceQueries.points — Function
x = points(tree::SimplexTree{N, M})
x = points(tree::Simplices{N, M}, i::Int)
x = points(tree::Simplices{N, M}, s::SVector{M, Int})

Get points spanning simplices in kd-tree or points spanning one simplex i or s. x is a NTuple{M, SVector{N, T}}.

source
DistanceQueries.pointsmatrix — Function
X = pointsmatrix(tree::SimplexTree{N, M}, i::Int)
X = pointsmatrix(tree::SimplexTree{N, M}, s::SVector{M, Int})

Get points spanning one simplex i or s as columns in a SMatrix{N, M}.

source
DistanceQueries.simplex — Function
s = simplex(tree::SimplexTree{N, M}, i::Int)
s = simplex(tree::SimplexTree{N, M}, s::SVector{M, Int})

Get simplex i as SVector{M, Int} of indices.

source