rangesearch

Class: KDTreeSearcher

Find all neighbors within specified distance using KDTreeSearcher object

Syntax

idx = rangesearch(NS,Y,r)
[idx,D] = rangesearch(NS,Y,r)
[idx,D] = rangesearch(NS,Y,r,Name,Value)

Description

idx = rangesearch(NS,Y,r) finds all points in NS.X that are within distance r of the Y points. Rows of NS.X and Y correspond to observations, and columns correspond to variables.

[idx,D] = rangesearch(NS,Y,r) returns the distances between each row of Y and the rows of NS.X that are r or less distant.

[idx,D] = rangesearch(NS,Y,r,Name,Value) finds nearby points with additional options specified by one or more Name,Value pair arguments.

Tips

  • For a fixed positive integer K, knnsearch finds the K points in NS.X that are nearest each Y point. In contrast, for a fixed positive real value r, rangesearch finds all the points in NS.X that are within a distance r of each Y point.

Input Arguments

NS

KDTreeSearcher object, constructed using KDTreeSearcher or createns.

Y

my-by-n numeric matrix, where each row represents one n-dimensional point. The number of columns n must equal the number of columns in NS.X.

r

Search radius, a scalar. rangesearch finds all NS.X points (rows) that are within distance r of each Y point. The meaning of distance depends on the Distance name-value pair argument.

Name-Value Pair Arguments

Specify optional comma-separated pairs of Name,Value arguments. Name is the argument name and Value is the corresponding value. Name must appear inside single quotes (' '). You can specify several name and value pair arguments in any order as Name1,Value1,...,NameN,ValueN.

'Distance'

String or function handle specifying the distance metric.

ValueDescription
'euclidean'Euclidean distance.
'cityblock'City block distance.
'minkowski'Minkowski distance. The default exponent is 2. To specify a different exponent, use the 'P' name-value pair argument.
'chebychev'Chebychev distance (maximum coordinate difference).

For definitions, see Distance Metrics.

Default: NS.Distance

'P'

Positive scalar indicating the exponent of Minkowski distance. This argument is only valid when the Distance name-value pair argument is 'minkowski'.

Default: 2

Output Arguments

idx

my-by-1 cell array, where my is the number of rows in Y. idx{I} contains the indices of points (rows) in NS.X whose distances to Y(I,:) are not greater than r. The entries in idx{I} are in ascending order of distance.

D

my-by-1 cell array, where my is the number of rows in Y. D{I} contains the distance values between Y(I,:) and the corresponding points in idx{I}.

Definitions

Distance Metrics

For definitions, see Distance Metrics.

Examples

expand all

Search for All Nearest Neighbors Within a Specified Distance

Search for all nearest neighbors within a specified distance of a query point using rangesearch on a KDTreeSearcher model.

Specify X and Y as samples of 5-dimensional, normally distributed variables.

rng(1);           % For reproducibility
X = randn(100,5); % Training data
Y = randn(10,5);  % Query data

Grow a K d-tree using X.

Mdl = KDTreeSearcher(X);

Mdl is a KDTreeSearcher model. By default, the software sets the distance metric to the Euclidean distance. You can change the default distance using the 'Distance' name-value pair argument or using dot notation.

Find the points in the training data (specifically, the property Mdl.X) that are within a Euclidean distance 1.5 of each point in the query data (Y).

[Idx,D] = rangesearch(Mdl,Y,1.5)
Idx = 

    [1x4  double]
    [1x12 double]
    [1x6  double]
    [1x0  double]
    [1x9  double]
    [         10]
    [1x2  double]
    [1x4  double]
    [1x0  double]
    [1x5  double]


D = 

    [1x4  double]
    [1x12 double]
    [1x6  double]
    [1x0  double]
    [1x9  double]
    [     1.2398]
    [1x2  double]
    [1x4  double]
    [1x0  double]
    [1x5  double]

Idx and D are cell vectors of numeric row vectors with length equal to the number of rows of Y (10 in this case). Idx{j} is a row vector containing the row indices of X corresponding to all observations within 1.5 units of observation Y(j,:). D{j} contain their distances. The software orders the indices in Idx{j} and distances in D{j} by closest to furthest.

To illustrate the meanings Idx and D, print all row indices of Mdl.X corresponding to those that are within 1.5 units of observation 7 in Y. Also, print their distances.

Idx{7}
D{7}
ans =

    60    30


ans =

    1.2620    1.2638

Mdl.X(60,:) is the closest observation in X to Y(7,:), and Mdl.X(30,:) is the next closest. Mdl.X(60,:) is 1.2620 units away from Y(7,:), and Mdl.X(30,:) is 1.2638 units away. Mdl.X(60,:) and Mdl.X(30,:) are the only two observations in Mdl.X that are within 1.5 units of Y(7,:).

Algorithms

For an overview of the kd-tree algorithm, see k-Nearest Neighbor Search Using a kd-Tree.

Alternatives

rangesearch is the KDTreeSearcher method for distance search. It is equivalent to the rangesearch function with the NSMethod name-value pair argument set to 'kdtree'.

rangesearch is the ExhaustiveSearcher method for distance search. It is equivalent to the rangesearch function with the NSMethod name-value pair argument set to 'exhaustive'.

Was this topic helpful?