Filter two lists of 2D coordinates such that only those that have a nearby neighbour in the other list are collected

I have two sets of coordinates:



I’m only interested in the coordinates that have a very close (overlapping in the plot below) different coloured neighbour. The threshold distance isn’t precise, just small relative to the spread of the other points. I need to be able to do this for about a million other similar sets of coordinates so efficiency is reasonably important.

The solution should provide a list of red points and a list of green points. Every one of which must have a exactly one neighbour in the other list. It’s not necessary to know exactly which points pair together.




You might also want to look at…
– s0rce
Nov 4 ’15 at 5:50


1 Answer


Mathematica wasn’t easily importing your example data from dropbox so I started by generating some random data.

green = RandomReal[1000, {100, 2}];
red = RandomReal[1000, {100, 2}];

Now we can compute NearestFunctions for both datasets.

nfgreen = Nearest@green;
nfred = Nearest@red;

And using Select to determine which points are close (defined arbitrarily as EuclideanDistance <= 10) Select[red, EuclideanDistance[#, First@nfgreen[#, 1]] <= 10 &] Select[green, EuclideanDistance[#, First@nfred[#, 1]] <= 10 &] You might be able to speed this up using Pick instead of select or clever use of Compile but I haven't played around much and I'm on a slow laptop. 3   There is no need to use Select. One can just use Flatten[nfred[#, {All, 10}] & /@ green, 1] and Flatten[nfgreen[#, {All, 10}] & /@ red, 1]. – Karsten 7. Nov 4 '15 at 6:02      @Karsten7.: Won't that produce duplicate copies of any red point is within 10 units of two green points (and vice versa)? – Rahul Nov 4 '15 at 8:27      Can be fixed with Union or DeleteDuplicates. – shrx Nov 4 '15 at 10:00      @Rahul Yes. And could either remove duplicates, as shrx commented, or use this fact to remove all points having more than one neighbor (and therefore also not exactly one). – Karsten 7. Nov 4 '15 at 19:20