Отобразить или подогнать (x, y) координаты к 2D списку Python как можно лучше

Question

У меня есть список объектов, которые я сопоставил на плоскости XY на основе сходства. Точки для этих объектов хранятся в списке 2D-Python:

>>> points
[[x1, x2, ... , xn],
 [y1, y2, ... , yn]]

Координаты представляют собой числа с плавающей точкой и несколько очерчивают квадрат на диаграмме рассеяния. Это пример 2000 объектов, отображаемых на плоскости:

пример построенных точек

Я пытаюсь "вписать" эти точки в двумерный список в Python. По сути, я хочу сохранить относительные сходства точек, но сопоставить их с 2D-массивом. Например, скажем, у меня есть эти четыре точки, которые образуют идеальный квадрат:

(1, 1), (1, 2), (2, 1), and (2, 2)

Я хочу алгоритм, который отобразит их (как можно лучше, очевидно, не идеально, если точки не образуют идеально заполненный квадрат) в двумерный список, например так:

[[(2, 1), (2, 2)], 
 [(1, 1), (1, 2)]]

Если у меня n точек, то созданный 2D-список будет иметь размеры m на m, где m*m >= n. Любые неиспользованные места в списке будут иметь "Нет" внутри него.

Вот код, который я написал, пытаясь найти решение. Я передаю функции список объектов и 2D-список их xy-координат соответственно. Затем я вычисляю верхнюю и нижнюю границу в направлениях x и y и вычисляю "сетки", которые будет представлять каждая точка в списке, исходя из размера матрицы, которую я пытаюсь заполнить. Затем я перебираю каждую точку и пытаюсь поместить ее в ближайшее сопоставленное место, которое я могу найти.

Я пробую саму точку, и если она уже заполнена, я обыскиваю периметр вокруг точки в матрице. Если все они заполнены, я увеличиваю "радиус" периметра, чтобы проверить, пока не найду место.

Это имеет две проблемы: 1) Я знаю, что это не так точно, как отображение, которое я мог создать, но я искал в Интернете и не могу найти другие идеи. 2) Иногда этот код никогда не заканчивается и не может найти подходящее открытое место. Я знаю, что могу исправить эту ошибку где-нибудь при расчете периметра, но я решил, что лучше всего потратить время на поиск более оптимального решения. Следовательно, я здесь!

Это мой первый пост, поэтому прошу прощения, если я не следовал надлежащей процедуре.

Вот код Будем очень благодарны любой помощи.

from math import ceil, sqrt

def insert_nearest(lst, obj, i, j, N):
    if lst[i][j] == None: # see if "ideal" spot is empty
        lst[i][j] = obj
        return
    yu = i - 1 # top of box
    yd = i + 1 # bottom of box
    xl = j - 1 # left of box
    xr = j + 1 # right of bog
    while True:
        to_try = [(yu, x) for x in range(xl, xr+1)] + \
                 [(yd, x) for x in range(xl, xr+1)] + \
                 [(y, xl) for y in range(yu+1, yd)] + \
                 [(y, xr) for y in range(yu+1, yd)] # "perimeter" points to check
        for coord in to_try: # check around perimeter for any empty spots
            try: # in case index is out of range
                if lst[coord[0]][coord[1]] == None:
                    lst[coord[0]][coord[1]] = obj
                    return
            except:
                continue
        # if perimeter is full, increase "raduis" of box and try again
        yu -= 1
        yd += 1
        xl -= 1
        xr += 1

def build_matrix(objList, points):
    N = ceil(sqrt(len(objList)))
    matrix = [[None]*N]*N

    xinc = (max(points[0]) - min(points[0])) / N # grid lines in x direction
    yinc = (max(points[1]) - min(points[1])) / N # grid lines in y direction

    for i in range(len(points[0])):
        x = min(N-1, int(points[0][i] // xinc)) # map to integer spot in list
        y = min(N-1, int(points[1][i] // yinc)) # map to integer spot in list
        insert_nearest(matrix, objList[i], x, y, N)

    return matrix