10
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – george2079
    Feb 25, 2014 at 13:10
  • $\begingroup$ 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. $\endgroup$
    – zakk
    Feb 25, 2014 at 13:19

3 Answers 3

12
$\begingroup$

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!

$\endgroup$
7
  • $\begingroup$ @MichaelE2 You mean scale back the results? $\endgroup$
    – Szabolcs
    Feb 25, 2014 at 13:52
  • 3
    $\begingroup$ Hmm, what about a tilted ellipse? I guess one would multiply the data by the inverse matrix representing the rotation and scaling... $\endgroup$
    – Ajasja
    Feb 25, 2014 at 13:58
  • $\begingroup$ @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. $\endgroup$
    – Szabolcs
    Feb 25, 2014 at 13:58
  • $\begingroup$ @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?) $\endgroup$
    – Michael E2
    Feb 25, 2014 at 14:16
  • $\begingroup$ @MichaelE2 Thanks! Finally I've gotten around to fixing it up :) $\endgroup$
    – Szabolcs
    Feb 26, 2014 at 0:59
5
$\begingroup$

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}}]

enter image description here

$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$
    – Yves Klett
    Feb 25, 2014 at 7:20
  • 4
    $\begingroup$ @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. $\endgroup$
    – user484
    Feb 25, 2014 at 9:00
  • $\begingroup$ @RahulNarain sounds like a good plan for such distance functions - looking forward to your answer :D $\endgroup$
    – Yves Klett
    Feb 25, 2014 at 12:18
  • $\begingroup$ @Yves: I had to go to bed. I'm happy to see that Szabolcs has taken care of it. :) $\endgroup$
    – user484
    Feb 25, 2014 at 17:26
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.