# rangesearch

Find all neighbors within specified distance using searcher object

## Description

searches for all neighbors (i.e., points, rows, or observations) in
`Idx`

= rangesearch(`Mdl`

,`Y`

,`r`

)`Mdl.X`

within radius `r`

of each point (i.e.,
row or observation) in the query data `Y`

using an exhaustive
search or a *K*d-tree. `rangesearch`

returns
`Idx`

, which is a column vector of the indices of
`Mdl.X`

within `r`

units.

returns the indices of the observation in `Idx`

= rangesearch(`Mdl`

,`Y`

,`r`

,`Name,Value`

)`Mdl.X`

within radius
`r`

of each observation in `Y`

with additional
options specified by one or more `Name,Value`

pair arguments. For
example, you can specify to use a different distance metric than is stored in
`Mdl.Distance`

or a different distance metric parameter than is
stored in `Mdl.DistParameter`

.

`[`

additionally returns the matrix `Idx`

,`D`

]
= rangesearch(___)`D`

using any of the input
arguments in the previous syntaxes. `D`

contains the distances
between the observations in `Mdl.X`

within radius
`r`

of each observation in `Y`

. By default,
the function arranges the columns of `D`

in ascending order by
closeness, with respect to the distance metric.

## Examples

### Search for Neighbors Within a Radius Using *K*d-tree and Exhaustive Search

`rangesearch`

accepts `ExhaustiveSearcher`

or `KDTreeSearcher`

model objects to search the training data for the nearest neighbors to the query data. An `ExhaustiveSearcher`

model invokes the exhaustive searcher algorithm, and a `KDTreeSearcher`

model defines a *K*d-tree, which `rangesearch`

uses to search for nearest neighbors.

Load Fisher's iris data set. Randomly reserve five observations from the data for query data. Focus on the petal dimensions.

load fisheriris rng(1); % For reproducibility n = size(meas,1); idx = randsample(n,5); X = meas(~ismember(1:n,idx),3:4); % Training data Y = meas(idx,3:4); % Query data

Grow a default two-dimensional *K*d-tree.

MdlKDT = KDTreeSearcher(X)

MdlKDT = KDTreeSearcher with properties: BucketSize: 50 Distance: 'euclidean' DistParameter: [] X: [145x2 double]

`MdlKDT`

is a `KDTreeSearcher`

model object. You can alter its writable properties using dot notation.

Prepare an exhaustive nearest neighbor searcher.

MdlES = ExhaustiveSearcher(X)

MdlES = ExhaustiveSearcher with properties: Distance: 'euclidean' DistParameter: [] X: [145x2 double]

`MdlES`

is an `ExhaustiveSearcher`

model object. It contains the options, such as the distance metric, to use to find nearest neighbors.

Alternatively, you can grow a *K*d-tree or prepare an exhaustive nearest neighbor searcher using `createns`

.

Search training data for the nearest neighbor indices that correspond to each query observation that are within a 0.5 cm radius. Conduct both types of searches and use the default settings.

```
r = 0.15; % Search radius
IdxKDT = rangesearch(MdlKDT,Y,r);
IdxES = rangesearch(MdlES,Y,r);
[IdxKDT IdxES]
```

`ans=`*5×2 cell array*
{[1 4 8 27 32 45 47 2 35 37 ... ]} {[1 4 8 27 32 45 47 2 35 37 ... ]}
{[ 13]} {[ 13]}
{[6 17 39 40 1 4 8 27 32 45 ... ]} {[6 17 39 40 1 4 8 27 32 45 ... ]}
{[ 64 66]} {[ 64 66]}
{1x0 double } {1x0 double }

`IdxKDT`

and `IdxES`

are cell arrays of vectors corresponding to the indices of `X`

that are within 0.15 cm of the observations in `Y`

. Each row of the index matrices corresponds to a query observation.

Compare the results between the methods.

cellfun(@isequal,IdxKDT,IdxES)

`ans = `*5x1 logical array*
1
1
1
1
1

In this case, the results are the same.

Plot the results for the setosa irises.

setosaIdx = strcmp(species(~ismember(1:n,idx)),'setosa'); XSetosa = X(setosaIdx,:); ySetosaIdx = strcmp(species(idx),'setosa'); YSetosa = Y(ySetosaIdx,:); figure; plot(XSetosa(:,1),XSetosa(:,2),'.k'); hold on; plot(YSetosa(:,1),YSetosa(:,2),'*r'); for j = 1:sum(ySetosaIdx) c = YSetosa(j,:); circleFun = @(x1,x2)r^2 - (x1 - c(1)).^2 - (x2 - c(2)).^2; fimplicit(circleFun,[c(1) + [-1 1]*r, c(2) + [-1 1]*r],'b-') end xlabel 'Petal length (cm)'; ylabel 'Petal width (cm)'; title 'Setosa Petal Measurements'; legend('Observations','Query Data','Search Radius'); axis equal hold off

### Search for Neighbors Within a Radius Using the Mahalanobis Distance

Load Fisher's iris data set.

`load fisheriris`

Remove five irises randomly from the predictor data to use as a query set.

rng(1); % For reproducibility n = size(meas,1); % Sample size qIdx = randsample(n,5); % Indices of query data X = meas(~ismember(1:n,qIdx),:); Y = meas(qIdx,:);

Prepare a default exhaustive nearest neighbor searcher.

Mdl = ExhaustiveSearcher(X)

Mdl = ExhaustiveSearcher with properties: Distance: 'euclidean' DistParameter: [] X: [145x4 double]

`Mdl`

is an `ExhaustiveSearcher`

model.

Find the indices of the training data (`X`

) that are within 0.15 cm of each point in the query data (`Y`

). Specify that the distances are with respect to the Mahalanobis metric.

r = 1; Idx = rangesearch(Mdl,Y,r,'Distance','mahalanobis')

`Idx=`*5×1 cell array*
{[26 38 7 17 47 4 27 46 25 10 39 20 21 2 33]}
{[ 6 21 25 4 19]}
{[ 1 34 33 22 24 2]}
{[ 84]}
{[ 69]}

Idx{3}

`ans = `*1×6*
1 34 33 22 24 2

Each cell of `Idx`

corresponds to a query data observation and contains in `X`

a vector of indices of the neighbors within 0.15cm of the query data. `rangesearch`

arranges the indices in ascending order by distance. For example, using the Mahalanobis distance, the second nearest neighbor of `Y(3,:)`

is `X(34,:)`

.

### Compute Distances of Neighbors Within a Radius

Load Fisher's iris data set.

`load fisheriris`

Remove five irises randomly from the predictor data to use as a query set.

rng(4); % For reproducibility n = size(meas,1); % Sample size qIdx = randsample(n,5); % Indices of query data X = meas(~ismember(1:n,qIdx),:); Y = meas(qIdx,:);

Grow a four-dimensional *K*d-tree using the training data. Specify to use the Minkowski distance for finding nearest neighbors.

Mdl = KDTreeSearcher(X);

`Mdl`

is a `KDTreeSearcher`

model. By default, the distance metric for finding nearest neighbors is the Euclidean metric.

Find the indices of the training data (`X`

) that are within 0.5 cm from each point in the query data (`Y`

).

r = 0.5; [Idx,D] = rangesearch(Mdl,Y,r);

`Idx`

and `D`

are five-element cell arrays of vectors. The vector values in `Idx`

are the indices in `X`

. The `X`

indices represent the observations that are within 0.5 cm of the query data, `Y`

. `D`

contains the distances that correspond to the observations.

Display the results for query observation 3.

Idx{3}

`ans = `*1×2*
127 122

D{3}

`ans = `*1×2*
0.2646 0.4359

The closest observation to `Y(3,:)`

is `X(127,:)`

, which is `0.2646`

cm away. The next closest is `X(122,:)`

, which is `0.4359`

cm away. All other observations are greater than `0.5`

cm away from `Y(5,:)`

.

## Input Arguments

`Mdl`

— Nearest neighbor searcher

`ExhaustiveSearcher`

model object | `KDTreeSearcher`

model object

Nearest neighbor searcher, specified as an `ExhaustiveSearcher`

or `KDTreeSearcher`

model object, respectively.

If `Mdl`

is an `ExhaustiveSearcher`

model, then
`rangesearch`

searches for nearest neighbors using an exhaustive
search. Otherwise, `rangesearch`

uses the grown
*K*d-tree to search for nearest neighbors.

`Y`

— Query data

numeric matrix

Query data, specified as a numeric matrix.

`Y`

is an *m*-by-*K* matrix.
Rows of `Y`

correspond to observations (i.e., examples),
and columns correspond to predictors (i.e., variables or features). `Y`

must
have the same number of columns as the training data stored in `Mdl.X`

.

**Data Types: **`single`

| `double`

### Name-Value Arguments

Specify optional pairs of arguments as
`Name1=Value1,...,NameN=ValueN`

, where `Name`

is
the argument name and `Value`

is the corresponding value.
Name-value arguments must appear after other arguments, but the order of the
pairs does not matter.

*
Before R2021a, use commas to separate each name and value, and enclose*
`Name`

*in quotes.*

**Example: **`'Distance','minkowski','P',3`

specifies to find all
observations in `Mdl.X`

within distance `r`

of
each observation in `Y`

, using the Minkowski distance metric with
exponent `3`

.

**For Both Nearest Neighbor Searchers**

`Distance`

— Distance metric

`Mdl.Distance`

(default) | `'cityblock'`

| `'euclidean'`

| `'mahalanobis'`

| `'minkowski'`

| `'seuclidean'`

| function handle | ...

Distance metric used to find neighbors of the training data to the query observations,
specified as the comma-separated pair consisting of `'Distance'`

and a
character vector, string scalar, or function handle.

For both types of nearest neighbor searchers, `rangesearch`

supports these
distance metrics.

Value | Description |
---|---|

`'chebychev'` | Chebychev distance (maximum coordinate difference). |

`'cityblock'` | City block distance. |

`'euclidean'` | Euclidean distance. |

`'minkowski'` | Minkowski distance. The default exponent is 2. To specify a different exponent, use the
`'P'` name-value pair argument. |

If `Mdl`

is an `ExhaustiveSearcher`

model object, then
`rangesearch`

also supports these distance metrics.

Value | Description |
---|---|

`'correlation'` | One minus the sample linear correlation between observations (treated as sequences of values). |

`'cosine'` | One minus the cosine of the included angle between observations (treated as row vectors). |

`'hamming'` | Hamming distance, which is the percentage of coordinates that differ. |

`'jaccard'` | One minus the Jaccard coefficient, which is the percentage of nonzero coordinates that differ. |

`'mahalanobis'` | Mahalanobis distance, computed using a positive definite covariance matrix. To change the
value of the covariance matrix, use the
`'Cov'` name-value pair
argument. |

`'seuclidean'` | Standardized Euclidean distance. Each coordinate difference between rows in
`Mdl.X` and the query matrix is
scaled by dividing by the corresponding element of
the standard deviation computed from
`Mdl.X` . To specify another
scaling, use the `'Scale'`
name-value pair argument. |

`'spearman'` | One minus the sample Spearman's rank correlation between observations (treated as sequences of values). |

If `Mdl`

is an `ExhaustiveSearcher`

model object, then you
can also specify a function handle for a custom distance metric
by using `@`

(for example,
`@distfun`

). The custom distance
function must:

Have the form

`function D2 = distfun(ZI,ZJ)`

.Take as arguments:

A 1-by-

*K*vector`ZI`

containing a single row from`Mdl.X`

or`Y`

, where*K*is the number of columns of`Mdl.X`

.An

*m*-by-*K*matrix`ZJ`

containing multiple rows of`Mdl.X`

or`Y`

, where*m*is a positive integer.

Return an

*m*-by-1 vector of distances`D2`

, where`D2(`

is the distance between the observations)`j`

`ZI`

and`ZJ(`

.,:)`j`

For more details, see Distance Metrics.

**Example: **`'Distance','minkowski'`

`P`

— Exponent for Minkowski distance metric

`2`

(default) | positive scalar

Exponent for the Minkowski distance metric, specified as the comma-separated pair consisting
of `'P'`

and a positive scalar. This argument is valid only if
`'Distance'`

is `'minkowski'`

.

**Example: **`'P',3`

**Data Types: **`single`

| `double`

`SortIndices`

— Flag to sort returned indices according to distance

`true`

(`1`

) (default) | `false`

(`0`

)

Flag to sort returned indices according to distance, specified as the
comma-separated pair consisting of `'SortIndices'`

and
either `true`

(`1`

) or
`false`

(`0`

).

For faster performance when `Y`

contains many
observations that have many nearest points, you can set
`SortIndices`

to `false`

. In
this case, `rangesearch`

returns the indices of the
nearest points in no particular order. When
`SortIndices`

is `true`

, the
function arranges the indices of the nearest points in ascending order
by distance.

**Example: **`'SortIndices',false`

**Data Types: **`logical`

**For Exhaustive Nearest Neighbor Searchers**

`Cov`

— Covariance matrix for Mahalanobis distance metric

`cov(Mdl.X,'omitrows')`

(default) | positive definite matrix

Covariance matrix for the Mahalanobis distance metric, specified as the comma-separated pair
consisting of `'Cov'`

and a positive definite matrix.
`Cov`

is a *K*-by-*K* matrix,
where *K* is the number of columns of `Mdl.X`

. If you
specify `Cov`

and do not specify
`'`

`Distance`

`','mahalanobis'`

,
then `rangesearch`

returns an error message.

**Example: **`'Cov',eye(3)`

**Data Types: **`single`

| `double`

`Scale`

— Scale parameter value for standardized Euclidean distance metric

`std(Mdl.X,'omitnan')`

(default) | nonnegative numeric vector

Scale parameter value for the standardized Euclidean distance metric, specified as the
comma-separated pair consisting of `'Scale'`

and a nonnegative numeric
vector. `Scale`

has length *K*, where
*K* is the number of columns of `Mdl.X`

.

The software scales each difference between the training and query data using the
corresponding element of `Scale`

. If you specify
`Scale`

and do not specify
`'`

`Distance`

`','seuclidean'`

,
then `rangesearch`

returns an error message.

**Example: **```
'Scale',quantile(Mdl.X,0.75) -
quantile(Mdl.X,0.25)
```

**Data Types: **`single`

| `double`

**Note**

If you specify
`'`

`Distance`

`'`

,
`'`

`Cov`

`'`

,
`'`

`P`

`'`

, or
`'`

`Scale`

`'`

, then
`Mdl.Distance`

and `Mdl.DistParameter`

do
not change value.

## Output Arguments

`Idx`

— Training data indices of nearest neighbors

cell array of numeric vectors

Training data indices of nearest neighbors, returned as a cell array of numeric vectors.

`Idx`

is an
*m*-by-`1`

cell array such that cell
`j`

(`Idx{j}`

) contains an
*m _{j}*-dimensional vector of
indices of the observations in

`Mdl.X`

that are within
`r`

units to the query observation
`Y(j,:)`

. If `SortIndices`

is
`true`

, then `rangesearch`

arranges
the elements of the vectors in ascending order by distance.`D`

— Distances of nearest neighbors to the query data

cell array of numeric vectors

Distances of the neighbors to the query data, returned as a numeric matrix or cell array of numeric vectors.

`D`

is an *m*-by-`1`

cell array such that cell `j`

(`D{j}`

)
contains an *m _{j}*-dimensional vector
of the distances that the observations in

`Mdl.X`

are from
the query observation `Y(j,:)`

. All elements of the vector
are less than `r`

. If `SortIndices`

is
`true`

, then `rangesearch`

arranges
the elements of the vectors in ascending order.## Tips

`knnsearch`

finds the *k*
(positive integer) points in `Mdl.X`

that are
*k*-nearest for each `Y`

point. In contrast,
`rangesearch`

finds all the points in `Mdl.X`

that are within distance `r`

(positive scalar) of each
`Y`

point.

## Alternative Functionality

`rangesearch`

is an object function that requires an `ExhaustiveSearcher`

or a `KDTreeSearcher`

model object, query data, and a distance. Under equivalent
conditions, `rangesearch`

returns the same results as `rangesearch`

when you specify the name-value pair argument
`'NSMethod','exhaustive'`

or
`'NSMethod','kdtree'`

, respectively.

## Extended Capabilities

### C/C++ Code Generation

Generate C and C++ code using MATLAB® Coder™.

Usage notes and limitations:

This table contains notes about the arguments of

`rangesearch`

. Arguments not included in this table are fully supported.Argument Notes and Limitations `Mdl`

There are two ways to use

`Mdl`

in code generation. For an example, see Code Generation for Nearest Neighbor Searcher.Use

`saveLearnerForCoder`

,`loadLearnerForCoder`

, and`codegen`

(MATLAB Coder) to generate code for the`rangesearch`

function. Save a trained model by using`saveLearnerForCoder`

. Define an entry-point function that loads the saved model by using`loadLearnerForCoder`

and calls the`rangesearch`

function. Then use`codegen`

to generate code for the entry-point function.Include

`coder.Constant(Mdl)`

in the`-args`

value of`codegen`

(MATLAB Coder).

If

`Mdl`

is a`KDTreeSearcher`

object, and the code generation build type is a MEX function, then`codegen`

(MATLAB Coder) generates a MEX function using Intel^{®}Threading Building Blocks (TBB) for parallel computation. Otherwise,`codegen`

generates code using`parfor`

(MATLAB Coder).MEX function for the

*k*d-tree search algorithm —`codegen`

generates an optimized MEX function using Intel TBB for parallel computation on multicore platforms. You can use the MEX function to accelerate MATLAB^{®}algorithms. For details on Intel TBB, see https://software.intel.com/content/www/us/en/develop/tools/oneapi/components/onetbb.html.If you generate the MEX function to test the generated code of the

`parfor`

version, you can disable the usage of Intel TBB. Set the`ExtrinsicCalls`

property of the MEX configuration object to`false`

. For details, see`coder.MexCodeConfig`

(MATLAB Coder).MEX function for the exhaustive search algorithm and standalone C/C++ code for both algorithms — The generated code of

`rangesearch`

uses`parfor`

(MATLAB Coder) to create loops that run in parallel on supported shared-memory multicore platforms in the generated code. If your compiler does not support the Open Multiprocessing (OpenMP) application interface or you disable OpenMP library, MATLAB Coder™ treats the`parfor`

-loops as`for`

-loops. To find supported compilers, see Supported Compilers. To disable OpenMP library, set the`EnableOpenMP`

property of the configuration object to`false`

. For details, see`coder.CodeConfig`

(MATLAB Coder).

`'Distance'`

Cannot be a custom distance function.

Must be a compile-time constant; its value cannot change in the generated code.

`'SortIndices'`

Not supported. The output arguments are always sorted. Name-value pair arguments Names in name-value pair arguments must be compile-time constants. For example, to allow a user-defined exponent for the Minkowski distance in the generated code, include

`{coder.Constant('Distance'),coder.Constant('Minkowski'),coder.Constant('P'),0}`

in the`-args`

value of`codegen`

(MATLAB Coder).`Idx`

The sorted order of tied distances in the generated code can be different from the order in MATLAB due to numerical precision.

Starting in R2020a,

`rangesearch`

returns integer-type (`int32`

) indices, rather than double-precision indices, in generated standalone C/C++ code. Therefore, the function allows for strict single-precision support when you use single-precision inputs. For MEX code generation, the function still returns double-precision indices to match the MATLAB behavior.

For more information, see Introduction to Code Generation and Code Generation for Nearest Neighbor Searcher.

## Version History

**Introduced in R2011b**

## Open Example

You have a modified version of this example. Do you want to open this example with your edits?

## MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

# Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

You can also select a web site from the following list:

## How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

### Americas

- América Latina (Español)
- Canada (English)
- United States (English)

### Europe

- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)

- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)