Dado um conjunto de pontos, como faço para aproximar o eixo principal de sua forma?

Question

Dada uma "forma" tirada pelo usuário, eu gostaria de "normalizar"-lo para todos eles têm tamanho e orientação similar. O que temos é um conjunto de pontos. I pode aproximar o tamanho usando a caixa ou círculo delimitadora, mas a orientação é um pouco mais complicado.

O caminho certo para fazê-lo, penso eu, é calcular o majoraxis de seu delimitadora elipse . Para fazer isso você precisa calcular o eigenvector do covariância matriz . Se o fizer, provavelmente vai ser muito complicado para a minha necessidade, desde que eu estou procurando alguma boa-suficiente estimativa. Escolher min, max, e 20 pontos aleatórios poderia ser algum arranque. Existe uma maneira fácil de aproximar esta?

Editar : Eu encontrei Poder método para eigenvector iteratively aproximada. Wikipedia artigo . Até agora eu estou gostando David resposta .

Answer 1

Você seria calcular os próprios de uma matriz 2x2, o que pode ser feito com algumas fórmulas simples, por isso não é tão complicado. Em pseudocódigo:

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

Você pode até mesmo fazer isso pela soma somente sobre alguns dos pontos para obter uma estimativa, se você espera que o seu subconjunto escolhido de pontos seria representativo do conjunto completo.

Editar :. Eu acho que x e y devem ser traduzidos para zero-média, ou seja, subtrair significa de todo x, y primeira (eed3si9n)

Answer 2

Aqui está um pensamento ... E se você executou uma regressão linear sobre os pontos e usado a inclinação da linha resultante? Se nem todos os pontos, pelo menos, uma amostra deles.

O valor r ^ 2 também dar-lhe informações sobre a forma geral. Quanto mais próximo de 0, o mais uniforme circular / a forma é (círculo / quadrado). Quanto mais próximo de 1, a mais estendido a forma é (oval / rectângulo).

Answer 3

A solução definitiva para este problema está sendo executado PCA
Eu gostaria de poder encontrar um pouco de implementação de bom para você para se referir a ...