My question is, I have a matrix having points. How do I find points which are in contact computationally?

Question

Let me be more clear and specific. I have a 2-d sparse matrix of size 10 * 10 of points of different colours . The co-ordinates of the points are integers, i.e points may be at positions (1,1) , (10,9 ) for example but not (1.1,2.5) etc.
Now the Problem is to make an algorithm which finds which points that appear in a series of four or more points in contact with each other and of a particular colour.The colour will be given beforehand. The algorithm should return the set of such points.
An example of points in contact is (1,1) and (2,2). Two points are in contact when the difference between their x-coordinates and y-coordinates are both less than 1.
Please do help me solve this. If you even know where I can find algorithms for co-ordinate geometry and where this particular problem might be covered please do let me know. Its really urgent and important.
Thanks a ton

Answer 1

This isn't all that difficult. I assume you represent your data as a 10x10 matrix containing colour values, using e.g. -1 to represent "no point at this location" and non-negative integers to represent various colours.

Start off with one collection for each existing point. Maintain an array of pointers to the collection containing each point; this will help you later. Also, have a "finished" flag on each collection, initially set to "false" on all of them.

For each collection, iterate through the points belonging to it. For each point, look up the colour of all adjacent points. For any adjacent point of the same colour, check which collection it is in; if the same as the one currently being processed, ignore and move on. If different, move all the points from that collection into the current collection and delete the other collection.

If no new points are found during the iteration, mark the collection as finished.

Process all collections in this way, then check to see if they are all finished. If not, repeat the process until all collections are finished.

I'd also suggest tagging each collection with the (common) colour of the points in it, and the number of points contained in it. This will be useful when you're looking for all collections of 4 or more points with a particular colour.