Encontre o Centróide de um Polígono
O centróide de um polígono fechado sem interseção, definido por n vértices ( x 0 , y 0 ), ( x 1 , y 1 ), ..., ( x n - 1 , y n − 1 ) é o ponto ( C x , C y ), onde
e onde A é a área assinada do polígono,
Nestas fórmulas, supõe-se que os vértices sejam numerados em ordem de ocorrência ao longo do perímetro do polígono. Além disso, presume-se que o vértice ( x n , y n ) seja o mesmo que ( x 0 , y 0 ), o que significa que i + 1 no último caso deve fazer um loop em torno de i = 0 . Observe que, se os pontos forem numerados no sentido horário, a área A , calculada como acima, terá um sinal negativo; mas as coordenadas do centróide estarão corretas, mesmo neste caso.
Dada uma lista de vértices em ordem (no sentido horário ou anti-horário), encontre o centróide do polígono fechado não interceptado por si e representado pelos vértices.
Se ajudar, você pode assumir que a entrada seja apenas CW ou apenas CCW. Diga isso na sua resposta, se precisar.
As coordenadas não precisam ser números inteiros e podem conter números negativos.
A entrada sempre será válida e conterá pelo menos três vértices.
As entradas só precisam ser manipuladas que se encaixem no tipo de dados de ponto flutuante nativo do seu idioma.
Você pode assumir que os números de entrada sempre conterão um ponto decimal.
Você pode assumir que números inteiros de entrada terminam em . ou .0.
Você pode usar números complexos para entrada.
A saída deve ser precisa até o milésimo mais próximo.
Veja também cada polígono em um plano de coordenadas, cole as coordenadas sem colchetes no menu "Editar" desta página .
Confirmei meus resultados usando esta Calculadora de pontos centróides do polígono , que é terrível. Não foi possível encontrar um em que você possa inserir todos os vértices de uma só vez ou que não tentou apagar seu -sinal quando você o digita primeiro. Vou postar minha solução Python para seu uso depois que as pessoas tiverem a chance de responder.
A técnica muito mais simples de calcular a média de todos os x e y funciona nos dois primeiros conjuntos, mas não no terceiro. Eu me pergunto o que faz a diferença ...
@ETHproductions O terceiro polígono não é convexo.
— JungHwan Min 19/10/19
@ETHproductions Se você aproximar um círculo com um polígono, poderá mover o ponto médio arbitrariamente para perto de um ponto no círculo usando mais pontos próximos a esse ponto, enquanto quase não afeta o centróide e mantém o polígono convexo.
@ETHproductions Na verdade, a convexidade não é a razão. Média de todos os xs e ys coloca todo o peso nos vértices em vez de distribuídos ao longo do corpo. O primeiro funciona porque é regular, então os dois métodos acabam no centro de simetria. O segundo funciona porque, para triângulos, os dois métodos levam ao mesmo ponto.
Podemos usar números complexos para E / S?
Geléia , 25 24 22 21 18 bytes
Aplica a fórmula mostrada no problema.
Economizou 3 bytes com a ajuda de @ Jonathan Allan.
Você pode substituir ṁL'$ṡ2por ṙ1ż@oużṙ1$
@ JonathanAllan Obrigado, também posso rodar ṙ-żpara evitar a troca e salvar outro byte
Tome isso , geléia!
Edit: Um não basta vencer Jelly ...
Gere um polígono com vértices nos pontos especificados.
Encontre o centróide do polígono.
Bem, você me bater, mas há provavelmente um caminho mais curto do que o que eu tenho, eu não tenho um entendimento completo do Jelly ainda
@miles aw ... :(
— JungHwan Min 19/10/16
Não tenho experiência com o Maxima, portanto, qualquer dica é bem-vinda.
Raquete 420 bytes
Função sem nome que recebe uma lista R de tuplas como entrada. O equivalente nomeado pode ser chamado usando, por exemplo:
Ungolfed e explicou
O passo final ( c(sum((x+X)*p),sum((y+Y)*p))/sum(p)*2/6) é uma maneira vetorizada de calcular ambos Cxe Cy. A soma nas fórmulas para Cxe Cyé armazenada em um vetor e, consequentemente, dividida pela "soma em A" *2/6. Por exemplo:
e, em seguida, impresso implicitamente.
*2/6provavelmente poderia ser /3?
@ mbomb007 É tão óbvio que acho que fui pego jogando golfe na outra parte. / shrug
Elegante, eu gosto do seu uso sapplypara lidar com essas listas! Pode haver espaço para o golfe aqui, não tenho certeza de quão flexível é a entrada permitida. Se você tiver permissão para inserir apenas uma sequência de coordenadas, c(-15.21,0.8,10.1,-0.3,-0.07,23.55)poderá salvar 17 bytes substituindo as primeiras linhas da sua função por y=l[s<-seq(2,sum(1|l),2)];x=l[-s];. Ou seja, definir ypara ser todo elemento indexado par le xpara ser todo elemento indexado ímpar.
— Rtbull #
Melhor ainda, seria se pudéssemos inserir uma matriz (ou matriz), como matrix(c(-15.21,0.8,10.1,-0.3,-0.07,23.55),2)pode ser o início de sua função x=l[1,];y=l[2,];, que economiza 35 bytes. (A matriz de entrada pode ser transposta, nesse caso x=l[,1];y=l[,2];.) É claro que a solução mais fácil de todas é se os pontos xe yforem apenas inseridos como vetores separados function(x,y), mas não acho que isso seja permitido ...
@rturnbull Perguntei ao OP nos comentários e ele queria especificamente uma lista de tuplas (muito inconveniente em R, é claro), então não acho que a abordagem matricial seja permitida. E mesmo que fosse, a entrada teria que ser a parte do vetor (ie c(...)) e a conversão da matriz teria que ser feita dentro da função.
Isso leva cada par de pontos [x, y]como um número complexo x + y*je gera o centróide resultante como um número complexo no mesmo formato.
Para o par de pontos [a, b]e [c, d], o valor a*d - b*cnecessário para cada par de pontos pode ser calculado a partir do determinante da matriz
Usando aritmética complexa, os valores complexos a + b*je c + d*jpodem ser usados ​​como
Observe que a parte imaginária é equivalente ao determinante. Além disso, o uso de valores complexos permite que os pontos sejam facilmente somados em componentes nas outras operações.
Assume que o sppacote está instalado ( https://cran.r-project.org/web/packages/sp/ )
Leva uma lista de vértices (por exemplo list(c(0.,0.), c(1.,0.), c(1.,1.), c(0.,1.)))
Aproveita o fato de que o "labpt" de um polígono é o centróide.
Implementação direta da fórmula
Não usa números complexos.
Na verdade, 45 40 39 bytes
Isso usa um algoritmo semelhante à resposta da geléia de milhas . Existe uma maneira mais curta de calcular determinantes usando um produto pontual, mas atualmente há um erro no produto pontual da Actually em que ele não funciona com listas de flutuadores. Sugestões de golfe são bem-vindas. Experimente online!
Uma versão mais curta e não competitiva
Esta é outra versão de 24 bytes que usa números complexos. Não é competitivo porque se baseia em correções de erros que pós-datam esse desafio. Experimente online!
C ++ 14, 241 bytes
Saída é a estrutura auxiliar P ,
Atualização: em vez de um retorno de chamada, estou usando [a b c d 1]como uma função e o argumento é apenas uma lista de índices para esse vetor. 1é usado como um valor sentinela ao calcularA .
Atualização 2: Não é pré A- calculado em let, usando (rest(cycle %))para obter vetores de entrada compensados ​​em um.
Em menos estágio de golfe:
Cria uma função auxiliar Fque implementa a soma com qualquer retorno de chamada l. Para Ao callback retorna constantemente 1, enquanto as coordenadas X e Y têm as suas próprias funções. (conj(subvec v 1)(v 0))descarta o primeiro elemento e anexa ao final, dessa forma é fácil acompanhar x_ie x_(i+1). Talvez ainda exista alguma repetição a ser eliminada, especialmente no final (map F[....