Dato un insieme di punti, come faccio approssimare l'asse maggiore della sua forma?

Question

Data una "forma" disegnata dall'utente, desidero "normalizzare" così tutti hanno dimensione e orientamento simili. Quello che abbiamo è un insieme di punti. Posso approssimare le dimensioni utilizzando rettangolo o un cerchio, ma l'orientamento è un po 'più complicato.

Il modo giusto per farlo, credo, è quello di calcolare il majoraxis della sua delimitazione dell'ellisse . Per fare questo è necessario calcolare il autovettore della matrice di covarianza . In questo modo probabilmente sarà troppo complicato per il mio bisogno, dal momento che sono alla ricerca di qualche buona-sufficiente stima. Picking min, max, e 20 punti casuali potrebbe essere un po 'avviamento. C'è un modo semplice per approssimare questo?

Modifica : Ho trovato Potenza metodo iterativo per autovettore approssimativa. Wikipedia articolo . Finora mi sto piacendo di David risposta .

Answer 1

Si sarebbe calcolando gli autovettori di una matrice 2x2, che può essere fatto con un paio di formule semplici, quindi non è così complicato. In pseudocodice:

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

Si potrebbe anche fare questo sommando più di solo alcuni dei punti per ottenere una stima, se ci si aspetta che il sottoinsieme scelto di punti sarebbe rappresentativo del set completo.

Modifica :. Credo x ed y devono essere tradotti a media zero, cioè sottrarre dire da tutti x, y prima (eed3si9n)

Answer 2

Ecco un pensiero ... Che cosa succede se è stata eseguita una regressione lineare sui punti e utilizzato il coefficiente angolare della retta risultante? Se non tutti i punti, almeno un campione di loro.

Il valore ^ r 2 sarebbe anche fornire informazioni circa la forma generale. Il più vicino a 0, il più circolare / uniforme la forma è (cerchio / quadrato). Il più vicino a 1, più stesa la forma è (ovale / rettangolo).

Answer 3

La soluzione definitiva a questo problema è in esecuzione PCA
Vorrei poter trovare un bel po 'di attuazione di fare riferimento a ...