在三维中封装三角形的最小球体

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

Answer 2

封装三角形的最小球体只是扩展到第三维度的外切圆

更新：当然不是。如果你绕着它的直径旋转一个最小的圆，就会得到一个球体。原因是，对于任何原点在三角形平面外的包含球体，都有一个较小的球体原点在平面上（通过将原点正交投影到平面上）。

Answer 3

您正试图找到点集p的最小封闭球MB（p），因此您可以使用此处实现的算法https://github.com/hbf/miniball.（注意："ball"one_answers"sphere"在本文中是同义词。）

然而，在您的情况下，这太过分了，因为手头的点集p正好包含3个点（三角形的顶点）。在这种特殊情况下，您可以使用以下事实：P={P，q，r}的最小封闭球MB（P）等于：

• B（p，q）如果r包含在B（p、q）中，或
• 如果q包含在B（p，r）中
• 如果p包含在B（q，r）中
• B（p，q，r）否则

这里，B（x，y）是包含点x，y的最小球，B（x、y、z），y，zB（x，y）和B（x、y，z）

注意：我是https://github.com/hbf/miniball.

Answer 4

假设球体只是圆（2-D）到3-D的平凡扩展（使用相同的中心点和相同的半径），我相信你正在寻找的是三角形的外切圆

显然，我没有考虑钝角三角形的情况，如果三角形的顶点（点）在圆上，那么圆是而不是最小的边界圆（因此是最小的边界球）。

现在我相信你正在寻找最小边界球，这是数学和计算机图形学中一个已知和研究的问题。"最小包围圈问题"是对O（n^｛2｝）和线性O（n）

据我所知，最小边界圆确实产生了最小边界球体，使用投影到三维中的相同参数（中心点和半径）。