# Neighbourhood points (2d)

I have a 2d coordinates system with some points on it, like this one:

Now I am looking for an algorithm (or just some approach) to find neighboured points. So, if you have the coordinates of one point, and a list of other ones, how to find all neighbours of that point? I really have no idea how to do this.

If I look at the orange point, the grey, the blue and the light green one are obviously neighbours of it, but what about the others?

You could put circles around the points... and look if any other of the points is in this circle. Those points should be listed as being neigbours of the first point.

What I had: An array with tuples in it, every tuple representing the (x,y)-coodrinates of a point.

What I wanted: A dictionary/map: the keys are every tuple from the above list and the value of such a point-tuple should be a list out of all it's neighbours.

Problems:

• How do I define what is a neighbourhood of two points? What would the inputs be to such a definition (e.g. proximity threshold)?
• What would be a strategy to design and implement this?
• This is just variation on the closest pair of points problem and the nearest neighbor problem. Have you read those Wikipedia pages and looked at their algorithms?
– user40980
Mar 1, 2016 at 19:11
• Are you looking for the Convex hull? Mar 1, 2016 at 19:12
• @MichaelT Since I want all neighbours of any point in the space and not just the two ones that are nearest to each other, I don't know to make this variation. No, I have not read through these articles, I will do now. Mar 1, 2016 at 19:17
• That is the problem you need to solve. You describe the blue and light green ones as "obviously neighbors" - but what do you mean by that. You appear to have some threshold that you are using.
– user40980
Mar 1, 2016 at 19:21
• That is the essence of programming - transforming thought to code. You need to identify the heuristics you are using to identify neighborhoods of points.
– user40980
Mar 1, 2016 at 19:25