How to allow a max Manhattan distance between all the points in a group

Question

I have a 2D-array in which I want to make groups where all the points in a group have a max Manhattan distance between them. The groups can be disjoint. For example, from this starting array (10 x 10):

[[ 67  97  72  35  73  77  80  48  21  34]
 [ 11  30  16   1  71  68  72   1  81  23]
 [ 85  31  94  10  50  85  63  11  61  69]
 [ 64  36   8  37  36  72  96  20  91  19]
 [ 99  54  84  56   3  80  41  45   1   8]
 [ 97  88  21   8  54  55  88  45  63  82]
 [ 13  53   1  90  39  28  48  15  86   8]
 [ 26  63  36  36   3  29  33  26  54  58]
 [ 74  40  53  12  21  17   4  87  14  22]
 [ 23  98   3 100  85  12  65  21  83  97]]

I should be able to divide it into different groups.

I currently have a function that finds the possible points I could add to a group with a starting point (here munip is the first point of the group):

def possible_munips(x, y, munip, dist_manhattan_max, temp_array):
    list = []
    for i in range(y):
        for j in range(x):
            if (j, i) != munip and munipIsValid(j, i, munip, dist_manhattan_max) and temp_array[i][j] != -1:
                list.append((j, i, temp_array[i][j]))

I iterate through an 2D-array, temp_array, in which the points that have already been put in a group have their value set to -1. munipIsValid checks if the point is at a max Manhattan distance from the starting point.

I then just add one by one the points until I've reached the desired length (k) of a group and I make sure every time I add a new point to a group, the group stays valid, like this:

munips = possible_munips(x, y, munip, dist_manhattan_max, temp_array)

while len(new_group) < k:
    point = munips[0]
    new_group.append(point)
    if not groupIsValid(new_group, distManhattanMax, len(new_group)):
        new_group.remove(point)
    munips.remove(point)
    current_sol.append(new_group)

for groups in current_sol:
    for munip in groups:
        temp_array[munip[1], munip[0]] = -1

I've also tried adding a swapping function which tries to swap points between groups in order to make both of them valid. But sometimes it doesn't find a solution and I'm left with and invalid group.

Answer 1

In layman's terms, you wish to find k classification areas also known as clusters. In this case, I recommend you first read about clustering. After you acquire enough knowledge, you can advance on this related question, which generalizes this classification for a custom distance function.