AlexanderMasht Jan 18 at 10:03

Алгоритм для аппроксимации плоскости

Easy

6 min

3.7K

Algorithms*Mathematics*

Comments 7

avdx Jan 18 at 10:47

Через SVD это просто делается:

https://www.ltu.se/cms_fs/1.51590!/svd-fitting.pdf

Часть 3: Fitting Planes and Lines by Orthogonal Distance Regression

Akon32 Jan 18 at 12:57

Апроксимацию облака точек плоскостью можно легко сделать методом главных компонент (principal component analysis, PCA), который реализуется нахождением собственных векторов матрицы ковариации координат точек. Один из векторов - нормаль к искомой плоскости. Собственные вектора через SVD можно найти, как указано в комменте выше.

А ещё через PCA можно находить не только плоскости, а и "иглы" или "эллипсоиды", анализируя соотношения собственных чисел матрицы ковариации.

И да, я тоже сначала изобрёл свой метод, аналогичный PCA.

hensew Jan 18 at 15:03

Подскажите, а можно апроксимировать проекцию лежащей капли? Кривая 5-го порядка к сожалению не сходится.

Refridgerator Jan 19 at 05:36

Рациональной функцией можно аппроксимировать всё, что угодно - только не совсем понятно, что у вас на рисунках изображено. Я вижу шайбу и полуокружность на шайбе.

alexejisma Jan 18 at 22:29

Для симметричной матрицы можно найти все собственные значения и собственные векторы без нахождения корней характеристического уравнения

Корни характеристического уравнения и собственные значения это одно и тоже =)

Метод вращений можно реализовать более эффективно. Сперва за одно вращение (!) зануляется элемент a31. Затем с помощью пары итераций значение a32 делается достаточно малым. Можно, кстати, ускорить сходимость используя сдвиги. А затем матрица принимает вид

a11 a12  0
a21 a22  0
 0   0  a33

Один корень равен a33, а остальные можно найти решив квадратное уравнение.

MrLantasire Jan 19 at 08:18

Решал я подобные задачки как раз для ЧПУ МНК. Есть наработки по аппроксимации плоскостью, прямой и окружностью.

Для данного случая предлагаю также посмотреть на варианты использовать D = 1, тогда нормаль получится ненормированная и посмотреть вычисление тензора моментов и инерции облака точек.

Литература, которая мне очень помогла:

Фокс А., Пратт М. Вычислительная геометрия

Рашевский П.К. Риманова геометрия и тензорный анализ

wataru Jan 19 at 15:11

Вообще говоря, нельзя просто так взять и считать производные. Потому что у вас A, B, C - не любые числа, у вас формула расстояния действуeт только если A^2+B^2+C^2=1. Т.е. у вас задача минимизации с ограничением.

Решается она множителями лагранжа. Получите почти такие же 3 линейные уравнения, но с 4-ой переменной $\lambda$ . Ее нужно загнать в коээфициенты с переменными и вы получите СЛАУ вида (M-EL)X = 0. Если система невырождена, то есть единственное решение для A, B, C и оно будет (0, 0, 0). Вот отсюда и вылезает, что det(M-EL) = 0.