Нахождение минимальной ограничивающей сферы для усеченного конуса

Question

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

Это похоже на простую геометрию, но я не могу понять это. Есть идеи?

Answer 1

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

Answer 2

Ну, есть, конечно, http://www.cgafaq.info/wiki/Minimal_enclosing_sphere (через Google).

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

Разобраться в первой сфере. Если усеченный вписывается в это, это ваш ответ. Иначе вторая сфера будет вашим ответом.

Answer 3

Существует несколько алгоритмов и реализаций для этой проблемы (см. Также этот пост).

• Для 2D и 3D реализация Gärtner, вероятно, самая быстрая.

• Для более высоких измерений (скажем, до 10000) взгляните на https://github.com/hbf/miniball, в котором реализованы алгоритмы Гертнера, Кутца и Фишера (примечание: я один из -авторы).

• Для очень, очень больших размеров алгоритмы набора (аппроксимации) ядра будут быстрее.

В вашем конкретном приложении вы можете попробовать любой из первых двух алгоритмов. Оба бегут в O(n) с очень маленькой постоянной и численно устойчивы.

Answer 4

Ну давай решать математикой.

Используя правую Y систему координат вверх (вперед - ось –Z), для усеченного конуса с шириной области просмотра w, высотой h, вблизи плоскости n, дальней плоскости f, угла поля зрения оси X fov, то минимальная ограничивающая сфера равна

k = sqrt(1+(h/w)^2) * tan⁡(fov/2)

if( k^2 >= (f-n)/(f+n) )
{
    C = (0, 0, -f)
    R = f*k
}
else
{
    C = (0, 0, -0.5 * (f+n) * (1+k^2))
    R = 0.5 * sqrt( (f-n)^2 + 2*(f^2+n^2)*k^2 + (f+n)^2*k^4 )
}

C - центр сферы в пространстве зрения, а R - радиус.

Я помещаю детали в свой блог, если вы заинтересованы: https://lxjk.github.io/2017/04/15/Calculate-Minimal-Bounding-Sphere-of-Frustum.html

Answer 5

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

Answer 6

Вам нужно найти точку на "вертикальной" линии вниз по центру усеченного конуса, где расстояние до ребра снизу и верху усеченного конуса (при условии, что оно симметрично) одинаково.

решите так, чтобы точка внизу была Xb, Yb, Zb, точка сверху - Xt, Yt, Zt, а линия - точка Xp, Yp, Zp плюс вектор Ax, By, Cz.

так что решите уравнение

sqrt( (Xb - (Xp + VAx) )^2 + (Yb - (Yp + VBy))^2 + (Zb - (Zp + VCy))^2) = 
sqrt( (Xt - (Xp + VAx) )^2 + (Yt - (Yp + VBy))^2 + (Zt - (Zp + VCy))^2).

Единственной переменной там является скаляр V.

Answer 7

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

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

Answer 8

Строго говоря, (в соответствии с этим) основание усеченного конуса может быть любым многоугольником, и, строго говоря, этот многоугольник даже не должен быть выпуклым. Тем не менее, чтобы получить общее решение проблемы, я думаю, что вам может понадобиться (почти) использовать все вершины, как предложено выше. Однако могут быть особые случаи, решение которых (как предложено выше) может потребовать сравнения только нескольких сфер. Мне нравится ссылка Энтони выше: Мегиддо обеспечивает преобразование, которое, как он утверждает, дает решение за O(n) (!) Времени. Неплохо!