check if four points are on the same plane, only by using distances (verify colinearity)

Question

There is a method called Cayley-Menger determinant in order to find if 3 points are collinear, 4 points are coplanar etc. provided that all the pairwise distances are given.

However, in 2-D, there is a much simple way to determine if 3 points, {A,B,C} are collinear: Triangle inequality!

!(|AB| + |AC| = |BC|) AND !(|AB| + |BC| = |AC|) AND !(|AC| + |BC| = |AB|) IFF A, B, C are not collinear

Is there a similar approach in 3-D?

Answer 1

Yes, there is similar formula for three dimensions.

---

Solution 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 formula states that the area A of the triangle with vertices a, b, c is

where s = 0.5( a + b + c). Thus you can compute each area from your distances and test if condition holds.

---

Solution 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.

A Heron formula gives a volume of the tetrahedron in terms of its edges, so you can test this based only on distances. Here is a brief derivation of the formula.

A triangular equality can be seen just a special case of Heron formula for computing a content of a n - dimensional simplex from it's n + 1 vertices. The content of a n-dimensional simplex is 1/n! times the “heights” of the vertices (taken in any linear sequence) above the sub-space containing the previous vertices. Imagine how you multiply a basis of a triangle by it's height ( and with 1/2) to get an area of triangle, then multiply this area by height (and 1/3) of a tetrahedron to get it's volume, and so on.

Note that any vertex of a simplex in k-dimensional space can be regarded as the apex of a “pyramid” on a (k-1)-dimensional base defined by the other vertices. Letting Vk-1 denote the content of the base, and h the perpendicular distance of the apex from the sub-space containing the base, the content Vk of the pyramid is given by

Therefore, applying this formula to the vertices (in any order) recursively, beginning with k = n, we have

where h1 is simply the distance between the first two vertices, h2 is the height of the third vertex above the line containing those two vertices, h3 is the height of the fourth vertex above the plane containing the first three vertices, and so on. Thus the content of a n-dimensional simplex is 1/n! times the “heights” of the vertices (taken in any linear sequence) above the sub-space containing the previous vertices.

In general we can apply an n-dimensional rotation that places n-1 of the vertices into a sub-space orthogonal to one of the axes.

This leads us to Cayley-Menger determinant, for the area of a triangle in terms of the edge lengths

which gives a Heron formula for the area of a triangle in terms of the edge lengths

A Heron formula for the volume of a tetrahedron

If U, V, W, u, v, w are lengths of edges of the tetrahedron (first three form a triangle; u opposite to U and so on), then

where:

If one of the points is located on a plane defined by three other points, Volume is 0, so one of the factors in numerator is 0 and this is condition you can test.

Heron's Formula and Brahmagupta's Generalization

Tetrahedron

---

I have written the function heron_3d in C++. This function returns boolean value indicating if 4 points belong to the same plane or not, using the approach described in Solution 1: comparing each face of the tetrahedron against the sum of 3 other faces using the Heron formula to calculate each area.

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

usage:

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