¿Cuál es la mejor manera de calcular un centroide 3D (o n-D)?

Question

Como parte de un proyecto de trabajo, tengo que calcular el centroide de un conjunto de puntos en el espacio 3D.Ahora lo estoy haciendo de una manera que parece simple pero ingenua: tomando el promedio de cada conjunto de puntos, como en:

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

dónde x, y y z son matrices de números de punto flotante.Creo recordar que hay una manera de obtener un centroide más preciso, pero no he encontrado un algoritmo simple para hacerlo.¿Alguien tiene algunas ideas o sugerencias?Estoy usando Python para esto, pero puedo adaptar ejemplos de otros lenguajes.

Answer 1

Al contrario de lo que se suele decir aquí, existen diferentes formas de definir (y calcular) el centro de una nube de puntos.La primera y más común solución ya la ha sugerido usted y la haré no Argumente que hay algo malo en esto:

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

El "problema" aquí es que "distorsionará" su punto central dependiendo de la distribución de sus puntos.Si, por ejemplo, asumes que todos tus puntos están dentro de una caja cúbica o alguna otra forma geométrica, pero la mayoría de ellos están ubicados en la mitad superior, tu punto central también se desplazará en esa dirección.

Como alternativa, podrías utilizar el medio matemático (la media de los extremos) en cada dimensión para evitar esto:

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

Puede usar esto cuando no le importe mucho la cantidad de puntos, sino más bien el cuadro delimitador global, porque eso es todo: el centro del cuadro delimitador alrededor de sus puntos.

Por último, también puedes utilizar el median (el elemento en el medio) en cada dimensión:

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

Ahora bien, esto hará más o menos lo contrario a lo que middle y realmente le ayudará a ignorar los valores atípicos en su nube de puntos y encontrar un punto central Residencia en la distribución de tus puntos.

Una forma más sólida de encontrar un "buen" punto central podría ser ignorar el 10% superior e inferior en cada dimensión y luego calcular el average o median.Como puedes ver, puedes definir el punto central de diferentes maneras.A continuación le muestro ejemplos de 2 nubes de puntos 2D con estas sugerencias en mente.

El punto azul oscuro es el centroide promedio (medio).La mediana se muestra en verde.Y el medio se muestra en rojo.En la segunda imagen verás exactamente de lo que estaba hablando antes:El punto verde está "más cerca" de la parte más densa de la nube de puntos, mientras que el punto rojo está más lejos de ella, teniendo en cuenta los límites más extremos de la nube de puntos.

Answer 2

No, esa es la única fórmula para el centroide de una colección de puntos.Ver Wikipedia: http://en.wikipedia.org/wiki/Centroid

Answer 3

Mencionas vagamente "una forma de obtener un centroide más preciso".Quizás estés hablando de un centroide que no se ve afectado por valores atípicos.Por ejemplo, el promedio El ingreso familiar en los EE. UU. es probablemente muy alto, porque un pequeño número de muy los ricos distorsionan el promedio;ellos son los "valores atípicos".Por esa razón, los estadísticos utilizan el mediana en cambio.Una forma de obtener la mediana es ordenar los valores y luego elegir el valor que se encuentra en la mitad de la lista.

Quizás estés buscando algo como esto, pero para puntos 2D o 3D.El problema es que, en 2D y superiores, no se puede ordenar.No hay un orden natural.Sin embargo, hay maneras de deshacerse de los valores atípicos.

Una manera es encontrar el casco convexo de los puntos.El casco convexo tiene todos los puntos en el "exterior" del conjunto de puntos.Si hace esto y descarta los puntos que están en el casco, descartará los valores atípicos y los puntos que queden darán un centroide más "representativo".Incluso puedes repetir este proceso varias veces y el resultado es como pelar una cebolla.De hecho, se llama "peeling del casco convexo".

Answer 4

puede utilizar la suma para aumentar la precisión (suma de Kahan). ¿Era eso lo que tenía en mente?

Answer 5

Potencialmente más eficiente:Si estás calculando esto varias veces, puedes acelerarlo bastante manteniendo dos variables permanentes.

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

luego cambiando N y sumas cada vez que se crean o destruyen puntos.Esto cambia las cosas de O(N) a O(1) para los cálculos a costa de más trabajo cada vez que se crea, se mueve o se destruye un punto.

Answer 6

Un "centroide más preciso". Creo que el centroide se define de la forma en que lo calculó, por lo que no puede haber un "centroide más preciso".

Answer 7

Sí, esa es la fórmula correcta.

Si tienes una gran cantidad de puntos puedes explotar la simetría del problema (ya sea cilíndrico, esférico, espejo).De lo contrario, puede tomar prestado de las estadísticas y promediar un número aleatorio de puntos y simplemente cometer un pequeño error.

Answer 8

Lo entendiste.Lo que estás calculando es el centroide o el vector medio.