检查四个点是否在同一平面上，只使用距离（验证共线性） [英] check if four points are on the same plane, only by using distances (verify colinearity)
问题描述
有一种方法叫做
我写了函数 heron_3d 在 C ++ 中。此函数返回 boolean 的值，指示4个点是否属于同一平面，使用解决方案1 中描述的方法：四面体，使用 Heron 公式计算每个面积，从而计算三个面的总和。
#include < cmath>
/ **
* @返回基于Heron公式的三角形面积
* /
double areaOfTriangle（double edge1，double edge2，double edge3）{
double = 0.5 *（edge1 + edge2 + edge3）;
return std :: sqrt（s *（s - edge1）*（s - edge2）*（s - edge3））;
}
/ **
* U，V，W，u，v，w是四面体边缘的长度，如
* http：//en.wikipedia .org / wiki / Tetrahedron
* @param U基准边1
* @param V基准边2
* @param W基准边3
* @param u与U相反
* @param v对V
* @param w对面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;
}
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?
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
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;
}
这篇关于检查四个点是否在同一平面上，只使用距离（验证共线性）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
