У меня есть куб с 8 переменными углами. У меня также есть набор данных вокселей, все измерения которого имеют одинаковый размер набора.
Кто-нибудь знает алгоритм, чтобы найти наименьшую возможную площадь (и при этом все 8 угловых позиций) для куба, в то время как куб все еще инкапсулирует все воксели?
Желательно не слишком тяжелый алгоритм.
j_random_hacker уже дал хороший ответ с кубами, выровненными по осям, кубами, выровненными по осям, и сферами. Однако, если вы действительно хотите найти оптимальный параллелепипед, алгоритм значительно усложняется.
Я предполагаю, что у вас есть набор вокселей в сетке. Если ваши воксели представляют собой твердое тело или образуют плотное облако, вы можете создать набор вокселей, представляющих внешнюю оболочку фигуры. Внутренние воксели не важны при создании выпуклой оболочки (будь то сфера или любой выпуклый многогранник).
Один из возможных методов для этого:
Если это звучит странно, подумайте о геометрии. Если вы попытаетесь нарисовать плоскость за пределами твердого тела (или), плоскость никогда не сможет достичь ни одного из средних положений вдоль линии, поэтому никакие точки, находящиеся на линейном сегменте между двумя другими точками, не помогут создать более плотную подгонку. (Это не оптимальный алгоритм в том смысле, что он не оставляет ненужных точек в наборе, но он прост и быстр.)
Если вы хотите создать многогранник, содержащий все точки, вы создаете его из набора плоскостей (6 в случае прямоугольного параллелепипеда). Плоскость довольно проста в том смысле, что для любых оптимальных ограничивающих плоскостей верно следующее:
Расстояние от точки до плоскости вычисляется очень просто (ax+by+cx+d для каждый пункт). Таким образом, поиск ограничивающей плоскости в каждом направлении является относительно быстрой и простой операцией O(n) (где n — количество оставшихся вокселей).
Хуже того, выбрать правильное направление для самолетов непросто. Я не знаю, существует ли для этого оптимальный алгоритм, но я могу думать только о неуклюжих или медленных алгоритмах либо с большим количеством вычислений грубой силы (плоские расстояния во многих направлениях), либо с итеративным угадыванием.
Даже они могут быть полезны, но на самом деле остается вопрос: почему? Могут быть лучшие способы, чем пытаться сделать маленький прямоугольный параллелепипед.
Если вы имеете в виду кубоид — трехмерную фигуру с 6 прямоугольными гранями — и если эти грани должны быть выровнены с осями ваших воксельных данных, то это просто (3D) ограничивающая рамка. Все, что вам нужно сделать, это вычислить минимальное и максимальное значения координат x, y и z каждого вокселя в вашем наборе данных. Взяв все 8 комбинаций {минимум, максимум} для этих 3 измерений, вы получите координаты 8 углов, хотя обычно вы записываете только две точки (min_x, min_y, min_z) и (max_x, max_y, max_z). , которые полностью описывают форму.
Если фигура должна быть кубом (т. е. все измерения равны), вам придется увеличить размер двух меньших измерений до размера наибольшего.
Если вы ищете формы для связывания объемов, которые можно использовать для эффективного тестирования пересечения (с точками, линиями, плоскостями или другими ограничивающими объемами), то еще одним хорошим выбором является сфера. Тест на пересечение двух сфер особенно прост: все, что вам нужно сделать, это проверить, превышает ли расстояние между их центрами сумму их радиусов.
