Как узнать, находятся ли точки point3D в одной плоскости?

Question

У меня есть набор point3D (X, Y, Z). Мне нужно проверить, являются ли они копланарными с какими-то допусками. Мой способ сделать это заключается в следующем: я преобразую все точки из Глобальной системы координат в локальную, где локальные x, y находятся в одной плоскости плоскости, определенной тремя точками в наборе, а z является нормалью к этой плоскости. И затем, все, что мне нужно сделать, это проверить, все ли точки в наборе имеют приблизительно одинаковые локальные значения z.

Однако сложная часть состоит в том, как выбрать 3 точки для определения базовой плоскости. Если выбран случайным образом, это иногда приводит к тому, что набор точек копланарен, иногда нет. Есть ли у вас какие-либо предложения?

Answer 1

1. нормальный n

   выберите любые 3 точки из вашего набора данных, которые не находятся в одной строке, позвольте назвать их p0,p1,p2.Для повышения точности они должны быть ближе друг к другу.Теперь, чтобы построить нормальный вектор, сделайте следующее:

   n = cross( p1-p0 , p2-p0 ); // perpendicular vector to both operands of cross
   n /= |n|;                   // unit vector
   

2. проверьте все точки

   для любой точки на плоскости, образованной p0,p1,p2altitude компонент (в нормальном направлении) должен быть равен нулю, поэтому для любой точки p:

   |dot( p-p0 , n )|<=1e-10
   

   1e-10 - это просто некоторый нулевой порог из-за потери точности на FPU ... Любая точкане удовлетворяющее условию не принадлежит плоскости ...

Итак, как выбрать 3 точки, образующие треугольник?

1. выберите p0,p1

   выберите p0 как точку с минимальными x,y,z координатами и p1 с максимальными x,y,z координатами.Это гарантирует, что они находятся достаточно далеко.

2. pick p2

   теперь ищут точки и находят так, что |dot( p1-p0, pi-p0 )| минимально.Хотя |pi-p0| не равно нулю и достаточно велико (например, по крайней мере 0.1*|p1-p0|).Это гарантирует, что точки образуют треугольник и не слишком близко к каждому.

Все это выполнимо в O(n), поэтому все еще быстро ...

Answer 2

Вероятно, наиболее распространенным способом сделать это будет анализ главных компонентов: https://en.wikipedia.org/wiki/Principal_component_analysis

Краткое описание:

1. Рассчитать ковариационную матрицу 3x3 входных точек
2. Извлечь наименьший собственный вектор.Это нормальный вектор для плоскости с наименьшей квадратической ошибкой, подходящей для всех ваших точек.