найти ортонормированный базис для плоского трехмерного (возможно, вырожденного) многоугольника

Question

Учитывая общий плоский трехмерный многоугольник, существует ли общий способ найти ортонормированный базис для этого плоского многоугольника?

Самый простой способ сделать это - предположить, что вы берете первые 3 точки многоугольника и формируете два вектора каждый, и это два ортонормированных базисных вектора, которые мы ищем. Но проблема этого подхода заключается в том, что эти 3 точки могут располагаться на одной и той же линии в многоугольнике, и, следовательно, вместо получения двух ортонормированных векторов мы получаем только один.

Другой подход к нахождению второго ортонормированного вектора состоит в том, чтобы пройти через многоугольник и найти другую точку, которая образует ортонормированный вектор, отличный от первого, но этот подход подвержен численным ошибкам (например, что если второй вектор почти то же самое с первым вектором? Числовые ошибки могут быть значительными).

Есть ли другой лучший подход?

Answer 1

Немного, но одним из способов будет вычисление ковариационной матрицы точек, а затем ее диагонализация.Если точки действительно плоские, то одно из собственных значений ковариационной матрицы будет равно нулю (или, скорее, очень мало, из-за арифметики конечной точности), и соответствующий собственный вектор будет нормалью к плоскости;два других собственных вектора будут охватывать плоскость многоугольника.Если у вас есть N точек, а i-я координата k-й точки равна p [k, i], то средняя (векторная) и (3x3) ковариационная матрицы могут быть вычислены как

m[i] = Sum{ k | p[k,i]}/N (i=1..3)
C[i,j] = Sum{ k | (p[k,i]-m[i])*(p[k,j]-m[j]) }/N (i,j=1..3)

Обратите внимание, что C симметричен, поэтому, чтобы узнать, как его диагонализировать, вам может понадобиться поискать «симметричную проблему собственных значений»

Answer 2

Вы можете использовать перекрестное произведение любых двух линий, соединенных любыми двумя вершинами. Если перекрестное произведение слишком мало, значит, вы находитесь на вырожденной территории.

Вы также можете взять центроид (среднее число точек, которое гарантированно лежит на одной плоскости) и выбрать самое большое из любых двух перекрестных произведений векторов из центроида в любую вершину. Это будет самый точный нормальный. Обратите внимание, что если самый большой перекрестный продукт мал, у вас может быть неточная норма.

Если вы не можете найти какой-либо перекрестный продукт, который не близок к 0, ваш оригинальный поли будет вырожденным, и нормальный будет трудно найти. В этом случае вы можете использовать алгебру произвольной или адаптивной точности, но, конечно, ошибка округления уже значительна в исходных данных, поэтому это может не помочь. Если возможно, сначала удалите вырожденные полики, а если нужно, прошейте сетку обратно:).