Поиск координат для случайного распределения изображений на дисплее без наложения

Question

У меня есть следующий код, который случайным образом генерирует список (X, Y) кортежей:

import random
coords = []
for i in range(10):
    x = random.randint(85,939)
    y = random.randint(75,693)
    coords.append((x,y))

В последнем списке значения X каждого кортежа считаются перекрывающимися, если абсолютная разница между ними меньше 85, а значения Y считаются перекрывающимися, если абсолютная разница меньше 75. Как я могу сделать уверен, что ни один из кортежей в окончательном списке не будет перекрываться в обоих измерениях?

Answer 1

Самый простой способ сделать это - просто сохранить выборку и отбросить координаты, что приведет к перекрытию. Это, однако, станет очень неэффективным, когда вы приблизитесь к заполнению доступного пространства. Если это не проблема, вы должны использовать это решение.

Немного эффективнее и, насколько я могу судить, статистически эквивалентным является выборка одной координаты, например строки, первой. Затем вычислите занятую область в этой строке и выполните выборку из оставшихся позиций, если таковые имеются.

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

В идеале, вы не рассчитываете занятые области каждый раз, но сохраняете отображение строки в занятую область в этой строке и количество не полных строк и просто обновляете это отображение при вставке новых изображений. Вам понадобится память для n_rows + 1 дополнительных номеров.

Чтобы уточнить: при выборке из ограниченного пространства просто вычтите занятые позиции и получите результат выборки n . Затем найдите правильное положение для n , пройдя по координатной оси n шагов, пропустив все занятые позиции.