Cluster adjacent points

Question

I have a sequence of xy planes with integer coordinates and each one has points scattered differently over it.

For each plane I would like perform clustering of the points, putting in the same cluster a point that is far from another point in the cluster by less than d (or exactly d).
For example if there is a point P1(x,y) in the cluster and d=1 also

• P2(x+1,y)
• P3(x,y+1)
• P4(x+1,y+1)
• P5(x-1,y)
• P6(x,y-1)
• P7(x-1,y-1)
• P8(x+1,y-1)
• P9(x-1,y+1)

will fall in the same cluster. Graphically:

P9   P3   P4    
   \ |  /
P5 - P1 - P2
   / |  \
P7   P6   P8

Which clustering algorithm is best suited for this task?

Answer 1

This is not so much a clustering problem, but you have your neighbor relation, and you want to compute the transitive closure of this neighbor relation.

This is a much simpler problem, and it has an obvious and efficient straightforward solution (breadth-first search):

While there are unprocessed points:

1. Initialize a new empty result set.
2. Working set = choose any one (!) unprocessed point
3. While the working set is not empty:
   1. Add working set to result set
   2. Mark all points in the working set as processed
   3. Working set = all ''unprocessed'' neighbors of the previous working set
4. Return the result set as new group.