Dado un conjunto de puntos, ¿cómo aproximar el eje principal de su forma?

Question

Dada una "forma" dibujado por el usuario, me gustaría "normalizar" de modo que todos tienen tamaño y la orientación similar. Lo que tenemos es un conjunto de puntos. I puede aproximar el tamaño utilizando cuadro delimitador o círculo, pero la orientación es un poco más complejo.

La forma correcta de hacerlo, creo, es calcular el majoraxis de su de delimitación elipse . Para ello es necesario calcular el vector propio de la covarianza matriz . Si lo hace, probablemente será demasiado complicado para mi necesidad, ya que estoy en busca de alguna estimación suficientemente buena. Recogiendo min, max, y 20 puntos al azar podría ser algún motor de arranque. ¿Hay una manera fácil de aproximarse a esto?

Editar : He encontrado Poder método de forma iterativa vector propio aproximada. artículo de Wikipedia . Hasta ahora estoy gustando de David respuesta.

Answer 1

Usted sería el cálculo de los vectores propios de una matriz de 2x2, que puede hacerse con algunas fórmulas sencillas, por lo que no es tan complicado. En 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

Incluso se puede hacer esto mediante la suma de sólo algunos de los puntos para obtener una estimación, si usted espera que su subconjunto elegido de puntos sería representativo del conjunto completo.

Editar :. Creo que x e y deben ser traducidos a media cero, es decir, restar significar de todas las x, y primero (eed3si9n)

Answer 2

He aquí un pensamiento ... Lo que si ha realizado una regresión lineal de los puntos y utilizó la pendiente de la línea resultante? Si no todos los puntos, al menos una muestra de ellos.

El r ^ 2 valor sería también le dará información sobre la forma general. Cuanto más cerca de 0, más circular / uniforme la forma es (círculo / cuadrado). Cuanto más cerca de 1, el más extendido con la forma es (oval / rectángulo).

Answer 3

La solución definitiva a este problema se está ejecutando PCA
Me gustaría poder encontrar una pequeña aplicación para hacer referencia a ...