Engee documentation

Neighbor search

It is often useful to search neighbor elements in a domain given a point of reference. This can be performed with search methods:

NeighborSearchMethod

A method for searching neighbors given a reference point.

search(pₒ, method, mask=nothing)

Return neighbors of point pₒ using method. Optionally, specify a mask for all indices of the domain.

search!(neighbors, pₒ, method; mask=nothing)

Update neighbors of point pₒ using method and return number of neighbors found. Optionally, specify a mask for all indices of the domain.

searchdists(pₒ, method, mask=nothing)

Return neighbors and distances of point pₒ using method. Optionally, specify a mask for all indices of the domain.

searchdists!(neighbors, distances, pₒ, method; mask=nothing)

Update neighbors and distances of point pₒ using method and return number of neighbors found. Optionally, specify a mask for all indices of the domain.

Search methods are constructed with various types of parameters. One may be interested in k-nearest neighbors, or interested in neighbors within a certain Neighborhood:

Neighborhood

A neighborhood is a geometry that is not attached to any specific point in space, and is free to slide over a domain of interest.

MetricBall(radii, rotation=nothing)
MetricBall(radius, metric=Euclidean())

A metric ball is a neighborhood that can be expressed in terms of a metric and a set of radii. The two main examples are the Euclidean ball an the Mahalanobis (ellipsoid) ball.

When multiple radii are provided, they can be rotated by a rotation specification from the Rotations.jl package. Alternatively, a metric from the Distances.jl package can be specified together with a single radius.

Examples

N-dimensional Euclidean ball with radius 1.0:

julia> euclidean = MetricBall(1.0)

Axis-aligned 3D ellipsoid with radii (3.0, 2.0, 1.0):

julia> mahalanobis = MetricBall((3.0, 2.0, 1.0))

The following example demonstrates neighbor search with the KNearestSearch method:

grid = CartesianGrid(10, 10)

# 4-nearest neighbors
searcher = KNearestSearch(grid, 4)

inds = search(Point(5.0, 5.0), searcher)
4-element view(::Vector{Int64}, 1:4) with eltype Int64:
 46
 45
 55
 56

The function search returns the indices of the elements in the domain that are neighbors of the point. The elements are:

grid[inds]
4-element Vector{Quadrangle{𝔼{2}, Cartesian2D{NoDatum, Quantity{Float64, 𝐋, Unitful.FreeUnits{(m,), 𝐋, nothing}}}}}:
 Quadrangle((x: 5.0 m, y: 4.0 m), ..., (x: 5.0 m, y: 5.0 m))
 Quadrangle((x: 4.0 m, y: 4.0 m), ..., (x: 4.0 m, y: 5.0 m))
 Quadrangle((x: 4.0 m, y: 5.0 m), ..., (x: 4.0 m, y: 6.0 m))
 Quadrangle((x: 5.0 m, y: 5.0 m), ..., (x: 5.0 m, y: 6.0 m))

Alternatively, the function searchdists also returns the distances to the (centroids) of the elements:

inds, dists = searchdists(Point(5.0, 5.0), searcher)

dists
4-element view(::Vector{Quantity{Float64, 𝐋, Unitful.FreeUnits{(m,), 𝐋, nothing}}}, 1:4) with eltype Quantity{Float64, 𝐋, Unitful.FreeUnits{(m,), 𝐋, nothing}}:
 0.7071067811865476 m
 0.7071067811865476 m
 0.7071067811865476 m
 0.7071067811865476 m

Finally, the functions search! and searchdists! can be used in hot loops to avoid unnecessary memory allocations.

BallSearch

BallSearch(domain, ball)

A method for searching neighbors in domain inside ball.

KNearestSearch

KNearestSearch(domain, k; metric=Euclidean())

A method for searching k nearest neighbors in domain according to metric.

KBallSearch

KBallSearch(domain, k, ball)

A method that searches k nearest neighbors and then filters these neighbors using a norm ball.