Encontrando o centro da geometria do objeto?

Dado um conjunto de pontos 2D ou 3D:

Como encontrar o centro da geometria de um objeto?

De acordo com a figura a seguir, o centro da geometria difere do centro de massa se for calculado da forma mais simples, isto é, densidade homogênea de massa. O problema aparece, de fato, no cálculo desses. Geralmente, uma abordagem é calcular em média as coordenadas X e as coordenadas Y separadamente, ou seja, encontrar uma posição média para os pontos dados (aqui em 2D). Isso pode ser usado como centróide para o conjunto de pontos que representam um objeto. Como mostrado, devido ao vértice extra ao longo da borda inferior, para um retângulo simples, o centróide resultante é (0,5,0,4) enquanto a resposta correta é (0,5,0,5) .
Observe que o exemplo dado é muito simples. O problema de interesse, no entanto, é para formas complexas em 2D e objetos em 3D para os quais apenas coordenadas de vértices estão disponíveis.
BTW, uma maneira computacional eficiente é de interesse.

Apenas para mencionar que verifiquei alguns links da Web, como o da Wikipedia, mas meu problema atual é que há um grupo de pontos 2D e 3D que desejam encontrar um ponto como representativo para eles. Assim, o centróide tornou-se interessante. Os pontos são dados sem qualquer informação topológica. Você pode considerá-los como nuvem de pontos. A demonstração aqui fornecida para deixar claro que a média comum de coordenadas conhecida (consulte, por exemplo, estas Perguntas e Respostas sobre estouro de pilha ) pode estar incorreta, como mostrado no exemplo.

Aqui estão algumas implementações para comparação:

• aa = resposta aceita abaixo
• chull = casco convexo de pontos, isto é, o polígono dourado
• cent = centróide proposto na Wikipedia e discutido em aa como o centróide poligonal
• centl = centróide de polilinha, conforme explicado em aa

Visualmente, centlparece melhor representativo para a geometria fornecida em comparação com cent. Dois outros parecem promissores aqui, mas geralmente eles são muito tendenciosos se a dispersão dos pontos não for homogênea, como é o caso usual.
E considere também que, embora o casco convexo torne o problema razoavelmente mais simples, no entanto, pode gerar bordas muito longas e muito curtas sem nenhum posicionamento simétrico no espaço, ou seja, a conscientização é necessária se você fizer uma média simples (ou seja, sem ponderação) para ambos os casos. : pontos inteiros (verde) ou vértices poligonais do casco convexo (azul).

Uma aplicação pode ser encontrada em Como encontrar um retângulo de área mínima para determinados pontos? .

Todo polígono possui, no mínimo, quatro "centros" distintos:

• O baricentro de seus vértices.

• O baricentro de suas bordas.

• Seu baricentro como um polígono.

• Um "centro" específico de GIS útil para rotular (geralmente calculado com métodos proprietários não documentados).

(Eles podem coincidir acidentalmente em casos especiais, mas para polígonos "genéricos" são pontos distintos.)

Um "baricentro" em geral é um "centro de massa". Os três tipos diferem no local em que a massa é presumida: ou ela é inteiramente sobre os vértices, se espalha uniformemente nas bordas ou se espalha uniformemente por todo o polígono.

Existem métodos simples para calcular todos os três baricentros. Uma abordagem baseia-se no fato básico de que o baricentro da união disjunta de duas massas é a média ponderada da massa total dos baracentros. A partir disso, obtemos facilmente o seguinte:

1. O baricentro de dois vértices (igualmente ponderados) é sua média. Isso é obtido pela média de suas coordenadas separadamente. Geometricamente, é o ponto médio do segmento de linha que une os dois vértices.

2. Indutivamente, o baricentro de n vértices (igualmente ponderados) é obtido pela média de suas coordenadas separadamente.

3. O baricentro de um segmento de linha é seu ponto médio. (Isso é claro por simetria.)

4. O baricentro de uma polilinha é obtido encontrando os pontos médios de cada segmento de linha e, em seguida, formando sua média ponderada usando os comprimentos do segmento como pesos.

   Por exemplo, considere a forma "L" delineada pelos pontos (0,0), (6,0), (6,12). Existem dois segmentos: um de comprimento 6 com ponto médio em ((0 + 0) / 2, (0 + 6) / 2) = (3,0) e outro de comprimento 12 com ponto médio em ((6 + 6) / 2, (0 + 12) / 2) = (6,6). Suas coordenadas médias ponderadas em comprimento são, portanto, (x, y) com

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

   Isso difere do baricentro dos três vértices, que é ((0 + 6 + 6) / 3, (0 + 0 + 12) / 3) = (4,4).

   ( Editar Como outro exemplo, considere a figura na pergunta, que apesar de quadrada, é representada como um pentágono determinado pela sequência de pontos (0,0), (1 / 2,0), (1,0), (1,1), (0,1). Os cinco lados têm comprimentos 1/2, 1/2, 1, 1, 1 e pontos médios (1 / 4,0), (3 / 4,0), (1 , 1/2), (1 / 2,1) e (0,1 / 2), respectivamente, e, portanto, sua média ponderada é 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 seria de esperar, mesmo que o baricentro dos vértices sozinho (calculado como no 2 acima) seja (0,5, 0,4).)

5. O baricentro de um polígono pode ser obtido por triangulação para decompô-lo em triângulos. O baricentro de um triângulo-qua-polígono coincide com o baricentro de seus vértices. A média ponderada por área desses barcentros é o baricentro do polígono. As áreas de triângulo são prontamente calculadas em termos de suas coordenadas de vértices (por exemplo, em termos de produto em cunha de dois dos lados). Para uma ilustração desses cálculos de área, incluindo como explorar áreas assinadas (positivas ou negativas), consulte a seção "Área" na minha página de notas de curso (antiga) .

   ( Editar Considere o polígono representado na pergunta, por exemplo. Podemos triangulá-lo com triângulos ((0,0), (1 / 2,0), (0,1)) à esquerda, ((0,1), (1 / 2,0), (1,1)) no meio e ((1,1), (1,0), (1 / 2,0)) à direita.Suas áreas são 1/4 , 1/2, 1/4 respectivamente e seus baricentros - obtidos pela média de seus vértices - são (1 / 6,1 / 3), (1 / 2,2 / 3) e (5 / 6,1 / 3), respectivamente.A média ponderada por área desses centros de barreiras é 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 deveria, apesar da presença desse quinto vértice ao longo da borda inferior.)

É evidente que cada um desses métodos é eficiente : requer apenas uma única passagem sobre a representação "espaguete" do polígono, usando (relativamente pouco) tempo constante em cada etapa. Observe que em todos os casos, exceto o primeiro (de vértices puros), são necessárias mais informações do que apenas uma lista de coordenadas de vértices: você também precisa conhecer a topologia da figura. No exemplo "L", precisávamos saber que (0,0) estava conectado a (6,0) e não a (6,12), por exemplo.

Estes são todos os conceitos euclidianos. Eles podem ser estendidos para a esfera (ou elipsóide) de várias maneiras. Um simples visualiza os recursos como um complexo simplicial em três dimensões (euclidianas), calcula o baricentro apropriado e o projeta para fora do centro do elipsóide de volta à superfície. Isso não requer novos conceitos ou fórmulas; você só precisa trabalhar com uma terceira (z) coordenada, além das duas primeiras. (As áreas ainda são encontradas usando comprimentos de produtos de cunha.)

Outra generalização reconhece que a métrica euclidiana - a raiz quadrada de uma soma dos quadrados, de acordo com Pitágoras - pode ser alterada para outras métricas de Lp para p> = 1: você toma a raiz enésima da soma da enésima potência. Encontrar "baricentros" apropriados não é mais tão simples, porque as belas propriedades aditivas exploradas acima (baricenters são médias ponderadas de baricentros de partes mais simples de uma figura) não são mais válidas em geral. Freqüentemente, soluções numéricas aproximadas iterativas precisam ser obtidas. Eles podem até não ser únicos.

Centros adicionais podem ser definidos para vários propósitos. Os triângulos têm muitos centros diferentes que podem generalizar (de alguma forma) para polígonos: o centro do circuncirculo, o centro de (alguns) incirculo máximo, o centro de uma elipse delimitadora de área mínima e outros. Qualquer conjunto pode ser encerrado em vários "cascos", como o casco convexo e os centros dos cascos obtidos.

Observe que muitos desses "centros" não estão necessariamente localizados no interior de um polígono. (Qualquer centro razoável de um polígono convexo estará dentro de seu interior.)

Essa variedade de abordagens e soluções indica que é preciso ter cuidado com um termo genérico como "centro da geometria" ou meramente "centro": pode ser qualquer coisa.