Определение принадлежности точек одной плоскости по расстояниям между ними

#алгоритм #геометрия

Имеем 4 точки в пространстве. Известны расстояния между каждой парой из этих точек.

Как определить принадлежат ли эти 4 точки одной плоскости?

Есть ли аналогичный алгоритм для любого количества точек?
    

Ответы

Ответ 1

Все четыре точки (A, B, C и D) будут лежать в одной плоскости тогда и только тогда,
когда объем тетраэдра с вершинами в этих четырех точках будет равен 0. Так что все,
что нам нужно - это уметь вычислять объем тетраэдра по длинам его сторон. 

Это можно сделать через определитель Кэли-Менгера 

           | 0     1        1        1        1    |
           | 1     0     d2(A,B)  d2(A,C)  d2(A,D) |
V = sqrt ( | 1  d2(A,B)     0     d2(B,C)  d2(B,D) | / 288 )
           | 1  d2(A,C)  d2(B,C)     0     d2(C,D) |
           | 1  d2(A,D)  d2(B,D)  d2(C,D)     0    |


где d2(A, B) - квадраты соответствующих длин сторон.

Это фактически трехмерная версия известной формулы Герона для площади треугольника.



В качестве более "осязаемого"/"конструктивного" решения задачи можно предложить рассмотреть
треугольники ABC и ABD. Если эти треугольники лежат в одной плоскости, то расстояние
CD может равняться только одному из двух значений: одно значение расстояния для ситуации,
когда С и D лежат по одну сторону от AB, другое - когда С и D лежат по разные стороны
от AB.

Не составит труда построить треугольники ABC и ABD на плоскости (например, положив
точку A в начало координат, а точку B на ось абсцисс), вычислить конкретные координаты
точек C и D и узнать искомые расстояния для планарного случая. После этого остается
лишь сравнить найденные расстояния с данным в условии расстоянием CD.



Вопрос о большем количестве точек не совсем понятен. Речь идет об N точек в N-1-мерном
пространстве? Или речь идет об N точек в трехмерном пространстве? В последнем случае
задача сводится просто к применению одного из вышеприведенных решений к четверкам точек
среди данных N. Лучше всего, наверное, действовать иерархически: проверить на планарность
независимые четверки, а затем уже проверять планарность между четверками.