Effectively gather data with small differences

I frequently encounter themes where I have a set of data, then I need to gather up those identical ones. However, due to numerical error in data, GatherBy cannot be directly implemented, while Gather seems too slow.

Take this case as an example: I have a set of 2D points, i.e. pts={{0.,0.},{1.,1.},{2.,1.},{2.0001,1.0001},{1.0049,0.},{1.0051,0.}}, and I need to gather up those points which represent the same thing under a tolerance of approximately 0.01 unit.

A natual solution is Gather[pts,Norm[#1-#2]<.01&], however Gather suffers from performance issue when the list is large. Another natural solution is GatherBy[pts,Round[#,0.01]&], however this is not correct, the last two elements should be gathered together while in this method, they are not.

FYI: A possible implementation is as follows, however I fear that this might be too slow, so I'm asking are there any built-in function which can serve this purpose or are there any better implementation.

TolerantGatherBy[list_, f_, fdiff_] :=
Module[{k, current = <||>, temp, fval},
Do[If[fval = f[i];
temp = SelectFirst[Keys@current, fdiff[fval, #] &, k]; temp === k,
AppendTo[current, f[i] -> {i}],
AppendTo[current[temp], i]], {i, list}];
Values@current
]

TolerantGatherBy[pts, Identity, Norm[#1 - #2] <= 0.01 &]


Or if I want to find out the index of those gathered together, I can write:

TolerantGatherBy[Range@Length@pts, pts[[#]] &, Norm[#1 - #2] <= 0.01 &]


I would like a solution which is similar to the performance of GatherBy while accepting tolerance.

ClusteringComponents does what you want; maybe play with the DistanceFunction and other options:

ClusteringComponents[pts, Length[pts], 1]

(*    {1, 2, 3, 3, 4, 4}    *)

• Thanks a lot for the quick answer, I will look into it! BTW, is this complicated function efficient comparing to Gather/GatherBy?
– Wjx
Feb 21, 2020 at 7:27
• @Wjx before you worry about performance, you should worry about algorithmic stability. Gather assumes that your criterion is transitive (some kind of equality). But as your criterion is not transitive (i.e., it can easily be that A is close to B and B is close to C, but A is not close to C), you need some general way to look for clusters. Feb 21, 2020 at 8:19
• I'm aware of this issue, but in my use case the error is small. Stability is not a issue as long as the cluster's size is always smaller than half the threshold I use. if A is close to B, B is close to C, then A will be close to C.
– Wjx
Feb 21, 2020 at 8:46
• So GatherBy[pts, Round]? Feb 21, 2020 at 18:05
• Check the example in the question~, GatherBy[pts,Round] could be incorrect when two data points are 0.4999 and 0.5001.
– Wjx
Feb 22, 2020 at 7:54

A possible solution for this particular case of gathering index of points which are near to other points:

PointGatherBy[pts_, tol_] :=
Values@PositionIndex@
Merge[Flatten[
MapIndexed[Function[s, s -> {Length@#1, #2[[1]]}] /@ #1 &,
Flatten[Values[
PositionIndex[
Round[Transpose[Transpose[pts] + #], tol]]] & /@
Tuples[{0, tol/2}, Length@pts[[1]]], 1]], 1],
TakeLargestBy[#, First, 1][[1, -1]] &]


performance check:

n = 2000;
pts = Join[RandomReal[0.001, {n, 2}] + #, #] &@RandomReal[100, {n, 2}];

Gather[Range@Length@pts,
Norm[pts[[#1]] - pts[[#2]]] <= .01 &]; // AbsoluteTiming
TolerantGatherBy[Range@Length@pts, pts[[#]] &,
Norm[#1 - #2] <= 0.01 &]; // AbsoluteTiming
PointGatherBy[pts, 0.01]; // AbsoluteTiming
ClusteringComponents[pts, Length[pts], 1]; // AbsoluteTiming


{16.9512, Null}

{15.7348, Null}

{0.242784, Null}

{57.5847, Null}