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

Question

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

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

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

Answer 1

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

// 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

Конечным решением этой проблемы является запуск СПС
Жаль, что я не могу найти приятную маленькую реализацию, на которую вы могли бы сослаться...