Найти наиболее подходящий 3D-объект

Question

У меня неровный трехмерный объект, и мне нужно вставить в него другую симметричную 3d-форму (конус или цилиндр). Мне нужно вращать и расширять / сжимать симметричную форму, чтобы мы могли найти самый большой подходящий конус / цилиндр в этот грубый объект.

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

Алгоритм также должен иметь оптимальную производительность.

Answer 1

Как насчет бумаги:

ФОЛЛЕРТ, Фрэнк и др. Вычисление самого большого пустого закрепленного цилиндра и связанные с этим проблемы. Международный журнал вычислительной геометрии и приложений, 1997, 7.06: 563-580.

Аннотация говорит:

Пусть S - множество из n точек в ℝd, и пусть каждая точка p из S имеет положительный вес w(p). Рассмотрим задачу вычисления луча R, исходящего из начала координат (соответственно, линии l через начало координат), такого, что minp∈S w(p) · d(p, R) (соответственно minp∈S w(p) · d(p, l)) максимально. Если все веса равны единице, это соответствует вычислению бункера, исходящего из начала координат (соответственно, цилиндра, ось которого содержит начало координат), который не содержит никакой точки S и радиус которого максимален. При d=2 мы покажем, как решить эти задачи за время O(n log n), что является оптимальным в модели дерева алгебраических вычислений. Для d=3 мы даем алгоритмы, которые основаны на методике параметрического поиска и выполняются за O(n log5 n) времени. Предыдущие наиболее известные алгоритмы для этих трехмерных задач имели почти квадратичное время выполнения. В заключительной части статьи мы рассмотрим некоторые связанные проблемы.

PDF здесь.