Предположим, что у меня есть n число одинаковых по размеру и равномерно развернутых квадратов в ограниченной области в 2D системе координат (с плавающей запятой). Ящики не должны перекрываться. Теперь я хочу найти свободное место для еще одной коробки. Мне нужно несколько советов по алгоритму для решения этой проблемы. Есть идеи?Графический алгоритм для подгонки в квадрат между набором квадратов
Для этого должен быть алгоритм линии сканирования. Вы говорите, что коробки одинаково повернуты, поэтому вы должны иметь возможность повернуть систему координат, если необходимо, чтобы края ящиков были параллельны координатам x и y. Затем я сортировал ящики в порядке координат y.
Теперь попробуйте поместить коробку в самое нижнее возможное положение. Прочтите из отсортированных ящиков, чтобы найти все ящики, достаточно низкие, чтобы помешать вашему размещению и создать упорядоченный набор (например, красно-черное дерево или аналогичный контейнерный класс) этих полей. Теперь просканируйте этот набор ящиков и посмотрите, есть ли достаточно большой промежуток, чтобы разместить коробку. Если нет, используйте исходный отсортированный список ящиков, чтобы найти и удалить нижний ящик, так что вы можете рассмотреть возможность размещения нового поля чуть выше этого нижнего поля, чтобы он не мог помешать этому. Добавьте больше ящиков из отсортированного списка, чтобы покрыть все ящики, достаточно высокие, чтобы помешать этой новой возможной высоте окна. Следите за тем, где вы удалили ящики из списка, и проверьте там, чтобы открыть, открыт ли пробел, достаточный для хранения коробки. Если нет, повторите упражнение, пока не найдете пробел или пробег в верхней части возможной области.
Это выглядит как стоимость N log N для начальной сортировки, а затем стоимость не более логарифма N на каждый ящик для вставки и удаления ячеек из упорядоченного набора. Проверка пробелов не стоит дороже, потому что вы проверяете только пробел в месте, где вы только что удалили ящик. Поэтому я думаю, что общая стоимость составляет N log N.
Вы хотите * любое * свободное квадратное пространство или свободное пространство, которое будет держать самый большой квадрат? – Geobits
@Geobits Дополнительный квадрат, чтобы он поместился, имеет тот же размер, что и все остальные квадраты. В конце концов, я хочу, чтобы ближайшее свободное пространство от данной точки – user1169629