Наименьшая сфера для инкапсуляции треугольника в 3D?

Question

Сначала я решил, что вы суммируете вершины и масштабируете на 1/3, чтобы найти начало координат, а затем берете наибольшее расстояние от вершины до начала координат.Это приводит к сфере, которая содержит треугольник, но это не обязательно самый маленький.

Известен ли метод определения наименьшей сферы для полной инкапсуляции произвольного треугольника в 3D?

Answer 1

Использовал здесь ответы и википедию, чтобы придумать что-то на с ++, которое работает для меня, надеюсь, это кому-нибудь поможет!

  static Sphere makeMinimumBoundingSphere(const Vec3 &p1, const Vec3 &p2, const Vec3 &p3) {
     Sphere s;
     // Calculate relative distances
     float A = (p1 - p2).distance();
     float B = (p2 - p3).distance();
     float C = (p3 - p1).distance();

     // Re-orient triangle (make A longest side)
     const Vec3 *a = &p3, *b = &p1, *c = &p2;
     if (B < C) swap(B, C), swap(b, c); 
     if (A < B) swap(A, B), swap(a, b); 

     // If obtuse, just use longest diameter, otherwise circumscribe
     if ((B*B) + (C*C) <= (A*A)) {
        s.radius = A / 2.f;
        s.position = (*b + *c) / 2.f;
     } else {
        // http://en.wikipedia.org/wiki/Circumscribed_circle
        precision cos_a = (B*B + C*C - A*A) / (B*C*2);
        s.radius = A / (sqrt(1 - cos_a*cos_a)*2.f);
        Vec3 alpha = *a - *c, beta = *b - *c;
        s.position = (beta * alpha.dot(alpha) - alpha * beta.dot(beta)).cross(alpha.cross(beta)) /
         (alpha.cross(beta).dot(alpha.cross(beta)) * 2.f) + *c;
     }
     return s;
  }

Answer 2

Самая маленькая сфера для инкапсуляции треугольника - это просто округленная окружность , расширенная в третье измерение.

Обновление: Поцарапайтеконечно нет.Это сфера, которую вы получаете, если вращать наименьший круг вокруг его диаметра.Причина в том, что для любой содержащей сферы, которая имеет свое происхождение из плоскости треугольника, существует меньшая, которая имеет свое происхождение на плоскости (проецируя начало координат ортогонально на плоскость).

Answer 3

Вы пытаетесь найти наименьший вмещающий шар MB (P) из набора точек P , чтобы вы могли использовать алгоритм, реализованный здесь https://github.com/hbf/miniball. (Примечание: "ball" и «сфера» в данном контексте является синонимом.)

Однако в вашем случае это излишне, поскольку в наборе точек P под рукой находится ровно 3 точки (вершины треугольника). В этом конкретном случае вы можете использовать тот факт, что наименьший вмещающий шар MB (P) из P = {p, q, r} равен либо:

• B (p, q) , если r содержится в B (p, q) или
• B (p, r) , если q содержится в B (p, r) или
• B (q, r) , если p содержится в B (q, r) или
• B (p, q, r) в противном случае.

Здесь B (x, y) - наименьший шар, содержащий точки x, y и B (x, y, z) - это маленький шарик, содержащий точки x, y, z на границе. B (x, y) и B (x, y, z) могут быть вычислены путем решения линейной системы уравнений.

Примечание: Я автор https://github.com/hbf/miniball.

Answer 4

Предполагая, что сфера является просто тривиальным продолжением круга (2-D) в 3-D (используя и ту же центральную точку и тот же радиус), Я считаю, что то, что вы ищете, называется описанный круг треугольника .

Очевидно, я не рассматривал случай тупого треугольника , который, если у вас есть вершины (точки) треугольника на круге, то круг равен , а не наименьший ограничивающий круг (и, следовательно, наименьшая ограничивающая сфера).

Теперь я считаю, что вы ищете минимальную ограничивающую сферу, , которая является известной и изученной проблемой в математике , и компьютерную графику . «Задача наименьшего окружающего круга» - это описание алгоритмов O (n ^ {2}) и линейного O (n) .

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