检查 3D 点是否位于 3D 柏拉图立体内？

Question

是否有任何已知方法可以快速有效地确定 3D 点是否位于已知大小的柏拉图体积内？

这对于立方体（六面体）或圆（椭圆体）来说似乎很容易。我似乎无法弄清楚四面体、八面体、十二面体或二十面体。我猜可能可以将形状分解成几个子实体，然后检查每个子实体，但如果可能的话，我想避免使用任何类型的迭代求解器。

Answer 1

一种简单的方法是将实体表示为半空间的交集。

3d 中的平面具有隐式方程：

ax + by + cz + d = 0

哪里(a, b, c)是平面法线，d是平面上-(a*x + b*y + c*z)任何点的值（计算值不取决于您选择的点）。

对于平面一侧空间中的点，结果a*x+ b*y + c*z + d将为负，而在另一侧，结果将为正。

柏拉图实体（任何凸实体）可以表示为所有面的非正侧上的空间点，即

a[i]*x + b[i]*y + c[i]*z + d[i] <= 0

因此，一个相当快的测试可能是：

struct Plane {
    double a, b, c, d;
};

struct Point {
    double x, y, z;
};

int side(const Point pt, const Plane& pl) {
    double v = pt.x*pl.a + pt.y*pl.b + pt.z*pl.c + pl.d;
    if (v < -EPS) return -1;
    if (v > EPS) return 1;
    return 0;
}

struct ConvexSolid {
    std::vector<Plane> planes;

    bool contains(const Point& pt) const {
        return std::all_of(planes.begin(), planes.end(),
                           [&](const Plane& pl){
                               return side(pt, pl) <= 0;
                           });
    }
};

此外，如果您知道您的大部分分数都在实体内，那么添加快速接受测试可能是一个好主意。考虑中心和与面的距离......如果您的点位于以中心为中心并具有该半径的球体内部，那么肯定也在实体内部。

因此，如果您预计许多点都在该球体内，那么首先检查它可能是一项不错的投资，因为它只需要检查

 r2 = (x-xc)*(x-xc) + (y-yc)*(y-yc) + (z-zc)*(z-zc)

这应该比检查一架飞机的成本略高。

但是请注意，如果大多数点不在该球体内，那么进行此检查确实是一种悲观。

另一个加速是同时考虑具有相同中心的边界球体……在这种情况下，您只能使用相同的r2计算来进行“带”检查，并且仅当r2 > r2min（即，如果点不在内部球体内部）和如果r2 < r2max（即，如果该点不在外部球体外部）。