仅通过距离检查四个点是否在同一平面上（验证共线性）

Question

仅通过距离检查四个点是否在同一平面上（验证共线性）

c++algorithmmathgeometrylinear-algebra

8

有一种方法叫做Cayley-Menger determinant，可以通过给出所有点对之间的距离来判断3个点是否共线，4个点是否共面等。

然而，在二维空间中，判断三个点 {A,B,C} 是否共线有一个更简单的方法：三角形不等式！

!(|AB| + |AC| = |BC|) AND !(|AB| + |BC| = |AC|) AND !(|AC| + |BC| = |AB|) IFF A, B, C 不共线

在三维空间中是否有类似的方法呢？

- padawan

不清楚你的问题是什么。 “我需要一个不使用坐标的解决方案[...]我不知道任何坐标或平面/线方程。”那么，Cayley-Menger行列式有什么问题吗？没有比它更简单的解决方案了。 2D只是一个极其特殊的情况，您可以以更简单的方式完成它。 - Ali

那么，为什么2D如此特别？3D有什么问题吗？我应该怎么做才能将同样的规则应用于3D呢？ - padawan

这个问题似乎不适合讨论，因为它涉及到数学。 - Ali

3D、4D和其他的都没有问题。 - 4pie0

@cagirici，关于这个话题，我还能为您做些什么吗？ - 4pie0

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- 4pie0 · Accepted Answer

是的，三维空间也有类似的公式。

解决方案1

如果且仅当你可以构成的四个三角形中有一个的面积等于其他三个的和（或者和/差，例如P1=P2+P3-P4），则这四个点在同一平面上。

海伦公式说明了由顶点a，b，c组成的三角形的面积A为：

enter image description here

s = 0.5( a + b + c)，因此您可以根据距离计算每个区域，并测试条件是否成立。

解决方案2

当且仅当由这四个点组成的四面体的体积为0时，这四个点在同一平面上。

海伦公式给出了四面体的体积与其边长的关系，因此您可以仅基于距离测试这一条件。以下是该公式的简要推导。

三角不等式可以被视为从它的n + 1个顶点计算n维单形体积的海伦公式的特殊情况。 n 维单形体的体积是所有顶点（以任意线性顺序取出）相对于包含前一个顶点的子空间的“高度”的1/n!倍数。想象一下如何将三角形的基础乘以其高度（及1/2），以获得三角形的面积，然后将该面积乘以四面体的高度（及1/3）以获得其体积，以此类推。

请注意，k 维空间中单体的任何顶点都可以被视为由其他顶点定义的 (k-1) 维基底上的“金字塔”顶点。设 Vk-1 为底的内容，h 为顶点到包含底的子空间的垂直距离，则金字塔的内容 Vk 为

enter image description here

因此，将此公式递归地应用于顶点（以任意顺序），从k = n开始，我们有

enter image description here

其中，h1 简单地表示前两个顶点之间的距离，h2 是第三个顶点在包含这两个顶点的直线上方的高度，h3 是第四个顶点在包含前三个顶点的平面上方的高度，等等。因此，n维单纯形的内容是 1 / n! 乘以顶点（按任意线性顺序取）在前一个顶点所在子空间上方的“高度”。

一般而言，我们可以应用一个n维旋转，将n-1个顶点放入垂直于其中一个轴的子空间中。

这引出了Cayley-Menger行列式，以边长表示三角形的面积。

enter image description here

这个公式是海伦(Heron)公式，用三角形的边长表示三角形面积

enter image description here

一个用于计算四面体体积的海龙公式

如果U，V，W，u，v，w是四面体边长的长度（前三个形成一个三角形; u与 U 相对等，依此类推），则

enter image description here

在哪里：

enter image description here

如果四个点中有一个点位于由另外三个点定义的平面上，则体积为0，因此分子中的一个因子为0，这是您可以测试的条件。海伦公式和婆罗摩定理的推广四面体

我已经用C++写好了heron_3d函数。该函数使用Solution 1中描述的方法，通过使用Heron公式计算每个面积来将四个点归属于同一平面或不在同一平面，并返回一个boolean值。具体做法是将四面体的每个面与另外三个面的和进行比较。

#include <cmath>
/**
 * @return area of triangle based on Heron formula
 */
double areaOfTriangle( double edge1, double edge2, double edge3) {
    double s = 0.5 * ( edge1 + edge2 + edge3);
    return std::sqrt( s * ( s - edge1) * ( s - edge2) * ( s - edge3));
}
/**
 * U, V, W, u, v, w are lengths of edges of the tetrahedron, as in 
 * http://en.wikipedia.org/wiki/Tetrahedron
 * @param U basis edge 1
 * @param V basis edge 2
 * @param W basis edge 3
 * @param u opposite to U
 * @param v opposite to V
 * @param w opposite to W
 * @return 
 */
bool heron_3d( double U, double V, double W,
               double u, double v, double w) {
    double areas[] = { areaOfTriangle( U, V, W),
                       areaOfTriangle( U, v, w),
                       areaOfTriangle( V, u, w),
                       areaOfTriangle( W, u, v)};
    for ( int i = 0; i < 4; ++i) {
        double area = areas[ i];
        double sum = 0;
        for ( int j = 1; j < 4; ++j) {
            sum += areas[ (i + j) % 4];
        }
        if ( area == sum) return true;
    }
    return false;
}

使用方法：

int main(int argc, char** argv) {

    bool b0 = heron_3d( 3, 3, 0, 5, 5, 4);  // true
    bool b1 = heron_3d( 3, 3.1, 0.1, 5.1, 5, 4); // false
    bool b2 = heron_3d( 3, 5, 2, std::sqrt( 16 + 25), 5, 4); // true
    return 0;
}