Consider a list of points:
pts = Partition[RandomReal[1, 10000], 2];
ListPlot[pts]
I'd like to delete points so that the minimum distance between two points is 0.05. The following code does the job:
pts2 = {pts[[1]]};
Table[If[Min[Map[Norm[pts[[i]] - #] &, pts2]] > 0.05,
AppendTo[pts2, pts[[i]]]], {i, 2, Length[pts],
1}]; // AbsoluteTiming (* -> 1.35 *)
ListPlot[pts2]
But it becomes slow for large lists, probably because of AppendTo
which does not know what type is going to come next.
How could this be done more efficiently? Note: there is no uniqueness of the resulting list, but that's not a problem.
Just for better referencing, let me give another formulation of the question: How to delete points in a neighbourhood of other points of a list?
Nearest
$\endgroup$pts2 = Union[pts, SameTest -> (Norm[#1 - #2] < 0.05 &)];
$\endgroup$Union
withSameTest
option set explicitly, has quadratic complexity in the number of points, because it performs pairwise conparisons. $\endgroup$