Qual è il modo migliore per calcolare il 3D (o n-D-a) baricentro?

Question

Come parte di un progetto di lavoro che devo calcolare il baricentro di un insieme di punti nello spazio 3D.Proprio ora sto facendo in un modo che sembra semplice ma ingenuo -- considerando la media di ogni insieme di punti, come in:

centroid = average(x), average(y), average(z)

dove x, y e z sono matrici di numeri a virgola mobile.Mi sembra di ricordare che c'è un modo per ottenere una più accurata baricentro, ma non ho trovato un algoritmo semplice per farlo.Qualcuno ha idee o suggerimenti?Sto usando Python per questo, ma posso adattare esempi da altre lingue.

Answer 1

Contraria al comune di astenersi qui, ci sono diversi modi per definire (e calcolare) un centro di una nuvola di punti.Il primo e più comune soluzione è stata suggerita da voi già e io non dire che c'è qualcosa di sbagliato in questo:

centroid = average(x), average(y), average(z)

Il "problema" qui è quella di "falsare" il punto centrale a seconda della distribuzione dei punti.Se, per esempio, si assume che tutti i punti sono all'interno di una scatola cubica o qualche altra forma geometrica, ma la maggior parte di loro capita di essere collocato nella metà superiore, il punto centrale sarà anche spostare in quella direzione.

Come alternativa si può utilizzare la matematica medio (media degli extrema) in ogni dimensione per evitare questo:

middle = middle(x), middle(y), middle(z)

È possibile utilizzare questa funzione quando non si cura molto circa il numero di punti, ma di più su riquadro di delimitazione, perché tutto questo è il centro del rettangolo di selezione intorno i tuoi punti.

Infine, è anche possibile utilizzare il median (elemento centrale), in ogni dimensione:

median = median(x), median(y), median(z)

Ora questo tipo di fare il contrario per il middle e effettivamente aiutare a ignorare i valori anomali nel tuo punto di cloud e trovare un punto centrale basato su la distribuzione dei punti.

Un modo efficace per trovare un "buon" punto centrale potrebbe essere quella di ignorare la parte superiore e inferiore del 10% in ogni dimensione e quindi calcolare l' average o median.Come si può vedere è possibile definire il punto centrale in modi diversi.Di seguito vi mostro alcuni esempi di 2 2D nuvole di punti con questi suggerimenti in mente.

Il blu scuro punto è la media del baricentro.La mediana è evidenziato in verde.E il mezzo è mostrato in rosso.Nella seconda immagine puoi vedere esattamente ciò di cui parlavo in precedenza:Il punto verde è "vicino" alla più parte della nuvola di punti, mentre il red dot è un ulteriore modo da esso, tenendo conto dei confini più estremi della nuvola di punti.

Answer 2

Nope, che è l'unica formula per il baricentro di un insieme di punti.Vedi Wikipedia: http://en.wikipedia.org/wiki/Centroid

Answer 3

È vagamente parlare di "un modo per ottenere una più accurata baricentro".Forse stai parlando di un baricentro che non è influenzato da valori anomali.Per esempio, il media il reddito delle famiglie negli USA è probabilmente molto alto, perché un piccolo numero di molto ricchi di inclinazione media;sono gli "outliers".Per questo motivo, consigliabile usare il mediana invece.Un modo per ottenere la mediana è quello di ordinare i valori, quindi scegliere il valore a metà strada giù la lista.

Forse stai cercando qualcosa di simile a questo, ma per il 2D o 3D punti.Il problema è, in 2D e superiore, non si può risolvere.Non c'è ordine naturale.Tuttavia, ci sono modi per sbarazzarsi di valori anomali.

Un modo è quello di trovare la convex hull dei punti.Il convex hull ha tutti i punti "di fuori" dell'insieme di punti.Se si esegue questa operazione, e buttare fuori i punti che sono sullo scafo, sarete buttare fuori gli outlier, e i punti che rimangono darà un effetto più "rappresentativo" baricentro.È anche possibile ripetere questo processo più volte, e il risultato è tipo come sbucciare una cipolla.Infatti, si chiama "convex hull peeling".

Answer 4

è possibile utilizzare per aumentare la precisione di somma - Kahan somma - era questo che aveva in mente?

Answer 5

Potenzialmente più efficiente:se sei il calcolo di questo più volte, è possibile accelerare un po ' da tenere due piedi variabili

N  # number of points
sums = dict(x=0,y=0,z=0)  # sums of the locations for each point

poi, cambiando la N e somme ogni volta che i punti sono creata o distrutta.Questo cambia le cose da O(N) O(1) per i calcoli, al costo di più di lavoro ogni volta che viene creato un punto, si sposta o viene distrutto.

Answer 6

"Una più accurata baricentro" credo che il baricentro è definito il modo in cui viene calcolato di conseguenza non ci può essere "più accurata baricentro".

Answer 7

Sì che è la formula corretta.

Se si dispone di un gran numero di punti è possibile sfruttare la simmetria del problema (cilindrico, sferico, specchio).In caso contrario, si può prendere in prestito da statistiche e la media di un numero casuale di punti e solo avere un po ' di errore.

Answer 8

Avete ottenuto.Che cosa si calcola il baricentro, o il vettore delle medie.