3

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

coordinate system with some points on it

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?
Improve this question
15
  • 2
    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
    Commented Mar 1, 2016 at 19:11
  • 1
    Are you looking for the Convex hull?
    – Ixrec
    Commented 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.
    – palsch
    Commented Mar 1, 2016 at 19:17
  • 4
    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
    Commented Mar 1, 2016 at 19:21
  • 4
    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
    Commented Mar 1, 2016 at 19:25

1 Answer 1

Reset to default
10

I'm going to define "neighboring points" as points that share an edge with area of point in Voronoi diagram.

To calculate which points are "neighbors" in voronoi diagram, you use Delaunay triangulation.

Improve this answer
2
  • 2
    That's a rather reasonable definition (and possibly a neat codegolf challenge). As an example, could you show the image this would result in as a visual aid?
    – user40980
    Commented Mar 1, 2016 at 21:22
  • 1) I like Voronoi diagrams. :) 2) I will accept your answer as soon as I have "translated" it into code. 3) Thanks!
    – palsch
    Commented Mar 3, 2016 at 20:07

Not the answer you're looking for? Browse other questions tagged or ask your own question.