12

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

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

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

1 ответ 1

14

Все четыре точки (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. Лучше всего, наверное, действовать иерархически: проверить на планарность независимые четверки, а затем уже проверять планарность между четверками.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.