Qual é a melhor maneira para calcular um 3D (ou n-D) centróide?

Question

Como parte de um projeto de trabalho que eu tenho para calcular o centróide de um conjunto de pontos no espaço 3D.Agora eu estou fazendo isso de uma forma que parece simples, mas ingênua -- pela média de cada conjunto de pontos, como em:

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

onde x, y e z são matrizes de números de ponto flutuante.Eu me lembro que há um caminho para obter um quadro mais preciso centróide, mas eu não encontrei um algoritmo simples para fazê-lo.Alguém tem alguma idéia ou sugestão?Eu estou usando Python para isso, mas eu posso adaptar-se exemplos de outros idiomas.

Answer 1

Ao contrário do comum abster-se aqui, existem diferentes formas de definir (e calcular) o centro de uma nuvem de pontos.A primeira e a solução mais comum tem sido sugerido por você e já vou não argumentam que não há nada de errado com este:

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

O "problema" aqui é que ele vai "distorcer" o centro de pontos dependendo de a distribuição de seus pontos.Se, por exemplo, suponha que todos os seus pontos estão dentro de uma cúbicos de caixa ou de alguma outra forma geométrica, mas a maioria deles acontecem para ser colocado na metade superior, o centro-ponto também mudança de direção.

Como alternativa, você pode usar a matemática médio (a média da extrema) em cada dimensão para evitar isso:

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

Você pode usar isso quando você não se preocupa muito com o número de pontos, mas mais sobre o global caixa delimitadora, porque este é o centro da caixa delimitadora em torno de seus pontos.

Por fim, você também pode usar o median (o elemento no meio) em cada dimensão:

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

Agora isso vai de classificação de fazer o oposto para o middle e realmente ajudá-lo a ignorar os outliers em sua nuvem de pontos e encontrar um ponto central com base no a distribuição de seus pontos.

Uma forma eficiente de encontrar um "bom" centerpoint poderia ser a de ignorar a parte superior e inferior de 10% em cada dimensão e, em seguida, calcular o average ou median.Como você pode ver, você pode definir o ponto central de maneiras diferentes.Abaixo estou mostrando exemplos de 2 2D nuvens de pontos com estas sugestões em mente.

O azul escuro ponto é a média (média aritmética) do centróide.A mediana é mostrado em verde.E o meio é mostrado em vermelho.Na segunda imagem, você verá exatamente o que eu estava falando antes:O ponto verde é "mais" para a sua parte mais densa da nuvem de pontos, enquanto o ponto vermelho é mais uma forma, tendo em conta os mais extremos limites da nuvem de pontos.

Answer 2

Nope, que é a única fórmula para o centróide de uma coleção de pontos.Ver Wikipedia: http://en.wikipedia.org/wiki/Centroid

Answer 3

Você vagamente mencionar "uma maneira de obter um quadro mais preciso centróide".Talvez você esteja falando de um centróide, que não é afetada por valores atípicos.Por exemplo, o média rendimento do agregado familiar, nos EUA, é, provavelmente, muito alto, porque um pequeno número de muito as pessoas ricas inclinação média;eles são os "outliers".Por essa razão, os estatísticos utilizam o mediana em vez disso.Uma forma de se obter a mediana é ordenar os valores, em seguida, escolher o valor da metade da lista.

Talvez você esteja procurando por algo assim, mas para 2D ou 3D pontos.O problema é que, em 2D e superior, você não pode classificar.Não há uma ordem natural.No entanto, existem maneiras de se livrar de outliers.

Uma maneira é encontrar o olucro convexo um dos pontos.A convex hull tem todos os pontos nos "fora" do conjunto de pontos.Se você fizer isso, e jogar fora os pontos que estão no casco, você estará jogando fora a outliers, e os pontos que permanecem vai dar mais um "representante" centróide.Você pode até repetir esse processo várias vezes, e o resultado é uma espécie de como descascar uma cebola.Na verdade, ele é chamado de "convex hull peeling".

Answer 4

você pode usar a aumentar a precisão soma - Kahan soma - era isso que você tinha em mente?

Answer 5

Potencialmente mais eficientes:se você está calculando isso várias vezes, você pode acelerar este um pouco por manter duas variáveis de pé

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

em seguida, alterando N e a soma sempre que os pontos são criados ou destruídos.Isso muda as coisas a partir de O(N) para O(1) para os cálculos do custo de mais trabalho a cada vez que um ponto é criado, se move, ou é destruído.

Answer 6

"Mais precisas centróide" eu acredito centróide é definido da forma calculada, portanto, não pode haver "mais preciso do centróide".

Answer 7

Sim essa é a fórmula correta.

Se você tiver um grande número de pontos que você pode explorar a simetria do problema (seja ele cilíndrica, esférica, espelho).Caso contrário, você pode pedir a partir de estatísticas e a média de um número aleatório de pontos e basta ter um pouco de erro.

Answer 8

Você tem isso.O que você está calculando é o centróide, ou seja, a média do vetor.