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

Question

Bueno, podría ser una pregunta sencilla. Dado un conjunto de puntos 2D o 3D, la pregunta es:

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

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

Actualización 1:
Sólo para mencionar que he revisado algunos enlaces web como los de Wikipedia, sin embargo mi problema actual es que hay un grupo de puntos 2D y 3D que desean encontrar un punto como representante de esos. Por lo tanto, el centroide se volvió de interés. Los puntos se dan sin ninguna información topológica. Pueden considerarse como nubes de puntos. La demostración aquí proporcionada para aclarar que el promedio comúnmente conocido de coordenadas (ver por ejemplo este ) puede ser incorrecta como se muestra en el ejemplo. Espero que el punto esté claro ahora.

Actualización 2:
Aquí hay algunas implementaciones para comparar:

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

Visualmente, centl parece más representativa de la geometría dada en comparación con cent . Otros dos parecen prometedores aquí, pero normalmente están demasiado sesgados si la dispersión de los puntos fuera inhomogénea como es el caso habitual.
Y también considere que aunque el casco convexo hace el problema razonablemente 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 se hace un promedio simple (es decir, sin ponderación) para ambos casos: puntos enteros (verde) o vértices de polígonos de casco convexo (azul).

Actualización 3:
Una aplicación puede encontrarse en este puesto .

Answer 1

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 del SIG útil para el etiquetado (normalmente calculado con métodos propietarios 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 cuanto al lugar en el que se supone que se encuentra la masa: o bien está enteramente en los vértices, repartida uniformemente en los bordes, o repartida uniformemente en el propio polígono.

Existen métodos sencillos para calcular los tres baricentros. Un método se basa en el hecho básico de que el baricentro de la unión disjunta de dos masas es la media total ponderada de los baricentros. De aquí se obtiene fácilmente lo siguiente:

1. El baricentro de dos vértices (igualmente ponderados) es su media. 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 encontrando los puntos medios de cada segmento de línea y luego formando su media ponderada utilizando las longitudes de los segmentos 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). Sus coordenadas medias ponderadas por la longitud son, por tanto, (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 de 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 tanto, su media ponderada 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 cabría esperar, aunque el baricentro de los vértices por sí solo (calculado como en el punto 2 anterior) 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-cuatropolígono coincide con el baricentro de sus vértices. La media ponderada de estos baricentros es el baricentro del polígono. Las áreas de los triángulos se calculan fácilmente en función de las coordenadas de sus vértices (por ejemplo, en función del producto de cuña de dos de los lados). Para ver una ilustración de este tipo de cálculos de área, incluida la forma de aprovechar las áreas con signo (positivo o negativo), véase la sección sobre "Área" en mi (antiguo) página de notas del curso .

   ( Editar Consideremos, por ejemplo, el polígono representado en la pregunta. Podríamos triangularlo con los triángulos ((0,0), (1/2,0), (0,1)) a la izquierda, ((0,1), (1/2,0), (1,1)) en el centro, 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. La media ponderada 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 en el borde inferior).

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

Todos estos son conceptos euclidianos. Pueden extenderse a la esfera (o elipsoide) de varias maneras. Una de ellas es considerar los rasgos como un complejo simplicial en tres dimensiones (euclidianas), calcular el baricentro correspondiente y proyectarlo desde el centro del elipsoide hasta la superficie. Esto no requiere nuevos conceptos ni fórmulas; sólo hay que trabajar con una tercera coordenada (z) además de las dos primeras. (Las áreas son todavía encontrados utilizando longitudes de productos en cuña).

Otra generalización reconoce que la métrica euclidiana -la raíz cuadrada de una suma de cuadrados, según Pitágoras- puede cambiarse por otras Métricas Lp para p >= 1: se toma la raíz p de la suma de las potencias p. Encontrar los "baricentros" adecuados ya no es tan sencillo, porque las bellas propiedades aditivas explotadas anteriormente (los baricentros son medias ponderadas de baricentros de partes más simples de una figura) ya no se mantienen en general. A menudo hay que obtener soluciones numéricas aproximadas e iterativas. Puede que ni siquiera sean únicas.

Se pueden definir centros adicionales para diversos fines. Los triángulos tienen muchos centros diferentes que pueden generalizarse (en cierto modo) a los polígonos: el centro de la circunferencia, el centro de (alguna) incircunferencia máxima, el centro de una elipse de área mínima, y otros. Cualquier conjunto puede encerrarse en varios "cascos", como el casco convexo, y obtener los centros de esos cascos.

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

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