¿Encontrar el centro de geometría del objeto?

Dado un conjunto de puntos 2D o 3D:

¿Cómo encontrar el centro de geometría de un objeto?

Según la siguiente figura, el centro de geometría difiere del centro de masa si se calcula en la forma más simple, es decir, la densidad de masa homogénea. El problema aparece, de hecho, en el cálculo de esos. Comúnmente, un enfoque es promediar las coordenadas X y las coordenadas Y por separado, es decir, encontrar una posición promedio para los puntos dados (aquí en 2D). Esto se puede usar como centroide para el conjunto de puntos que representan un objeto. Como se muestra, debido al vértice adicional a lo largo del borde inferior, para un rectángulo simple, el centroide resultante es (0.5,0.4) mientras que la respuesta correcta es (0.5,0.5) .
Tenga en cuenta que el ejemplo dado es demasiado simple. Sin embargo, el problema de interés es para formas complejas en 2D y objetos en 3D para los que solo hay coordenadas de vértices disponibles.
Por cierto, una forma computacional eficiente es de interés.

Solo para mencionar que he revisado algunos enlaces web como Wikipedia, sin embargo, mi problema actual es que hay un grupo de puntos 2D y 3D que desean encontrar un punto como representante de ellos. Así, el centroide se volvió de interés. Los puntos se dan sin ninguna información topológica. Puede considerarlos como nube de puntos. La demostración aquí proporcionada para dejar en claro que el promedio de coordenadas comúnmente conocido (ver, por ejemplo, estas Preguntas y respuestas sobre el desbordamiento de pila ) puede ser incorrecto como se muestra en el ejemplo.

Aquí hay algunas implementaciones para comparar:

• aa = respuesta aceptada a continuación
• chull = casco convexo de puntos, es decir, el polígono dorado
• cent = centroide propuesto en Wikipedia y discutido en aa como el centroide poligonal
• centl = centroide de polilínea como se explica en aa

Visualmente, se centlve mejor representativo de la geometría dada en comparación con cent. Otros dos parecen prometedores aquí, pero generalmente son demasiado parciales si la dispersión de los puntos no es homogénea, como es el caso habitual.
Y también considere que, aunque el casco convexo hace que el problema sea bastante más simple, sin embargo, puede generar bordes demasiado largos y demasiado cortos sin ningún posicionamiento simétrico en el espacio, es decir, la conciencia es necesaria si realiza un promedio simple (es decir, sin ponderación) en ambos casos : puntos enteros (verde) o vértices de polígono de casco convexo (azul).

¿Se podría encontrar una aplicación en Encontrar el área mínima del rectángulo para puntos dados? .

Cada polígono tiene, como mínimo, cuatro "centros" distintos:

• El baricentro de sus vértices.

• El baricentro de sus bordes.

• Su baricentro como polígono.

• Un "centro" específico de SIG útil para el etiquetado (generalmente calculado con métodos patentados no documentados).

(Pueden coincidir accidentalmente en casos especiales, pero para los polígonos "genéricos" son puntos distintos).

Un "baricentro" en general es un "centro de masa". Los tres tipos difieren en el lugar donde se presume que se encuentra la masa: está completamente en los vértices, se extiende uniformemente en los bordes o se extiende uniformemente en todo el polígono.

Existen métodos simples para calcular los tres baricentros. Un enfoque se basa en el hecho básico de que el baricentro de la unión disjunta de dos masas es el promedio ponderado de la masa total de los baricentros. De esto obtenemos fácilmente lo siguiente:

1. El baricentro de dos vértices (igualmente ponderados) es su promedio. Esto se obtiene promediando sus coordenadas por separado. Geométricamente, es el punto medio del segmento de línea que une los dos vértices.

2. Inductivamente, el baricentro de n vértices (igualmente ponderados) se obtiene promediando sus coordenadas por separado.

3. El baricentro de un segmento de línea es su punto medio. (Esto está claro por simetría).

4. El baricentro de una polilínea se obtiene al encontrar los puntos medios de cada segmento de línea y luego formar su promedio ponderado utilizando las longitudes de segmento como pesos.

   Por ejemplo, considere la forma de "L" delineada por los puntos (0,0), (6,0), (6,12). Hay dos segmentos: uno de longitud 6 con punto medio en ((0 + 0) / 2, (0 + 6) / 2) = (3,0) y otro de longitud 12 con punto medio en ((6 + 6) / 2, (0 + 12) / 2) = (6,6). Por lo tanto, sus coordenadas promedio ponderadas en longitud son (x, y) con

   x = (6*3 + 12*6) / (6+12) = 5,  y = (6*0 + 12*6) / (6+12) = 4.
   

   Esto difiere del baricentro de los tres vértices, que es ((0 + 6 + 6) / 3, (0 + 0 + 12) / 3) = (4,4).

   ( Editar Como otro ejemplo, considere la figura en la pregunta, que aunque tiene forma cuadrada, se representa como un pentágono determinado por la secuencia de puntos (0,0), (1 / 2,0), (1,0), (1,1), (0,1). Los cinco lados tienen longitudes 1/2, 1/2, 1, 1, 1 y puntos medios (1 / 4,0), (3 / 4,0), (1 , 1/2), (1 / 2,1) y (0,1 / 2), respectivamente. Por lo tanto, su promedio ponderado es igual a

   [(1/2)*(1/4, 0) + (1/2)*(3/4, 0) + (1)*(1, 1/2) + (1)*(1/2, 1) + (1)*(0, 1/2)] / (1/2+1/2+1+1+1)
   = (2/4, 2/4) = (0.5, 0.5)
   

   como uno esperaría, a pesar de que el baricentro de los vértices solo (calculado como en # 2 arriba) es (0.5, 0.4).)

5. El baricentro de un polígono se puede obtener por triangulación para descomponerlo en triángulos. El baricentro de un triángulo-qua-polígono coincide con el baricentro de sus vértices. El promedio ponderado por área de estos baricentros es el baricentro del polígono. Las áreas triangulares se calculan fácilmente en términos de sus coordenadas de vértice (por ejemplo, en términos del producto de cuña de dos de los lados). Para ver una ilustración de dichos cálculos de área, incluida la forma de explotar áreas firmadas (positivas o negativas), consulte la sección sobre "Área" en la página de notas de mi curso (antiguo) .

   ( Editar Considere el polígono representado en la pregunta, por ejemplo. Podríamos triangularlo con triángulos ((0,0), (1 / 2,0), (0,1)) a la izquierda, ((0,1), (1 / 2,0), (1,1)) en el medio y ((1,1), (1,0), (1 / 2,0)) a la derecha. Sus áreas son 1/4 , 1/2, 1/4 respectivamente y sus baricentros, obtenidos promediando sus vértices, son (1 / 6,1 / 3), (1 / 2,2 / 3) y (5 / 6,1 / 3), respectivamente. El promedio ponderado por área de estos baricentros es igual a

   [(1/4)*(1/6,1/3) + (1/2)*(1/2,2/3) + (1/4)*(5/6,1/3)] / (1/4 + 1/2 + 1/4)
   = (12/24, 6/12)
   = (0.5, 0.5)
   

   como debería, a pesar de la presencia de ese quinto vértice a lo largo del borde inferior).

Es evidente que cada uno de estos métodos es eficiente : requiere un solo paso sobre la representación de "espagueti" del polígono, utilizando (bastante poco) tiempo constante en cada paso. Tenga en cuenta que en todos los casos, excepto el primero (de vértices puros), se necesita más información que solo una lista de coordenadas de vértice: también necesita conocer la topología de la figura. En el ejemplo "L", necesitábamos saber que (0,0) estaba conectado a (6,0) y no a (6,12), por ejemplo.

Todos estos son conceptos euclidianos. Se pueden extender a la esfera (o elipsoide) de varias maneras. Una sencilla ve las características como un complejo simplicial en tres dimensiones (euclidianas), calcula el baricentro apropiado y luego lo proyecta hacia afuera desde el centro del elipsoide de regreso a la superficie. Esto no requiere nuevos conceptos o fórmulas; solo tiene que trabajar con una tercera coordenada (z) además de las dos primeras coordenadas. (Las áreas aún se encuentran utilizando longitudes de productos de cuña).

Otra generalización reconoce que la métrica euclidiana, la raíz cuadrada de una suma de cuadrados, según Pitágoras, se puede cambiar a otras métricas Lp para p> = 1: se toma la raíz pth de la suma de los poderes pth. Encontrar "baricentros" apropiados ya no es tan simple, porque las hermosas propiedades aditivas explotadas anteriormente (los baricentros son promedios ponderados de los baricentros de partes más simples de una figura) ya no se mantienen en general. A menudo, se deben obtener soluciones numéricas aproximadas iterativas. Puede que ni siquiera sean únicos.

Se pueden definir centros adicionales para diversos fines. Los triángulos tienen muchos centros diferentes que pueden generalizarse (un poco) a polígonos: el centro del círculo circunferencial, el centro de (algunos) incírculos máximos, el centro de una elipse delimitadora de área mínima y otros. Cualquier conjunto puede encerrarse en varios "cascos", como el casco convexo y los centros de esos cascos obtenidos.

Tenga en cuenta que muchos de estos "centros" no están necesariamente ubicados dentro del interior de un polígono. (Sin embargo, cualquier centro razonable de un polígono convexo estará dentro de su interior).

Esta variedad de enfoques y soluciones indica que uno debe desconfiar de un término genérico como "centro de geometría" o simplemente "centro": podría ser casi cualquier cosa.