21
\$\begingroup\$

Calculate the area of a polygon.

Inspired by this shoelace algorithm video.

Task

Your job is to create a program or function that calculates the area of a polygon. Program or function is defined according the the default definition in meta.

Input

You will receive the X and Y coordinates of each vertex of the polygon. You can take the input as a list of tuples ([[x1, y1], [x2, y2], etc]), a matrix, or a flat list ([x1, y1, x2, y2, etc]). Two lists containing x and y coordinates respectively are allowed as well. The vertices are numbered counterclockwise and the first vertex is the same as the last vertex provided, thus closing the polygon.

If you want you can take the input without the last vertex (so receive each coordinate just once).

You can assume that the edges of the polygons don't intersect. You can also assume that all vertices have integer coordinates.

Output

The area of the polygon. All standard output methods are allowed. If your language does not allow for float division and the solution would not be an integer, you are allowed to return a fraction. The fraction does not necessarily have to be simplified, so returning 2/4 would be allowed.

Winning criterium

Shortest code wins!

Test cases

[[4,4],[0,1],[-2,5],[-6,0],[-1,-4],[5,-2],[4,4]]
55

enter image description here

[[1,1],[0,1],[1,0],[1,1]]
0.5
1/2

enter image description here

\$\endgroup\$
4
  • \$\begingroup\$ Is input like [x1, x2, x3], [y1, y2, y3] allowed? \$\endgroup\$
    – user58826
    Jun 14, 2017 at 13:34
  • \$\begingroup\$ @programmer5000 and Martin Ender , yes, I'll edit it in :) \$\endgroup\$
    – JAD
    Jun 14, 2017 at 13:35
  • \$\begingroup\$ I agree, voted to reopen. \$\endgroup\$
    – user58826
    Jun 14, 2017 at 13:53
  • 1
    \$\begingroup\$ @flawr I made that a dupe of this. It is not really a dupe of its dupe target, which to apply the same method as here recursively would require finding the vertices that are crossing points and would require ordering the resulting subsets into counter-clockwise fashion - that seems much more complex. \$\endgroup\$ Jun 14, 2017 at 14:08

19 Answers 19

30
\$\begingroup\$

Mathematica, 13 bytes

Area@*Polygon
\$\endgroup\$
4
  • \$\begingroup\$ Could it get more trivial? \$\endgroup\$
    – Mr. Xcoder
    Jun 14, 2017 at 19:27
  • 7
    \$\begingroup\$ @Mr.Xcoder Sure. \$\endgroup\$ Jun 14, 2017 at 19:27
  • 1
    \$\begingroup\$ o_O - I am literally mindblown... \$\endgroup\$
    – Mr. Xcoder
    Jun 14, 2017 at 19:28
  • 3
    \$\begingroup\$ That's Mathematica for you. Every conceivable thing is built in to the language. \$\endgroup\$ Jun 15, 2017 at 14:37
21
\$\begingroup\$

Octave, 9 bytes

@polyarea

Inputs are a vector with the x values and a vector with the y values. This works in MATLAB too.

Try it online!

\$\endgroup\$
16
\$\begingroup\$

JavaScript (ES6),  69 67 47  44 bytes

Thanks to @Rick for noticing that we don't need the absolute value if the vertices are guaranteed to be sorted in counterclockwise order and for suggesting to take a flat list as input, saving 20 bytes!
Saved 3 more bytes thanks to @Shaggy

Takes input as a flat list of vertices, including the last vertex.

f=([x,y,...a])=>a+a?x*a[1]/2-y*a[0]/2+f(a):0

Try it online!

How?

This is based on the formula used in many other answers. For \$n\$ 0-indexed vertices:

$$area=\left|\frac{(x_0y_1-y_0x_1)+(x_1y_2-y_1x_2)+\ldots+(x_{n-1}y_0-y_{n-1}x_0)}{2}\right|$$

\$\endgroup\$
7
  • \$\begingroup\$ Very impressive! Could you explain how it works? \$\endgroup\$
    – Rugnir
    Jun 15, 2017 at 14:40
  • \$\begingroup\$ The vertices in the second test case were mistakenly ordered incorrectly. The abs shouldn't be necessary. \$\endgroup\$
    – Rick
    Jun 15, 2017 at 17:42
  • \$\begingroup\$ You can also save 7 bytes switching to a flat list: a=>(g=([x,y,...a])=>1-a?0:x*a[1]-y*a[0]+g(a))(a)/2 \$\endgroup\$
    – Rick
    Jun 15, 2017 at 18:42
  • \$\begingroup\$ @Rick is right - abs isn't necessary. Without it the formula calculates the signed area, which is positive because the vertices are given in the counterclockwise order. \$\endgroup\$
    – Angs
    Apr 25, 2018 at 21:43
  • \$\begingroup\$ @Rick Thanks! Updated ... about 10 months later :/ \$\endgroup\$
    – Arnauld
    Apr 25, 2018 at 23:12
13
\$\begingroup\$

Jelly,  8  6 bytes

-1 byte thanks to Emigna (redundant , ÆḊ has a left-depth of 2)
-1 byte thanks to Emigna, again (halve, H, is floating point no need to ÷2)

ṡ2ÆḊSH

A monadic link taking a list of pairs of coordinates in counter-clockwise fashion as per the examples (with the one repeat) and returning the area.

Try it online!

How?

Applies the shoelace algorithm, just as described in the video (which I happened to also watch just the other day!)

ṡ2ÆḊSH - Link: list of [x,y] coordinate pairs anticlockwise & wrapped, p
ṡ2     - all overlapping slices of length 2
  ÆḊ   - determinant (vectorises)
    S  - sum
     H - halve
\$\endgroup\$
7
  • \$\begingroup\$ The second test-case returns ` -0.5` for me :o \$\endgroup\$
    – JAD
    Jun 14, 2017 at 13:32
  • \$\begingroup\$ Oh, I'll have to check it out... \$\endgroup\$ Jun 14, 2017 at 13:33
  • \$\begingroup\$ That's because as [x,y] coordinates they are given clockwise rather than counter-clockwise. An input of [[1,1],[0,1],[1,0],[1,1]] will return a 0.5. \$\endgroup\$ Jun 14, 2017 at 13:38
  • 1
    \$\begingroup\$ Woops, I'll edit that :D \$\endgroup\$
    – JAD
    Jun 14, 2017 at 13:39
  • 1
    \$\begingroup\$ Also, H instead of ÷2 \$\endgroup\$
    – Emigna
    Jun 14, 2017 at 13:50
7
\$\begingroup\$

Python 3, 72 71 bytes

from numpy import*
g=lambda x,y:(dot(x[:-1],y[1:])-dot(x[1:],y[:-1]))/2

Takes two lists, as it was allowed in the comments

x = [x0,x1,x2, ...]
y = [y0,y1,y2, ...] 

Try it online!

This is basically just the implementation of the shoelace-formula. May I get plus points for a golf that you actually would implement like that? :D

-1, there is no need for a space behind x,y:.


\$\endgroup\$
9
  • \$\begingroup\$ Taking two lists is also mentioned in the body of the question now :) \$\endgroup\$
    – JAD
    Jun 14, 2017 at 14:34
  • \$\begingroup\$ @JarkoDubbeldam Uh, I just saw, that it has to output the area. This solution currently just returns the area. Is that allowed as well, or shall it be printed? \$\endgroup\$
    – P. Siehr
    Jun 14, 2017 at 14:37
  • \$\begingroup\$ A function returning a value counts as output :) \$\endgroup\$
    – JAD
    Jun 14, 2017 at 14:37
  • \$\begingroup\$ I think that with python you don't even have to name the function, so just starting with lambda x,y: is fine. \$\endgroup\$
    – JAD
    Jun 14, 2017 at 14:38
  • \$\begingroup\$ @JarkoDubbeldam Are there anywhere rules for each language? \$\endgroup\$
    – P. Siehr
    Jun 14, 2017 at 14:40
7
\$\begingroup\$

R, 54 52 bytes

pryr::f({for(i in 2:nrow(x))F=F+det(x[i-1:0,]);F/2})

Which evaluates to the function:

function (x) 
{
    for (i in 2:nrow(x)) F = F + det(x[i - 1:0, ])
    F/2
}

Makes use of the predefined F = FALSE = 0. Implements the shoelace algorithm in the linked video :)

-2 bytes thanks to Giuseppe

\$\endgroup\$
2
  • \$\begingroup\$ -1 byte for i+-1:0 as the row index \$\endgroup\$
    – Giuseppe
    Jun 14, 2017 at 16:29
  • \$\begingroup\$ @Giuseppe Nice. I'll remove the + as well ;) \$\endgroup\$
    – JAD
    Jun 14, 2017 at 17:38
6
\$\begingroup\$

Mathics, 31 bytes

Total[Det/@Partition[#,2,1]/2]&

Try it online!


Mathematica, 25 bytes

Tr@BlockMap[Det,#,2,1]/2&
\$\endgroup\$
4
\$\begingroup\$

Factor, 35 bytes

[ dup pick [ rest v. ] 2bi@ - 2 / ]

Try it online!

Takes two arrays of x- and y-coordinates on the top of the stack, and returns the area as an integer or a rational.

Exploits the vector dot product v. which ignores excess elements on either side, so calculating one side of the shoelace is as simple as "remove the first element from the top array, and compute the dot product". And we can reuse it to evaluate the other side of the shoelace by simply swapping the two input arrays.

Honorable mention goes to the Apply combinator 2bi@, which lets us simplify multi-application of the inner function.

Input:
{ 4 0 -2 -6 -1  5 4 }
{ 4 1  5  0 -4 -2 4 }
Remove the first element from top:
{ 4 0 -2 -6 -1 5 4 }
{ 1 5  0 -4 -2 4 }
Evaluate the dot product (sum of elementwise product, ignoring any excess element)

[                  ! Input: ( x y )
  dup pick         ! Copy stack items to form ( x y y x )
  [ rest v. ]      ! The function that evaluates one side of shoelace
  2bi@             ! Apply the above to ( x y ), then to ( y x )
  - 2 /            ! Subtract the two and halve
]
\$\endgroup\$
3
\$\begingroup\$

JS (ES6), 98 95 94 93 88 86 82 81 77 73 bytes

(X,Y)=>{for(i in X){a+=(X[i]+X[i-1])*(Y[i]-Y[i-1]);if(!+i)a=0}return a/2}

Takes input like [x1, x2, x3], [y1, y2, y3], and skips the repeated coord pair.

-3 bytes thanks to @JarkoDubbeldam

-4 bytes thanks to @JarkoDubbeldam

-1 byte thanks to @ZacharyT

-4 bytes thanks to @ZacharyT

-4 bytes thanks to @Rick

\$\endgroup\$
0
3
\$\begingroup\$

J, 12 bytes

Assuming the input is a list of 2 element lists (ie, a table)

-:+/-/ .*2[\
  • 2[\ -- breaks it down into the shoelace Xs, ie, overlapping squares of 4 elms
  • -/ .* -- the determinant of each
  • +/ -- sum it
  • -: -- divide by 2

If we get the input as a single list, we need to first transform into a table, giving us 20 bytes:

-:+/-/ .*2[\ _2&(,\)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ "Assuming the input is a list of 2 element lists (ie, a table)" This is allowed :) \$\endgroup\$
    – JAD
    Jun 15, 2017 at 7:20
3
\$\begingroup\$

MS-SQL, 66 bytes

SELECT geometry::STPolyFromText('POLYGON('+p+')',0).STArea()FROM g

MS SQL 2008 and higher support Open Geospatial Consortium (OGC)-standard spatial data/functions, which I'm taking advantage of here.

Input data is stored in field p of pre-existing table g, per our input standards.

Input is a text field with ordered pairs in the following format: (4 4,0 1,-2 5,-6 0,-1 -4,5 -2,4 4)

Now just for fun, if you allowed my input table to hold Open Geospatial Consortium-standard geometry objects (instead of just text data), then it becomes almost trivial:

--Create and populate input table, not counted in byte total
CREATE TABLE g (p geometry)
INSERT g VALUES (geometry::STPolyFromText('POLYGON((5 5, 10 5, 10 10, 5 5))', 0))

--23 bytes!
SELECT p.STArea()FROM g
\$\endgroup\$
2
\$\begingroup\$

Haskell, 45 bytes

(a:b:c)?(d:e:f)=(a*e-d*b)/2+(b:c)?(e:f)
_?_=0

Try it online!

\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Extended), 14 bytes

2÷⍨1⊥2-/⍤×∘⌽/⊢

Try it online!

Same formula as in Arnauld's answer.

Takes input as a list of points, sorted in counterclockwise order.

Explanation

2÷⍨1⊥2-/⍤×∘⌽/⊢
             ⊢ take the input (list of pts)
     2      /  reduce overlapping pairs by the following function:
         ×       multiply the first
          ∘⌽     with the second reversed
      -/⍤        reduce the multipled pair by subraction
   1⊥          sum the resultant array (using decoding)
2÷⍨            halve it
\$\endgroup\$
2
\$\begingroup\$

PARI/GP 61 bytes

c=concat;s(z,v=1)=c(z,z)[^#x*2]+c(z[^1],z)*v
s(x,-1)*s(y)~/4

assumes coordinates given by two vectors x=[x1,...xn], y=[y1,...,yn]

Test cases

A(x,y)={my(c=concat,s(z,v=1)=c(z,z)[^#x*2]+c(z[^1],z)*v);s(x,-1)*s(y)~/4};
A([1, 0, 1, 1],[1, 1, 0, 1])
1/2
A([4,0,-2,-6,-1,5,4],[4,1,5,0,-4,-2,4])
55
\$\endgroup\$
2
\$\begingroup\$

PHP, 76 75 73 bytes

Well, i probably shoot myself in the knee with PHP and his $ prefix for variable but i just wanna try the challenge with it anyway.

Header just remove error reporting for conviniance and format input as 2 array like it's allowed in post... i was just lazzy to retype it myself XD. (you can test both case by switching var in the for loop)

Edit: Figure out i can pass 2 arg to for() and save carac from while keyword with the same logic

Edit : Saved 2 bytes by reverse the iteration order and use juste $i for condition, saved <0 (need to substract for 2nd option since result will be negative otherwise, but same bytes length)

for($i=count($x);$i;){$s-=$x[$j=$i--]*$y[$i]-$y[$j]*$x[$i];}$s=abs($s)/2;

Try it online!

PHP, 67 66 64 bytes

Solution without the abs() who work on both given case but feel like cheat since can return negative values in some cases ^^'

for($i=count($x);$i;){$s-=($x[$j=$i--]*$y[$i]-$y[$j]*$x[$i])/2;}

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! Don't worry about $s being ungolfy, scoring is by language here. \$\endgroup\$ Oct 24, 2022 at 18:28
1
\$\begingroup\$

Perl 5 -pa, 62 bytes

map$\+=$F[$i]*($a[($i+1)%@a]-$a[$i++-1]),@a=eval<>}{$\=abs$\/2

Try it online!

Takes input as a list of X coordinates on the first line followed by a list of Y coordinates on the second.

\$\endgroup\$
1
\$\begingroup\$

R, 51 46 bytes

Edit: save 5 more bytes since no need to take abs() if points always encircle the polygon in counter-clockwise fashion

pryr::f(sum(x*(1:0-.5)*x[2:1,c(2:ncol(x),1)]))

Try it online!

After 3 years, 1 6 bytes shaved from the previously-best R solution!

\$\endgroup\$
1
\$\begingroup\$

Python 3, 58 bytes

lambda x,y:sum(x[i-1]*(j-y[i-2])/2for i,j in enumerate(y))

Try it online!

Implementation of the shoelace algorithm.

\$\endgroup\$
1
\$\begingroup\$

Excel, 97 bytes

=LET(a,A1#,x,ROW(a),y,{2,1},b,IF(x=ROWS(a),INDEX(a,1,y),INDEX(a,x+1,y)),SUM(MMULT(a*b,{1;-1}))/2)

LET and dynamic arrays were not Excel features in 2017.

\$\endgroup\$
1
  • \$\begingroup\$ It may be worth noting that the input has to be an array in a formula like this ={4,4;0,1;-2,5;-6,0;-1,-4;5,-2;4,4} \$\endgroup\$ Oct 24, 2022 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.