# Selecting for 2D points that are within a threshold distance of an upper- and lower-bound number of points

I have a very large set of 2D points:

numberOf2DPoints = 10^6;
pointList = RandomReal[{0, 1000}, {numberOf2DPoints, 2}];


I'd like to find a way to quickly generate a distribution I can study for the number of points within a distance $r$ from each point, and then I'd like to select points that have at least a lowerbound $k_a$ and an upperbound $k_b$ number of points within a distance $r$ of themselves. Is there a way to use a function like Nearest to accomplish this?

Clarification --- The lowerbound $k_a$ and upperbound $k_b$ refers strictly to the count for the number of points in a circular disk of radius $r$ centered on a particular point (hopefully this makes sense). So I'd want basically a simple histogram for what this distribution of point counts looks like, and to select points that have satisfy the upper- and lowerbound point count criterion.

• Related: (32923) (7203910)
– ssch
Oct 27, 2013 at 18:53
• – rm -rf
Oct 27, 2013 at 19:25

It's not easy to find in the documentation on Nearest and NearestFunction but they can return all points within a certain radius.

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

So you can get all points that lie between a distance of 2 and 3 like so:

numberOf2DPoints = 10^6;
pointList = RandomReal[{0, 1000}, {numberOf2DPoints, 2}];
nf = Nearest[pointList];

Complement[
nf[pointList[], {Infinity, 3}],
nf[pointList[], {Infinity, 2}]]


Perhaps there is yet another way to call a NearestFunction that removes the need for Complement

• Awesome, sometimes I have so wanted a Nearest[data, x, {n, r}]. Oct 27, 2013 at 20:16
• @ssch Fantastic! To clarify something, I meant selecting for points that had an upper and lowerbound count of points, not to count the number of points between an upper or lowerbound Euclidean distance from the point. So the Complement operation isn't necessary. :) Oct 27, 2013 at 20:24

This is the distribution you're after. Not as fast as one might want, but:

numberOf2DPoints = 10^5;
pointList = RandomReal[{0, 1000}, {numberOf2DPoints, 2}];
f = Nearest[pointList];
leuc = EuclideanDistance[#, f[#, 2][]] & /@ pointList;
h[leuc_, min_, max_] := Length@Select[leuc, min <= # <= max &]
Plot3D[h[leuc, min, max], {min, 0, 7}, {max, 0, 7}, PlotRange -> All] • Perhaps there is a way for computing h[] faster. Let's see. Oct 27, 2013 at 20:17
• This is also great, but I think I was unclear in my writing, and I apologize. I meant a distribution for the count of the number of points within a disk centered on each point. So it should be a simple 1D curve or histogram. Oct 27, 2013 at 20:26
• @RTaylor "for each point" or "for one point" ? Oct 27, 2013 at 20:31
• I mean that we place a disk of radius $r$ on the plane centered at each point. I'm then looking to generate a distribution for the number of points contained in a disk by looking at all disks. Oct 27, 2013 at 20:33
• For the selection part, I then want to select points where their corresponding disks contain at least $k_a$ points and at most $k_b$ points. Is this clearer? Apologies again. Oct 27, 2013 at 20:34