Учитывая набор точек, как мне аппроксимировать большую ось его формы?

Question

Учитывая "форму", нарисованную пользователем, я хотел бы "нормализовать" ее, чтобы они все имели одинаковый размер и ориентацию. То, что у нас есть, это набор баллов. Я могу приблизить размер, используя ограничивающую рамку или круг, но ориентация немного сложнее.

Думаю, правильный способ сделать это - вычислить майорас его ограничивающего эллипса . Для этого вам нужно вычислить собственный вектор ковариационной матрицы . Вероятно, это будет слишком сложно для моей потребности, так как я ищу достаточно хорошую оценку. Выбор минимальных, максимальных и 20 случайных точек может стать началом. Есть ли простой способ приблизить это?

Редактировать : Я нашел Степенной метод для итеративно приближенного собственного вектора. Статья в Википедии . Пока мне нравится Ответ Дэвида .

Answer 1

Вы бы вычисляли собственные векторы матрицы 2х2, что можно сделать с помощью нескольких простых формул, так что это не так сложно. В псевдокоде:

// sums are over all points
b = -(sum(x * x) - sum(y * y)) / (2 * sum(x * y))
evec1_x = b + sqrt(b ** 2 + 1)
evec1_y = 1
evec2_x = b - sqrt(b ** 2 + 1)
evec2_y = 1

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

Редактировать : Я думаю, что x и y должны быть переведены в среднее значение нуля, то есть вычесть среднее из всех x, y сначала (eed3si9n) .

Answer 2

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

Значение r ^ 2 также даст вам информацию об общей форме. Чем ближе к 0, тем более круглая / равномерная форма (круг / квадрат). Чем ближе к 1, тем больше вытянутая форма (овал / прямоугольник).

Answer 3

Окончательное решение этой проблемы - PCA
Хотел бы я найти милую реализацию для вас, чтобы сослаться на ...