De Wikipédia :

Le centre de gravité d'un polygone fermé non auto-intersecté défini par n sommets ( x ₀ , y ₀ ), ( x ₁ , y ₁ ), ..., ( x _{n - 1} , y _{n − 1} ) est le point ( C _x , C _y ), où

et où A est la zone signée du polygone,

Dans ces formules, les sommets sont supposés être numérotés dans l'ordre de leur occurrence le long du périmètre du polygone. De plus, le sommet ( x _n , y _n ) est supposé être le même que ( x ₀ , y ₀ ), ce qui signifie que i + 1 dans le dernier cas doit boucler vers i = 0 . Notez que si les points sont numérotés dans le sens horaire, la zone A , calculée comme ci-dessus, aura un signe négatif; mais les coordonnées du centroïde seront correctes même dans ce cas.

• Étant donné une liste de sommets dans l'ordre (dans le sens horaire ou antihoraire), trouvez le centroïde du polygone fermé non auto-intersecté représenté par les sommets.
  • Si cela peut vous aider, vous pouvez supposer que l'entrée est uniquement CW ou CCW uniquement. Dites-le dans votre réponse si vous en avez besoin.
• Les coordonnées ne sont pas obligatoirement des entiers et peuvent contenir des nombres négatifs.
• L'entrée sera toujours valide et contiendra au moins trois sommets.
• Il suffit de gérer les entrées qui correspondent au type de données en virgule flottante natif de votre langue.
• Vous pouvez supposer que les nombres entrés contiendront toujours un point décimal.
• Vous pouvez supposer que les entiers d'entrée se terminent par .ou .0.
• Vous pouvez utiliser des nombres complexes pour la saisie.
• La sortie doit être précise au millième près.

Exemples

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

Pour voir chaque polygone sur un plan de coordonnées, collez les coordonnées sans les crochets dans le menu "Edition" de cette page .

J'ai confirmé mes résultats en utilisant ce calculateur de points du polygone centroïde , ce qui est affreux. Je n'ai pas pu en trouver un sur lequel vous pouvez saisir tous les sommets à la fois, ou qui n'a pas essayé d'effacer votre -signe lorsque vous le tapez en premier. Je publierai ma solution Python pour votre usage après que les gens auront eu la chance de répondre.

Gelée , 25 24 22 21 18 octets

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

Applique la formule indiquée dans le problème.

Enregistré 3 octets avec l'aide de @ Jonathan Allan.

Essayez-le en ligne! ou Vérifiez tous les cas de test.

Explication

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

Mathematica, 23 octets

RegionCentroid@*Polygon

Prends ça , Jelly!

Edit: On ne bat pas simplement Jelly ...

Explication

Polygon

Générez un polygone avec des sommets aux points spécifiés.

RegionCentroid

Trouvez le centre de gravité du polygone.

J, 29 octets

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

Applique la formule indiquée dans le problème.

Usage

   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

Explication

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

Maxima, 124118116112106106 octets

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]);

Je n'ai pas d'expérience avec Maxima, donc tout indice est le bienvenu.

Usage:

(%i6) f([[-15.21,0.8], [10.1,-0.3], [-0.07,23.55]]);
(%o6)              [- 1.726666666666668, 8.016666666666668]

Raquette 420 octets

(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))

Non golfé:

(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)))

Essai:

(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)])

Production:

'(-1.7266666666666677 8.01666666666667)
'(5.8010476997538465 15.067381276150996)

R, 129 127 octets

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}

Fonction sans nom qui prend en entrée une liste R de tuples. L'équivalent nommé peut être appelé en utilisant par exemple:

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

Non golfé et expliqué

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
}

La dernière étape ( c(sum((x+X)*p),sum((y+Y)*p))/sum(p)*2/6) est une manière vectorisée de calculer à la fois Cxet Cy. La somme dans les formules pourCx et Cyest stockée dans un vecteur et par conséquent divisée par la "somme dans A" *2/6. Par exemple:

(SUMinCx, SUMinCy) / SUMinA / 3

, puis imprimé implicitement.

Essayez-le sur R-fiddle

Python, 156 127 octets

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

Non golfé:

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.

Cela prend chaque paire de points [x, y]comme un nombre complexe x + y*jet génère le centroïde résultant sous la forme d'un nombre complexe dans le même format.

Pour la paire de points [a, b]et [c, d], la valeur a*d - b*cnécessaire pour chaque paire de points peut être calculée à partir du déterminant de la matrice

| a b |
| c d |

En utilisant l'arithmétique complexe, les valeurs complexes a + b*j et c + d*jpeuvent être utilisées comme

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

Notez que la partie imaginaire est équivalente au déterminant. De plus, l'utilisation de valeurs complexes permet de sommer facilement les points par composant dans les autres opérations.

R + sp (46 octets)

Suppose que le sppackage est installé ( https://cran.r-project.org/web/packages/sp/ )

Prend une liste de sommets, (par exemple list(c(0.,0.), c(1.,0.), c(1.,1.), c(0.,1.)) )

Profite du fait que le "labpt" d'un polygone est le centroïde.

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

JavaScript (ES6), 102

Mise en œuvre directe de la formule

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]

Tester

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>

Python 2, 153 octets

N'utilise pas de nombres complexes.

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

Essayez-le en ligne

Non golfé:

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

En fait, 45 40 39 octets

Celui-ci utilise un algorithme similaire à la réponse Jelly de Miles . Il existe un moyen plus court de calculer les déterminants à l'aide d'un produit scalaire, mais il existe actuellement un bogue avec le produit scalaire d'Actually où il ne fonctionnera pas avec les listes de flottants. Suggestions de golf bienvenues. Essayez-le en ligne!

;\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.

Une version plus courte et non compétitive

Il s'agit d'une autre version de 24 octets qui utilise des nombres complexes. Il n'est pas compétitif car il repose sur des correctifs de bogues postérieurs à ce défi. Essayez-le en ligne!

;\│¥)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.

C ++ 14, 241 octets

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};}

La sortie est la structure d'aide P,

Non golfé:

 //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};
}

Usage:

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})

Clojure, 177 156 143 octets

Mise à jour: Au lieu d'un rappel, j'utilise [a b c d 1]comme fonction et l'argument est juste une liste d'index de ce vecteur. 1est utilisé comme valeur sentinelle lors du calcul A.

Mise à jour 2: pas de précalcul Aà let, en utilisant (rest(cycle %))pour obtenir un décalage d'un vecteur des vecteurs d'entrée.

#(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)))

Version originale:

#(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))]))

À l'étape moins golfée:

(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)))])))

Crée une fonction d'assistance Fqui implémente la sommation avec n'importe quel rappel l. Car Ale rappel revient constamment 1alors que les coordonnées X et Y ont leurs propres fonctions. (conj(subvec v 1)(v 0))supprime le premier élément et ajoute à la fin, de cette façon, il est facile de garder une trace de x_iet x_(i+1). Peut-être qu'il reste encore des répétitions à éliminer, surtout au dernier (map F[....