Как узнать, находится ли набор point3D в одной плоскости?
У меня есть набор point3D (X, Y, Z). Мне нужно проверить, копланарны ли они с какими-то допусками. Мой способ сделать это так: я конвертирую все точки из глобальной системы координат в локальную, где локальные x, y находятся в одной плоскости с плоскостью, определяемой тремя точками в наборе, а z перпендикулярно этой плоскости. И затем все, что мне нужно сделать, это проверить, все ли точки в наборе имеют примерно одинаковые локальные значения z.
Однако сложность состоит в том, как выбрать 3 точки для определения базовой плоскости. При случайном выборе это может привести к тому, что иногда набор точек компланарен, а иногда - нет. У вас есть какие-либо предложения?
Ответы 2
Вероятно, наиболее распространенный способ сделать это - с помощью анализа главных компонентов: https://en.wikipedia.org/wiki/Principal_component_analysis
Краткое описание:
- Вычислить ковариационную матрицу 3x3 входных точек
- Извлеките наименьший собственный вектор. Это нормальный вектор для плоскости, которая соответствует наименьшей квадрату ошибки для всех ваших точек.
нормальный
nвыберите любые 3 точки из вашего набора данных, которые не находятся в одной строке, позвольте называть их
p0,p1,p2. Для повышения точности они должны быть удалены друг от друга. Теперь, чтобы построить нормальный вектор, сделайте следующее:n = cross( p1-p0 , p2-p0 ); // perpendicular vector to both operands of cross n /= |n|; // unit vectorпроверить все точки
для любой точки на плоскости, образованной
p0,p1,p2, компонентaltitude(в нормальном направлении) должен быть равен нулю, поэтому для любой точкиp:|dot( p-p0 , n )|<=1e-101e-10- это просто какой-то нулевой порог из-за потери точности на FPU ... Любая точка, не удовлетворяющая условию, не принадлежит плоскости ...
Итак, как выбрать 3 точки, образующие треугольник?
выбрать
p0,p1выберите
p0как точку с минимальными координатамиx,y,zиp1с максимальными координатамиx,y,z. Это гарантирует, что они достаточно далеко.выбрать
p2теперь ищите точки и найдите такое, что
|dot( p1-p0, pi-p0 )|минимален. При этом|pi-p0|не нулевой и достаточно большой (например0.1*|p1-p0|хотя бы). Это гарантирует, что точки образуют треугольник и не находятся слишком близко друг к другу.
Все это можно сделать в O(n), так что все еще быстро ...
@ N.T.C Да, ты прав, извини, я забыл отправить вторую часть ответа ... глупый я :)
Разве это не то же самое, что я описал в своем вопросе? Проблема здесь в том, какой критерий использовать для выбора p1, p2 и p3. Это довольно сложно, поскольку, например, если все точки копланарны, кроме точки p3, то выбор может привести к неверным результатам.