Codegolf - Найдите Центроид Многоугольника

От Википедия:

Центр тяжести несамопересекающегося замкнутого многоугольника. определяетсян₀вершины (₀), (х₁, да₁), ..., (х_{, да}х_n−1, даn−1_{) — это точка (}С_х,

С й

), где и где_А- подписанная площадь многоугольника,_{В этих формулах предполагается, что вершины пронумерованы в порядке} их расположение по периметру многоугольника. Кроме того,₀₀ вершина ( х н , дан ) предполагается таким же, как

• (
  • х
• , да
• ), значение
• я + 1
• по последнему делу

•  - 

  or [(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 .
• должен зацикливаться на
• я = 0

. Обратите внимание: если точки пронумерованы

по часовой стрелке упорядочить площадь.

А , рассчитанный, как указано выше, будет иметь отрицательное значение . sign when you type it first. I'll post my Python solution for your use after people have had a chance to answer.

знак; но координаты центроида будут правильными даже в этом случае.

Математика, 23 байта

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 (map F[... 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Брать ЧТО, Джелли!

Редактировать: невозможно просто победить Джелли...

Объяснение

Создайте многоугольник с вершинами в указанных точках.

Найдите центр тяжести многоугольника.

Желе, 25 24 22 21 18 байт

Применяет формулу, показанную в задаче.

Сэкономлено 3 байта с помощью @Джонатан Аллан.

Попробуйте онлайн! или Проверьте все тестовые примеры.

Объяснение

Дж, 29 байт

Применяет формулу, показанную в задаче.

Использование

Объяснение

Максима, 124 118 116 112 106 байт

У меня нет опыта работы с Maxima, поэтому любые намеки приветствуются.

Использование:

Ракетка 420 байт

Не в гольфе:

Тестирование:

Выход:

Р, 129 127 байт

Безымянная функция, которая принимает на вход R-список кортежей. Именованный эквивалент можно вызвать, например:

Ungolfed и объяснено

Последний шаг( 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}) ) is a vectorized way of calculating both //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}; } и P . The sum in the formulas for 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};} и 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. are stored in a vector and consequently divided by the "sum in ;\│¥)Z`iá*╫@X`M;Σ3*)♀*Σ/ " 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. . E.g.:

, а затем неявно напечатано.

Попробуйте это на R-fiddle

Питон, 156 127 байт

Не в гольфе:

Идея это.

Это требует каждой пары очков <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> as a complex number #I { width:90% } #C { width:90%; height:200px;} и выводит полученный центроид как комплексное число в том же формате.

За пару очков 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+' 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() и 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(l)sp::Polygon(do.call(rbind,l))@labpt which is needed for each pair of points can be computed from the determinant of the matrix

Используя сложную арифметику, комплексные значения sp and conjugate(a + b*j) * (c + d*j) (a - b*j) * (c + d*j) (a*c + b*d) + (a*d - b*c)*j может использоваться как

Обратите внимание, что мнимая часть эквивалентна определителю. Кроме того, использование комплексных значений позволяет легко суммировать точки покомпонентно в других операциях.

R + sp (46 байт)

Предполагает a + b*j package is installed (https://cran.r-project.org/web/packages/sp/)

Принимает список вершин (например | a b | | c d | )

Использует тот факт, что «labpt» полигона является центроидом.

JavaScript (ES6), 102

Прямая реализация формулы

Тест

Питон 2, 153 байта

Не использует комплексные числа.

Попробуйте онлайн

Не в гольфе:

На самом деле 45 40 39 байт

Здесь используется алгоритм, аналогичный ответ Майлза Джелли. Существует более короткий способ вычисления определителей с использованием скалярного произведения, но в настоящее время существует ошибка в скалярном произведении Фактически, из-за которой оно не работает со списками чисел с плавающей запятой. Предложения по игре в гольф приветствуются. Попробуйте онлайн!

Унгольфинг

Более короткая, неконкурентная версия.

Это еще одна 24-байтовая версия, в которой используются комплексные числа. Оно неконкурентноспособно, поскольку основано на исправлениях ошибок, появившихся после этого испытания. Попробуйте онлайн!

Унгольфинг

С++14, 241 байт

Результатом является вспомогательная структура Cy ,

Не в гольфе:

Использование:

Clojure, 177 156 143 байт

Обновление: вместо обратного вызова я использую 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 } as a function and the argument is just a list of indexes to this vector. f(list(c(-15.21,0.8),c(10.1,-0.3),c(-0.07,23.55))) используется в качестве контрольного значения при расчете 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} .

Обновление 2: отсутствие предварительных расчетов '(-1.7266666666666677 8.01666666666667) '(5.8010476997538465 15.067381276150996) at (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)]) , с использованием (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))) to get input vectors offset by one.

Оригинальная версия:

На менее играющей в гольф стадии:

Создает вспомогательную функцию 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 which implements the summation with any callback 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 . Для 2+/@(+/\(*%3*1#.])-/ .*\)],{. the callback returns constantly 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 тогда как координаты X и Y имеют свои собственные функции. S×3÷@×" ṙ-żµÆḊçS€S drops the first element and appends to the end, this way it is easy to keep track of RegionCentroid and Polygon . Maybe there is still some repetition to be eliminated, especially at the last RegionCentroid@*Polygon .