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?
  • 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 Mar 1 '16 at 19:11
  • 1
    Are you looking for the Convex hull? – Ixrec Mar 1 '16 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 Mar 1 '16 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 Mar 1 '16 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 Mar 1 '16 at 19:25
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.

  • 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 Mar 1 '16 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 Mar 3 '16 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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