Encontre o Centróide de um Polígono

16

Da Wikipedia :

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

Fórmula para Centroid

e onde A é a área assinada do polígono,

Fórmula para a área 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.

Exemplos

[(0.,0.), (1.,0.), (1.,1.), (0.,1.)]        -> (0.5, 0.5)
[(-15.21,0.8), (10.1,-0.3), (-0.07,23.55)]  -> -1.727 8.017
[(-39.00,-55.94), (-56.08,-4.73), (-72.64,12.12), (-31.04,53.58), (-30.36,28.29), (17.96,59.17), (0.00,0.00), (10.00,0.00), (20.00,0.00), (148.63,114.32), (8.06,-41.04), (-41.25,34.43)]   -> 5.80104769975, 15.0673812762

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.

mbomb007
fonte
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
1
@ETHproductions O terceiro polígono não é convexo.
JungHwan Min 19/10/19
1
@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.
Christian Sievers
2
@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.
Ton Hospel
1
Podemos usar números complexos para E / S?
Xnor

Respostas:

16

Geléia , 25 24 22 21 18 bytes

S×3÷@×"
ṙ-żµÆḊçS€S

Aplica a fórmula mostrada no problema.

Economizou 3 bytes com a ajuda de @ Jonathan Allan.

Experimente online! ou Verifique todos os casos de teste.

Explicação

S×3÷@×"  Helper link. Input: determinants on LHS, sum of pairs on RHS
S        Sum the determinants
 ×3      Multiply by 3
     ×"  Vectorized multiply between determinants and sums
   ÷@    Divide that by the determinant sum multipled by 3 and return

ṙ-żµÆḊçS€S  Main link. Input: 2d list of points
ṙ-          Rotate the list of points by 1 to the right
  ż         Interleave those with the original points
            This creates all overlapping slices of length 2
   µ        Start new monadic chain
    ÆḊ      Get the determinant of each slice
       S€   Get the sum of each slice (sum of pairs of points)
      ç     Call the helper link
         S  Sum and return
milhas
fonte
Você pode substituir ṁL‘$ṡ2por ṙ1ż@oużṙ1$
Jonathan Allan
@ JonathanAllan Obrigado, também posso rodar ṙ-żpara evitar a troca e salvar outro byte
miles
Ah sim, claro!
Jonathan Allan
17

Mathematica, 23 bytes

RegionCentroid@*Polygon

Tome isso , geléia!

Edit: Um não basta vencer Jelly ...

Explicação

Polygon

Gere um polígono com vértices nos pontos especificados.

RegionCentroid

Encontre o centróide do polígono.

JungHwan Min
fonte
2
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
milhas
3
@miles aw ... :(
JungHwan Min 19/10/16
4

J, 29 bytes

2+/@(+/\(*%3*1#.])-/ .*\)],{.

Aplica a fórmula mostrada no problema.

Uso

   f =: 2+/@(+/\(*%3*1#.])-/ .*\)],{.
   f 0 0 , 1 0 , 1 1 ,: 0 1
0.5 0.5
   f _15.21 0.8 , 10.1 _0.3 ,: _0.07 23.55
_1.72667 8.01667
   f _39 _55.94 , _56.08 _4.73 , _72.64 12.12 , _31.04 53.58 , _30.36 28.29 , 17.96 59.17 , 0 0 , 10 0 , 20 0 , 148.63 114.32 , 8.06 _41.04 ,: _41.25 34.43
5.80105 15.0674

Explicação

2+/@(+/\(*%3*1#.])-/ .*\)],{.  Input: 2d array of points P [[x1 y1] [x2 y2] ...]
                           {.  Head of P
                         ]     Get P
                          ,    Join, makes the end cycle back to the front
2                              The constant 2
2                      \       For each pair of points
                  -/ .*        Take the determinant
2    +/\                       Sum each pair of points
         *                     Multiply the sum of each pair by its determinant
          %                    Divide each by
             1#.]              The sum of the determinants
           3*                  Multiplied by 3
 +/@                           Sum and return
milhas
fonte
4

Maxima, 124 118 116 112 106 byte

f(l):=(l:endcons(l[1],l),l:sum([3,l[i-1]+l[i]]*determinant(matrix(l[i-1],l[i])),i,2,length(l)),l[2]/l[1]);

Não tenho experiência com o Maxima, portanto, qualquer dica é bem-vinda.

Uso:

(%i6) f([[-15.21,0.8], [10.1,-0.3], [-0.07,23.55]]);
(%o6)              [- 1.726666666666668, 8.016666666666668]
Peneiradores cristãos
fonte
3

Raquete 420 bytes

(let*((lr list-ref)(getx(lambda(i)(lr(lr l i)0)))(gety(lambda(i)(lr(lr l i)1)))(n(length l))(j(λ(i)(if(= i(sub1 n))0(add1 i))))
(A(/(for/sum((i n))(-(*(getx i)(gety(j i)))(*(getx(j i))(gety i))))2))
(cx(/(for/sum((i n))(*(+(getx i)(getx(j i)))(-(*(getx i)(gety(j i)))(*(getx(j i))(gety i)))))(* 6 A)))
(cy(/(for/sum((i n))(*(+(gety i)(gety(j i)))(-(*(getx i)(gety(j i)))(*(getx(j i))(gety i)))))(* 6 A))))
(list cx cy))

Ungolfed:

(define(f l)
  (let* ((lr list-ref)
         (getx (lambda(i)(lr (lr l i)0)))
         (gety (lambda(i)(lr (lr l i)1)))
         (n (length l))
         (j (lambda(i) (if (= i (sub1 n)) 0 (add1 i))))
         (A (/(for/sum ((i n))
                (-(* (getx i) (gety (j i)))
                  (* (getx (j i)) (gety i))))
              2))
         (cx (/(for/sum ((i n))
                 (*(+(getx i)(getx (j i)))
                   (-(*(getx i)(gety (j i)))
                     (*(getx (j i))(gety i)))))
               (* 6 A)))
         (cy (/(for/sum ((i n))
                 (*(+(gety i)(gety (j i)))
                   (-(*(getx i)(gety (j i)))
                     (*(getx (j i))(gety i)))))
               (* 6 A))))
    (list cx cy)))

Teste:

(f '[(-15.21 0.8)  (10.1 -0.3)  (-0.07 23.55)] ) 
(f '[(-39.00 -55.94)  (-56.08 -4.73)  (-72.64 12.12)  (-31.04 53.58) 
     (-30.36 28.29)  (17.96 59.17)  (0.00 0.00)  (10.00 0.00)  
     (20.00 0.00) (148.63 114.32)  (8.06 -41.04)  (-41.25 34.43)])

Resultado:

'(-1.7266666666666677 8.01666666666667)
'(5.8010476997538465 15.067381276150996)
rnso
fonte
3

R, 129 127 bytes

function(l){s=sapply;x=s(l,`[`,1);y=s(l,`[`,2);X=c(x[-1],x[1]);Y=c(y[-1],y[1]);p=x*Y-X*y;c(sum((x+X)*p),sum((y+Y)*p))/sum(p)/3}

Função sem nome que recebe uma lista R de tuplas como entrada. O equivalente nomeado pode ser chamado usando, por exemplo:

f(list(c(-15.21,0.8),c(10.1,-0.3),c(-0.07,23.55)))

Ungolfed e explicou

f=function(l){s=sapply;                           # Alias for sapply
              x=s(l,`[`,1);                       # Split list of tuples into vector of first elements
              y=s(l,`[`,2);                       # =||= but for second element 
              X=c(x[-1],x[1]);                    # Generate a vector for x(i+1)
              Y=c(y[-1],y[1]);                    # Generate a vector for y(i+1)
              p=x*Y-X*y;                          # Calculate the outer product used in both A, Cx and Cy
              c(sum((x+X)*p),sum((y+Y)*p))/sum(p)/3    # See post for explanation
}

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:

(SUMinCx, SUMinCy) / SUMinA / 3

e, em seguida, impresso implicitamente.

Experimente no R-fiddle

Billywob
fonte
*2/6provavelmente poderia ser /3?
mbomb007
@ mbomb007 É tão óbvio que acho que fui pego jogando golfe na outra parte. / shrug
Billywob
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
@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.
Billywob
2

Python, 156 127 bytes

def f(p):n=len(p);p=p+p[:1];i=s=0;exec'd=(p[i].conjugate()*p[i+1]).imag;s+=d;p[i]=(p[i]+p[i+1])*d;i+=1;'*n;print sum(p[:n])/s/3

Ungolfed:

def f(points):
  n = len(points)
  points = points + [points[0]]
  determinantSum = 0
  for i in range(n):
    determinant = (points[i].conjugate() * points[i+1]).imag
    determinantSum += determinant
    points[i] = (points[i] + points[i+1]) * determinant
  print sum(points[:n]) / determinantSum / 3

Ideone it.

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

| a b |
| c d |

Usando aritmética complexa, os valores complexos a + b*je c + d*jpodem ser usados ​​como

conjugate(a + b*j) * (c + d*j)
(a - b*j) * (c + d*j)
(a*c + b*d) + (a*d - b*c)*j

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.

milhas
fonte
2

R + sp (46 bytes)

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.

function(l)sp::Polygon(do.call(rbind,l))@labpt
mnel
fonte
2

JavaScript (ES6), 102

Implementação direta da fórmula

l=>[...l,l[0]].map(([x,y],i)=>(i?(a+=w=t*y-x*u,X+=(t+x)*w,Y+=(u+y)*w):X=Y=a=0,t=x,u=y))&&[X/3/a,Y/3/a]

Teste

f=
l=>[...l,l[0]].map(([x,y],i)=>(i?(a+=w=t*y-x*u,X+=(t+x)*w,Y+=(u+y)*w):X=Y=a=0,t=x,u=y))&&[X/3/a,Y/3/a]

function go()
{
  var c=[],cx,cy;
  // build coordinates array
  I.value.match(/-?[\d.]+/g).map((v,i)=>i&1?t[1]=+v:c.push(t=[+v]));
  console.log(c+''),
  [cx,cy]=f(c);
  O.textContent='CX:'+cx+' CY:'+cy;
  // try to display the polygon
  var mx=Math.max(...c.map(v=>v[0])),
    nx=Math.min(...c.map(v=>v[0])),
    my=Math.max(...c.map(v=>v[1])),
    ny=Math.min(...c.map(v=>v[1])),  
    dx=mx-nx, dy=my-ny,
    ctx=C.getContext("2d"),
    cw=C.width, ch=C.height,
    fx=(mx-nx)/cw, fy=(my-ny)/ch, fs=Math.max(fx,fy)
  C.width=cw
  ctx.setTransform(1,0,0,1,0,0);
  ctx.beginPath();
  c.forEach(([x,y],i)=>ctx.lineTo((x-nx)/fs,(y-ny)/fs));
  ctx.closePath();
  ctx.stroke();
  ctx.fillStyle='#ff0000';
  ctx.fillRect((cx-nx)/fs-2,(cy-ny)/fs-2,5,5);
}
go()
#I { width:90% }
#C { width:90%; height:200px;}
<input id=I value='[[-15.21,0.8], [10.1,-0.3], [-0.07,23.55]]'>
<button onclick='go()'>GO</button>
<pre id=O></pre>
<canvas id=C></canvas>

edc65
fonte
1

Python 2, 153 bytes

Não usa números complexos.

P=input()
A=x=y=0;n=len(P)
for i in range(n):m=-~i%n;a=P[i][0];b=P[i][1];c=P[m][0];d=P[m][1];t=a*d-b*c;A+=t;x+=t*(a+c);y+=t*(b+d)
k=1/(3*A);print x*k,y*k

Experimente online

Ungolfed:

def centroid(P):
    A=x=y=0
    n=len(P)
    for i in range(n):
        m=-~i%n
        x0=P[i][0];y0=P[i][1]
        x1=P[m][0];y1=P[m][1]
        t = x0*y1 - y0*x1
        A += t/2.
        x += t * (x0 + x1)
        y += t * (y0 + y1)
    k = 1/(6*A)
    x *= k
    y *= k
    return x,y
mbomb007
fonte
1

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!

;\Z♂#;`i¥`M@`i│N@F*)F@N*-`M;Σ3*)♀*┬♂Σ♀/

Ungolfing

         Implicit input pts.
;\       Duplicate pts, rotate right.
Z        Zip rot_pts and pts together.
♂#       Convert the iterables inside the zip to lists
         (currently necessary due to a bug with duplicate)
;        Duplicate the zip.
`...`M   Get the sum each pair of points in the zip.
  i        Flatten the pair to the stack.
  ¥        Pairwise add the two coordinate vectors.
@        Swap with the other zip.
`...`M   Get the determinants of the zip.
  i│       Flatten to stack and duplicate entire stack.
           Stack: [a,b], [c,d], [a,b], [c,d]
  N@F*)    Push b*c and move it to BOS.
  F@N*     Push a*d.
  -        Get a*d-b*c.
;Σ3*)    Push 3 * sum(determinants) and move it to BOS.
♀*       Vector multiply the determinants and the sums.
┬        Transpose the coordinate pairs in the vector.
♂Σ       Sum the x's, then the y's.
♀/       Divide the x and y of this last coordinate pair by 3*sum(determinants).
         Implicit return.

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!

;\│¥)Z`iá*╫@X`M;Σ3*)♀*Σ/

Ungolfing

         Implicit input a list of complex numbers, pts.
;\       Duplicate pts, rotate right.
│        Duplicate stack. Stack: rot_pts, pts, rot_pts, pts.
¥)       Pairwise sum the two lists of points together and rotate to BOS.
Z        Zip rot_pts and pts together.
`...`M   Map the following function over the zipped points to get our determinants.
  i        Flatten the list of [a+b*i, c+d*i].
  á        Push the complex conjugate of a+bi, i.e. a-b*i.
  *        Multiply a-b*i by c+d*i, getting (a*c+b*d)+(a*d-b*c)*i.
           Our determinant is the imaginary part of this result.
  ╫@X      Push Re(z), Im(z) to the stack, and immediately discard Re(z).
           This map returns a list of these determinants.
;        Duplicate list_determinants.
Σ3*)     Push 3 * sum(list_determinants) and rotate that to BOS.
♀*Σ      Pairwise multiply the sums of pairs of points and the determinants and sum.
/        Divide that sum by 3*sum(list_determinants).
         Implicit return.
Sherlock9
fonte
1

C ++ 14, 241 bytes

struct P{float x;float y;};
#define S(N,T)auto N(P){return 0;}auto N(P a,P b,auto...V){return(T)*(a.x*b.y-b.x*a.y)+N(b,V...);}
S(A,1)S(X,a.x+b.x)S(Y,a.y+b.y)auto f(auto q,auto...p){auto a=A(q,p...,q)*3;return P{X(q,p...,q)/a,Y(q,p...,q)/a};}

Saída é a estrutura auxiliar P ,

Ungolfed:

 //helper struct
struct P{float x;float y;};

//Area, Cx and Cy are quite similar
#define S(N,T)\  //N is the function name, T is the term in the sum
auto N(P){return 0;} \   //end of recursion for only 1 element
auto N(P a,P b,auto...V){ \ //extract the first two elements
  return (T)*(a.x*b.y-b.x*a.y) //compute with a and b
         + N(b,V...); \        //recursion without first element
}

//instantiate the 3 formulas
S(A,1)
S(X,a.x+b.x)
S(Y,a.y+b.y)


auto f(auto q,auto...p){
  auto a=A(q,p...,q)*3; //q,p...,q appends the first element to the end
  return P{X(q,p...,q)/a,Y(q,p...,q)/a};
}

Uso:

f(P{0.,0.}, P{1.,0.}, P{1.,1.}, P{0.,1.})
f(P{-15.21,0.8}, P{10.1,-0.3}, P{-0.07,23.55})
Karl Napf
fonte
1

Clojure, 177 156 143 bytes

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.

#(let[F(fn[I](apply +(map(fn[[a b][c d]](*(apply +(map[a b c d 1]I))(-(* a d)(* c b))))%(rest(cycle %)))))](for[i[[0 2][1 3]]](/(F i)(F[4])3)))

Versão original:

#(let[F(fn[L](apply +(map(fn[[a b][c d]](*(L[a b c d])(-(* a d)(* c b))))%(conj(subvec % 1)(% 0)))))A(*(F(fn[& l]1))3)](map F[(fn[v](/(+(v 0)(v 2))A))(fn[v](/(+(v 1)(v 3))A))]))

Em menos estágio de golfe:

(def f (fn[v](let[F (fn[l](apply +(map
                                    (fn[[a b][c d]](*(l a b c d)(-(* a d)(* c b))))
                                    v
                                    (conj(subvec v 1)(v 0)))))
                  A (* (F(fn[& l] 1)) 3)]
                [(F (fn[a b c d](/(+ a c)A)))
                 (F (fn[a b c d](/(+ b d)A)))])))

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[....

NikoNyrh
fonte