19
\$\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\$
  • \$\begingroup\$ Is input like [x1, x2, x3], [y1, y2, y3] allowed? \$\endgroup\$ – programmer5000 Jun 14 '17 at 13:34
  • \$\begingroup\$ @programmer5000 and Martin Ender , yes, I'll edit it in :) \$\endgroup\$ – JAD Jun 14 '17 at 13:35
  • \$\begingroup\$ I agree, voted to reopen. \$\endgroup\$ – programmer5000 Jun 14 '17 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\$ – Jonathan Allan Jun 14 '17 at 14:08

12 Answers 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\$
  • \$\begingroup\$ The second test-case returns ` -0.5` for me :o \$\endgroup\$ – JAD Jun 14 '17 at 13:32
  • \$\begingroup\$ Oh, I'll have to check it out... \$\endgroup\$ – Jonathan Allan Jun 14 '17 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\$ – Jonathan Allan Jun 14 '17 at 13:38
  • 1
    \$\begingroup\$ Woops, I'll edit that :D \$\endgroup\$ – JAD Jun 14 '17 at 13:39
  • 1
    \$\begingroup\$ Also, H instead of ÷2 \$\endgroup\$ – Emigna Jun 14 '17 at 13:50
29
\$\begingroup\$

Mathematica, 13 bytes

Area@*Polygon
\$\endgroup\$
  • \$\begingroup\$ Could it get more trivial? \$\endgroup\$ – Mr. Xcoder Jun 14 '17 at 19:27
  • 5
    \$\begingroup\$ @Mr.Xcoder Sure. \$\endgroup\$ – Martin Ender Jun 14 '17 at 19:27
  • \$\begingroup\$ o_O - I am literally mindblown... \$\endgroup\$ – Mr. Xcoder Jun 14 '17 at 19:28
  • 3
    \$\begingroup\$ That's Mathematica for you. Every conceivable thing is built in to the language. \$\endgroup\$ – Brian Minton Jun 15 '17 at 14:37
19
\$\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 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!

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

f=([x,y,...a])=>1/a[0]?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\$
  • \$\begingroup\$ Very impressive! Could you explain how it works? \$\endgroup\$ – Rugnir Jun 15 '17 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 '17 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 '17 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 '18 at 21:43
  • \$\begingroup\$ @Rick Thanks! Updated ... about 10 months later :/ \$\endgroup\$ – Arnauld Apr 25 '18 at 23:12
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\$
  • \$\begingroup\$ -1 byte for i+-1:0 as the row index \$\endgroup\$ – Giuseppe Jun 14 '17 at 16:29
  • \$\begingroup\$ @Giuseppe Nice. I'll remove the + as well ;) \$\endgroup\$ – JAD Jun 14 '17 at 17:38
6
\$\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\$
  • \$\begingroup\$ Taking two lists is also mentioned in the body of the question now :) \$\endgroup\$ – JAD Jun 14 '17 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 '17 at 14:37
  • \$\begingroup\$ A function returning a value counts as output :) \$\endgroup\$ – JAD Jun 14 '17 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 '17 at 14:38
  • \$\begingroup\$ @JarkoDubbeldam Are there anywhere rules for each language? \$\endgroup\$ – P. Siehr Jun 14 '17 at 14:40
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\$

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\$
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
    \$\begingroup\$ "Assuming the input is a list of 2 element lists (ie, a table)" This is allowed :) \$\endgroup\$ – JAD Jun 15 '17 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\$
1
\$\begingroup\$

Haskell, 45 bytes

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

Try it online!

\$\endgroup\$
0
\$\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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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