Edit on 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.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 method and return number of neighbors found. Optionally, specify a mask for all indices of the domain.

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

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

source
Meshes.searchdists! — Function
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.

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=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))
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:
 56
 45
 46
 55

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, Float64}}:
 Quadrangle((5.0, 5.0), ..., (5.0, 6.0))
 Quadrangle((4.0, 4.0), ..., (4.0, 5.0))
 Quadrangle((5.0, 4.0), ..., (5.0, 5.0))
 Quadrangle((4.0, 5.0), ..., (4.0, 6.0))

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{Float64}, 1:4) with eltype Float64:
 0.7071067811865476
 0.7071067811865476
 0.7071067811865476
 0.7071067811865476

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 norm ball.

source