Algorithm to partition an area - find points close to each other

Question

Is there an algorithm to find all points with a set distance from each other ? Or all rectangles that are touching ?

I divide the plane (in lat/lon coordinate system, of certain limits) in sample rectangles of n x n, and each rectangle gets a value from 0 to 7. I need to be able to show islands for each value. n > 100 - could be 15000.

I have written some very brute-force code, but I only managed to get some very rough rectangles...

Example of my input:

111111111111111122222111
111221122222111122211111
111222222222111112211111
111222222111111112211111
111221111113311112111111
111111111113311111111111

The above, defined using points in a rectangle (each 1 and 2 and others being rectangles that I acquire through some sampling...) - I end up having a few thousands - possibly a hundred thousands little rectangles, and I would like to get the regions of each kind.

I have discovered that I can get the regions, using a convex hull algorithm - if I can properly separate the rectangles (or their center points) into regions.

At the input to my function, I would get only rectangles with the same metric.

Example:

1111111111111111     111
111  11     1111   11111
111         11111  11111
111      11111111  11111
111  111111  1111 111111
11111111111  11111111111


                22222
   22  22222    222
   222222222     22
   222222        22
   22            2

I would like to find some algorithm so I can get the rectangles that are touching, or the points that are at a certain distance from each other, in separate sets (they have absolute coordinates), so I can run the convex hull algorithm on the resultant sets.

Since the rectangles are created from sampling, they are identical in width/height.

Is there such a thing ?

My code is in VB.NET, but C#, or any language or pseudocode would help.

Thank you very much.

Edit:

I have all kinds of tests, like

Public Function AreTwoRectanglesNearEachOther(ByRef one As RectangleF, ByRef two As RectangleF) As Integer
        If Math.Abs(one.Right - two.Left) <= distance_lat Then
            Return 1    ' one is before two
        ElseIf Math.Abs(two.Right - one.Left) <= distance_lat Then
            Return -1   ' one is after two
        ElseIf Math.Abs(two.Top - one.Bottom) <= distance_lon AndAlso one.Right - two.Left > 0 Then
            Return 2    ' one is above two
        ElseIf Math.Abs(one.Top - two.Bottom) <= distance_lon AndAlso one.Right - two.Left > 0 Then
            Return -2   ' one is below two
        Else
            Return 0    ' they are not next to each other
        End If
    End Function

where distance_lat and distance_lon is dim_lat/10, respectively dim_lon/10

Answer 1

Thank you mmgp - I did implement the connected component labeling algorithm - it was a wonderful idea.