# Using an ellipse as a threshold for Nearest function

The Nearest function can receive as a threshold parameter a radius to look for elements inside that. From the documentation:

Nearest[data,x,{n,r}] give up to the n nearest elements to x within a radius r


What about if instead of a circle I want to use an ellipse as a threshold? So I would have an X and Y limit for the Nearest function.

I know that Nearest can receive a DistanceFunction as a parameter but I can't think of how to use that for this purpose.

Any ideas?

-
what you are asking is not quite clear, which may be why you are confused about the usage of distance function. You want the exclude points outside an ellipse (threshhold), but how to rank inside points is an independent criteria. Bills answer gives one interpretation. – george2079 Feb 25 '14 at 13:10

## 4 Answers

The simplest solution is to rescale the data. Suppose we have a distance limit of $r_x = 2$ and $r_y = 1$ and a point set

data = {{x1,y1}, {x2,y2}, ...}


Instead of working with data and these two radii, work with a single radius $r=1$ and the dataset

dataScaled = {{0.5 x1, y1}, {0.5 x2, y2}, ...}


Finally, transform the results back to the original coordinate system.

This can be generalized for arbitrary affine transformations, including rotations.

For example, let's assume that the ellipse is rotated 30 degrees and it has dimensions 2 and 1. This can be obtained from a circle by using the following transformation matrix:

backtrafo = N[RotationMatrix[30*Degree] . {{2, 0}, {0, 1}}]


Let's visualize it!

Graphics[GeometricTransformation[Circle[], AffineTransform[backtrafo]], Frame -> True]


We need to apply the reverse transformation of this on our data and use the result in Nearest:

trafo = Inverse[backtrafo];

Nearest[trafo.# & /@ data -> data, trafo.point, {n, 1}]


This will give us the all the points within the rotated ellipse drawn around point.

Let's test the method visually. Generate some points:

data = RandomReal[{-2, 2}, {100, 2}];


Find the points within the ellipse centred on the origin:

pointsWithin = Nearest[trafo.# & /@ data -> data, trafo.{0, 0}, {Infinity, 1}];


And finally visualize all points together with the ellipse:

Graphics[{
GeometricTransformation[Circle[], AffineTransform[backtrafo]],
Point[data], {Red, Point[pointsWithin]}}, Frame -> True]


Technical comment: An advantage of this method compared to using a DistanceFunction is that a custom DistanceFunction will prevent Nearest from using a very efficient quad-tree data structure, and it will resort to a much slower pairwise-distance calculation.

Thanks to Michael E2 for suggestion on simple and efficient code!

-
@MichaelE2 You mean scale back the results? – Szabolcs Feb 25 '14 at 13:52
Hmm, what about a tilted ellipse? I guess one would multiply the data by the inverse matrix representing the rotation and scaling... – Ajasja Feb 25 '14 at 13:58
@Ajasja Yes, exactly. The OP was asking for different radii along the $x$ and $y$ axes so I didn't include that. Generally, any affine transformation (and then reverse transformation) should work. – Szabolcs Feb 25 '14 at 13:58
@Szabolcs I meant scale x. Something like Nearest[trafo.data -> data, trafo.x, {n, 1}]. Scaling back might be more efficient, unless many calls to a NearestFunction are to be used. (Still I think x needs to be scaled, right?) – Michael E2 Feb 25 '14 at 14:16
@MichaelE2 Thanks! Finally I've gotten around to fixing it up :) – Szabolcs Feb 26 '14 at 0:59

I guess one method would be to take the larger radius of your ellipse to collect all possible candidates with

Nearest[data,x,{n,r}]


and after that filter them with e.g. Select to find all points that are inside your ellipse.

-

DistanceFunction is one way to go. For example, the code below generates a random set of points in the box with all elements drawn from -1 to 1 and then selects the 20 points that are closest to the point {0.5, 0} (in the sense of an ellipse defined by the matrix a). In the example, a is tall and skinny, but could have any orientation and scale.

data = RandomReal[{-1, 1}, {100, 2}];
a = {{2, 0}, {0, 1/2}};
f[x_, y_] := Norm[a.(x - y)];
nf = Nearest[data, {0.5, 0}, 20, DistanceFunction -> f];
ListPlot[nf, PlotRange -> {{-1, 1}, {-1, 1}}]


-
The only issue with DistanceFunction is that for custom functions the performance is much worse than for the standard euclidian distance, so a combination with @halirutan´s approach may be more performant for large sets. – Yves Klett Feb 25 '14 at 7:20
@Yves, bill: One could transform the data so the ellipse maps to a circle, use the standard Euclidean distance there, and transform the results back. – Rahul Feb 25 '14 at 9:00
@RahulNarain sounds like a good plan for such distance functions - looking forward to your answer :D – Yves Klett Feb 25 '14 at 12:18
@Yves: I had to go to bed. I'm happy to see that Szabolcs has taken care of it. :) – Rahul Feb 25 '14 at 17:26

The DistanceFunction seems the way to go. However you may also want to rescale your dataset so that the ellipse constraint becomes a circle constraint.

-
This was my thought, too. To improve this answer you might want to flesh it out with some code and an explanation of the advantages of this approach. – Michael E2 Feb 25 '14 at 13:48