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

Question

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

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

Answer 1

一个简单的方法是将实体表示为semispaces的交集。

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

ax + by + cz + d = 0

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

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

柏拉图立体（任何凸立体）可以表示为 space 中所有面的非正侧的点，即

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计算来做一个"band" 检查，只有在 r2 > r2min（即如果点不在内球内）和 r2 < r2max（即如果点不在外球体之外）。

Answer 2

point in polygon 在查找二维点是否位于任何类型的多边形 (2D space) 的上下文中是一个众所周知的问题。参见例如

How can I determine whether a 2D Point is within a Polygon?。

多面体 (3D) 中的点问题---对于任何一种多面体的情况---有点棘手。但是，在您的情况下，您严格考虑凸多面体，因为所有柏拉图立体都是后一种类型。

在这种情况下，我可以为您指出两种解决此问题的方法。

1 ：（任何凸 多胞形 的一般方法）您可以将您的问题视为查找一个点是否在一组已知点的 convex hull 内，在你的情况下，你的点是你的柏拉图固体的顶点，它们精确地描述了它们自己的凸包（由于凸性，没有 "interior" 顶点）。已经讨论了如何实现这个问题的一般解决方案，例如这里：

Find if a point is inside a convex hull for a set of points without computing the hull itself
一个非常优雅的解决方案是让您的多面体描述一组可行的线性规划 (LP) 问题，并且在附加等式约束 decisionVariable = myPoint（强制包含）的情况下，如果该点位于多面体之外，则您的 LP 将不可行，否则可行（无需求解最优性，仅用于可行性）。

2 : 如上所述，多边形中的二维点已被充分研究，您甚至可以找到它的 C++ 代码 in the SO link I provided above。由于您正在考虑 3D 中的凸多面体，我们知道通过这种多面体切割的 2D 平面的交点将描述一个凸多边形。因此，对于您要研究的每个点，您创建包含该点并与多面体（您的柏拉图立体）相交的平面：然后剩下的问题是解决 “多边形问题中的二维点”。 =41=], 在这架飞机上.

Answer 3

从该点到形状外的某处画一条线，并计算它通过了多少个表面。如果数字是奇数，则该点在内部，否则在外部。

QED

Answer 4

如果您正在寻找优化的算法，您可以尝试检查该点是否位于实体边界球之外，并仅在不位于边界球之外时才检查曲面。

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

Check if a 3D point lies inside a 3D platonic solid?

c++

algorithm

geometry

computational-geometry