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

如果给定所有成对的距离，则有一种称为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中是否有类似的方法？

最佳答案

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

解决方案1

Heron公式指出，具有顶点 a ， b ， c 的三角形的面积 A 为

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

解决方案2

苍鹭公式根据其边缘给出了四面体的体积，因此您只能基于距离进行测试。这是该公式的简要推导。

可以看到三角等式只是 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公式

如果 U ， V ， W ， u ， v ， w 是四面体的边长(与三角形U_ _ _ _ _ _ _ _ _ _) ，然后

在哪里:

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

Heron's Formula and Brahmagupta's Generalization

Tetrahedron

我已经在 C++ 中编写了函数heron_3d。此函数使用解决方案1 中描述的方法，返回boolean值，指示4个点是否属于同一平面。

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

关于c++ - 仅通过使用距离来检查四个点是否在同一平面上(验证共线性)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22426748/