Алгоритм оптимального размещения сферы между другими сферами в трехмерной ограничительной рамке?

Question

Я борюсь с проблемой 3D, для которой я пытаюсь найти эффективный алгоритм.

У меня есть ограничивающий прямоугольник с заданной шириной, высотой и глубиной.
У меня также есть список сфер. То есть координата центра (x _i , y _i , z _i ) и радиус r _i для каждой сферы.

Сферы гарантированно помещаются в ограничивающую рамку и не перекрывают друг друга.

Итак, моя ситуация такова:

Теперь у меня есть новая сфера с радиусом r, которую я должен уместить внутри ограничительной рамки, не перекрывая ни одну из предыдущих сфер.

У меня также есть целевая точка T = (x, y, z), и моя цель - подогнать эту новую сферу (с учетом условий выше) как можно ближе к этой целевой точке.

Я пытаюсь построить эффективный алгоритм, чтобы найти оптимальное положение для новой сферы. Оптимально как в: максимально близко к целевой точке. Или «ложный» результат, если нет места для этой новой сферы между или вокруг существующих где-либо внутри ограничивающей рамки.

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

Обратите внимание, что существует много известных алгоритмов "упаковки сфер", но они, как правило, просто заполняют объемы случайными сферами. Кроме того, они часто используют метод проб и ошибок, просто делают определенное количество случайных попыток и затем завершают свою работу.

В то время как у меня есть определенный конкретный новый размер сферы, и мне нужно соответствовать этому (или выяснить, чтоэто невозможно).

Answer 1

Возможный подход заключается в вычислении «карты расстояний» сфер, то есть функции, которая возвращает для каждой точки (x, y, z) расстояние до ближайшей сферы, которое также равно расстоянию до ближайшего центра минусрадиус соответствующей сферы. Карта состоит из пересечения (гипер) конических поверхностей.

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

Если я прав, карта расстояний напрямую связана с аддитивно-взвешенной диаграммой Вороного центров сфер (https://en.wikipedia.org/wiki/Weighted_Voronoi_diagram),, а вершины диаграммы соответствуют локальным максимумам. Отсюда самая близкая вершина Вороного со значением, которое превышаетрадиус цели даст решение.

К сожалению, построение этой диаграммы не будет булочкой смеха. Проверьте статью «Евклидова диаграмма Вороного трехмерных шаров и ее вычисление по кривым краям» и ее библиографию.

---

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

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

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

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

Ключевым моментом в этом процессе является быстрый поиск сфер, ближайших к данному кубу, для начальных оценок,Может быть полезна структура данных, такая как kD-дерево или подобное.