Минимальная охватывающая сфера - производная от OBB? - PullRequest
1 голос
/ 21 марта 2012

Мне нужно вычислить минимальную охватывающую сферу из набора точек в 3D, которая уже заключена в ориентированную ограничивающую рамку (OBB).

Верно ли мое предположение, что сфера может быть получена изOBB следующим образом?

sphere_radius = 0.5 * obb_diagonal
sphere_center = obb_center

Если нет,

  • почему?
  • может ли вообще использоваться OBB?

1 Ответ

2 голосов
/ 21 марта 2012

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

В качестве контрпримера рассмотрим кубическую ограничивающую рамку от (-1,-1,-1) до (1,1,1), содержащую шесть точек в центре граней куба: (1,0,0), (-1,0,0), (0,1,0), (0,-1,0), (0,0,1), (0,0,-1).

Минимальная ограничивающая сфера для этого набора точек будет шаром радиуса 1 с центром в (0,0,0). Шар, построенный по предложенному вами алгоритму, будет шаром радиуса 1.7 (ish) с центром в начале координат.

Вместо этого вы захотите использовать алгоритм, чтобы найти минимальную ограничивающую сферу. Существуют алгоритмы, позволяющие делать это за линейное время (см. в этом вопросе , чтобы узнать, где искать. Miniball - это хорошее ключевое слово для поиска.)

...