У меня есть 3-мерный массив numpy с двоичными (0 и 1) значениями, представляющими вокселизированное пространство. Значение 1 означает, что воксель занят, 0 означает, что он пуст. Для простоты опишу проблему с 2D-данными. Пример такого кармана может выглядеть следующим образом:
1 1 1 1 1 1 1
1 1 0 0 0 1 1
1 0 0 0 0 0 1
1 0 0 1 0 0 1
1 0 0 1 1 1 1
1 1 1 1 1 1 1
У меня также есть набор данных фрагментов, которые меньше кармана. Думайте о них как о кусочках тетриса, если хотите, только в 3D. Как и в игре, фрагменты можно вращать. Некоторые примеры:
0 1 1 1 1 1 0 1 1 0
1 1 0 0 0 1 0 1 1 0
Я хочу заполнить карман фрагментами, чтобы оставшееся пустое пространство (0) было как можно меньше.
До сих пор я думал, что Я мог бы разложить карман на меньшие прямоугольные angular карманы, вычислить размеры этих прямоугольных angular областей и фрагментов, а затем просто сопоставить их на основе этих размеров. Или, может быть, я мог бы повернуть фрагменты так, чтобы значения 1 были ближе к «стене», и сфокусироваться на прямоугольниках ближе к границе. Затем я мог бы снова взглянуть на области прямоугольника angular и работать над заполнением ядра / внутренней части кармана. Чтобы оптимизировать результат, я могу обернуть эти шаги вокруг поиска по дереву Монте-Карло al go.
Очевидно, я не жду полного ответа, но если у вас есть лучшие идеи о том, как подойти к этому , Я был бы рад это услышать. Также приветствуются любые ссылки на аналогичные алгоритмы космического поиска / статьи.