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

Question

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

• Для 2D и 3D, Реализация Гертнера , вероятно, самый быстрый.

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

• Для очень и очень больших размеров алгоритмы core-set (приближение)Быстрее.

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

Answer 4

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

Answer 5

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

Используя правую 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 6

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

Answer 7

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

решить так, чтобы точка внизу была 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 8

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

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