c++ - 检查四个点是否在同一平面上，仅使用距离(验证共线性)

Question

有一个方法叫Cayley-Menger determinant为了找出 3 个点是否共线，4 个点是否共面等。前提是所有成对距离都已给出。

但是，在二维中，有一种非常简单的方法可以确定 3 个点 {A,B,C} 是否共线:三角不等式!

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

在 3-D 中是否有类似的方法？

Answer 1

是的，三个维度也有类似的公式。

---

方案一

The four points are in the same plane if and only if one of the areas of the four triangles you can make has an area equal to the sum (or sum/difference, e.g. P1=P2+P3-P4) of the other three areas.

Heron 公式指出顶点a、b、c 的三角形的面积A 是

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

---

解决方案2

The four points are in the same plane if and only if the volume of the tetrahedron comprised from these four points is 0.

Heron 公式根据边给出了四面体的体积，因此您可以仅根据距离对其进行测试。这里简单推导一下公式。

三角等式可以看作是 Heron 公式的一个特例，用于计算 n - 维度单纯形的内容，它是 n + 1顶点。 n 维单纯形的内容是 1/n! 包含前一个子空间之上的顶点(以任何线性序列获取)的“高度”的倍数顶点。想象一下如何将三角形的底乘以它的高度(以及 1/2)以获得三角形的面积，然后将该面积乘以高度(以及 1/3>) 四面体的体积，等等。

注意k维空间中单纯形的任意顶点都可以看作是(k-1)维底上“金字塔”的顶点由其他顶点定义。令Vk-1表示基的内容，h顶点到包含基的子空间的垂直距离，内容Vk 的金字塔是由

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

其中 h1 只是前两个顶点之间的距离，h2 是包含这两个顶点的直线上方的第三个顶点的高度，h3 是包含前三个顶点的平面上方第四个顶点的高度，依此类推。因此，n 维单纯形的内容是 1/n! 乘以包含以前的顶点。

一般来说，我们可以应用 n 维旋转，将 n-1 顶点放入与轴之一正交的子空间中。

这导致我们得到 Cayley-Menger 行列式，用于三角形面积的边长

根据边长给出三角形面积的 Heron 公式

四面体体积的 Heron 公式

如果U, V, W, u, v, < strong>w 为四面体的边长(前三者构成三角形；u 与U 等相对)，则

哪里:

如果其中一个点位于由其他三个点定义的平面上，则体积为 0，因此分子中的一个因子为 0，这是您可以测试的条件。

Heron's Formula and Brahmagupta's Generalization

Tetrahedron

---

我用 C++ 编写了函数 heron_3d。此函数返回 boolean 值，指示 4 个点是否属于同一平面，使用解决方案 1 中描述的方法:将四面体的每个面与 3 的总和进行比较其他人脸使用 Heron 公式计算每个区域。

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