GitHub

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:

Meshes.BoundedNeighborSearchMethod — Type
BoundedNeighborSearchMethod

A method for searching neighbors with the property that the number of neighbors is bounded above by a known constant (e.g. k-nearest neighbors).

source
Meshes.search — Function
search(pₒ, method, mask=nothing)

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

source
Meshes.search! — Function
search!(neighbors, pₒ, method; mask=nothing)

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

See BoundedNeighborSearchMethod for additional details.

source
Meshes.searchdists — Function
searchdists(pₒ, method, mask=nothing)

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

See BoundedNeighborSearchMethod for additional details.

source
Meshes.searchdists! — Function
searchdists!(neighbors, distances, pₒ, method; mask=nothing)

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

See BoundedNeighborSearchMethod for additional details.

source

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:

Meshes.Neighborhood — Type
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.

source
Meshes.MetricBall — Type
MetricBall(radii, rotation=I)
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> MetricBall(1.0)

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

julia> MetricBall((3.0, 2.0, 1.0))
source

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}, CoordRefSystems.Cartesian2D{CoordRefSystems.NoDatum, Unitful.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{Unitful.Quantity{Float64, 𝐋, Unitful.FreeUnits{(m,), 𝐋, nothing}}}, 1:4) with eltype Unitful.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

KNearestSearch

Meshes.KNearestSearch — Type
KNearestSearch(domain, k; metric=Euclidean())

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

source

KBallSearch

Meshes.KBallSearch — Type
KBallSearch(domain, k, ball)

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

See MetricBall for additional details.

source