algorithm - 封装 3D 三角形的最小球体？

Question

起初我想你将顶点相加并按 1/3 缩放以找到原点，然后取从顶点到原点的最大距离。这会产生一个包含三角形的球体，但它不一定是最小的。

是否有已知的方法来确定最小球体以完全封装 3D 中的任意三角形？

Answer 1

使用这里的答案和维基百科在 c++ 中提出了一些对我有用的东西，我希望这对某人有帮助!

  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;
  }