Shoelace formula for polygonal area

From Rosetta Code
Task
Shoelace formula for polygonal area
You are encouraged to solve this task according to the task description, using any language you may know.

Write a function/method/routine to use the the Shoelace formula to calculate the area of the polygon described by the ordered points:

    (3,4), (5,11), (12,8), (9,5), and (5,6)

Show the answer here, on this page.


ALGOL 68[edit]

BEGIN
# returns the area of the polygon defined by the points p using the Shoelace formula #
OP AREA = ( [,]REAL p )REAL:
BEGIN
[,]REAL points = p[ AT 1, AT 1 ]; # normalise array bounds to start at 1 #
IF 2 UPB points /= 2 THEN
# the points do not have 2 coordinates #
-1
ELSE
REAL result := 0;
INT n = 1 UPB points;
IF n > 1 THEN
# there at least two points #
[]REAL x = points[ :, 1 ];
[]REAL y = points[ :, 2 ];
FOR i TO 1 UPB points - 1 DO
result +:= x[ i ] * y[ i + 1 ];
result -:= x[ i + 1 ] * y[ i ]
OD;
result +:= x[ n ] * y[ 1 ];
result -:= x[ 1 ] * y[ n ]
FI;
( ABS result ) / 2
FI
END # AREA # ;
 
# test case as per the task #
print( ( fixed( AREA [,]REAL( ( 3.0, 4.0 ), ( 5.0, 11.0 ), ( 12.0, 8.0 ), ( 9.0, 5.0 ), ( 5.0, 6.0 ) ), -6, 2 ), newline ) )
END
 
Output:
 30.00

J[edit]

Implementation:

shoelace=:verb define
0.5*|+/((* 1&|.)/ - (* _1&|.)/)|:y
)

Task example:

   shoelace 3 4,5 11,12 8,9 5,:5 6
30

Exposition:

We start with our list of coordinate pairs

   3 4,5 11,12 8,9 5,:5 6
3 4
5 11
12 8
9 5
5 6

But the first thing we do is transpose them so that x coordinates and y coordinates are the two items we are working with:

   |:3 4,5 11,12 8,9 5,:5 6
3 5 12 9 5
4 11 8 5 6

We want to rotate the y list by one (in each direction) and multiply the x list items by the corresponding y list items. Something like this, for example:

   3 5 12 9 5* 1|.4 11 8 5 6
33 40 60 54 20

Or, rephrased:

   (* 1&|.)/|:3 4,5 11,12 8,9 5,:5 6
33 40 60 54 20

We'll be subtracting what we get when we rotate in the other direction, which looks like this:

   ((* 1&|.)/ - (* _1&|.)/)|:3 4,5 11,12 8,9 5,:5 6
15 20 _72 _18 _5

Finally, we add up that list, take the absolute value (there are contexts where signed area is interesting - for example, some graphics application - but that was not a part of this task) and divide that by 2.

Kotlin[edit]

// version 1.1.3
 
class Point(val x: Int, val y: Int) {
override fun toString() = "($x, $y)"
}
 
fun shoelaceArea(v: List<Point>): Double {
val n = v.size
var a = 0.0
for (i in 0 until n - 1) {
a += v[i].x * v[i + 1].y - v[i + 1].x * v[i].y
}
return Math.abs(a + v[n - 1].x * v[0].y - v[0].x * v[n -1].y) / 2.0
}
 
fun main(args: Array<String>) {
val v = listOf(
Point(3, 4), Point(5, 11), Point(12, 8), Point(9, 5), Point(5, 6)
)
val area = shoelaceArea(v)
println("Given a polygon with vertices at $v,")
println("its area is $area")
}
Output:
Given a polygon with vertices at [(3, 4), (5, 11), (12, 8), (9, 5), (5, 6)],
its area is 30.0

Perl 6[edit]

Index and mod offset[edit]

Works with: Rakudo version 2017.07
sub area-by-shoelace(@p) {
(^@p).map({@p[$_;0] * @p[($_+1)%@p;1] - @p[$_;1] * @p[($_+1)%@p;0]}).sum.abs / 2
}
 
say area-by-shoelace( [ (3,4), (5,11), (12,8), (9,5), (5,6) ] );
Output:
30

Slice and rotation[edit]

Works with: Rakudo version 2017.07
sub area-by-shoelace ( @p ) {
my @x := @p».[0];
my @y := @p».[1];
 
my $s := ( @x Z* @y.rotate( 1) ).sum
- ( @x Z* @y.rotate(-1) ).sum;
 
return $s.abs / 2;
}
 
say area-by-shoelace( [ (3,4), (5,11), (12,8), (9,5), (5,6) ] );
 
Output:
30

Python[edit]

>>> def area_by_shoelace(x, y):
"Assumes x,y points go around the polygon in one direction"
return abs( sum(i * j for i, j in zip(x, y[1:] + y[:1]))
-sum(i * j for i, j in zip(x[1:] + x[:1], y ))) / 2
 
>>> points = [(3,4), (5,11), (12,8), (9,5), (5,6)]
>>> x, y = zip(*points)
>>> area_by_shoelace(x, y)
30.0
>>>

Racket[edit]

#lang racket/base
 
(struct P (x y))
 
(define (area . Ps)
(define (A P-a P-b)
(+ (for/sum ((p_i Ps)
(p_i+1 (in-sequences (cdr Ps)
(in-value (car Ps)))))
(* (P-a p_i) (P-b p_i+1)))))
(/ (abs (- (A P-x P-y) (A P-y P-x))) 2))
 
(module+ main
(area (P 3 4) (P 5 11) (P 12 8) (P 9 5) (P 5 6)))
Output:
30

REXX[edit]

/*REXX program uses a  Shoelace  formula to calculate the area of an  N-sided  polygon. */
parse arg pts /*obtain optional arguments from the CL*/
if pts='' then pts= '(3,4),(5,11),(12,8),(9,5),(5,6)' /*Not specified? Use default. */
pts=space(pts, 0); @=pts /*elide extra blanks; save pts.*/
do n=1 until @='' /*perform destructive parse on @*/
parse var @ '(' x.n ',' y.n ")" ',' @ /*obtain X and Y coördinates*/
end /*n*/
A=0 /*initialize the area to zero.*/
do j=1 for n; jp=j+1; if jp>n then jp=1 /*adjust for J for overflow. */
jm=j-1; if jm==0 then jm=n /* " " " " underflow. */
A=A + x.j * (y.jp - y.jm) /*compute a part of the area. */
end /*j*/
A=abs(A/2) /*obtain half of the │ A │ sum*/
say 'polygon area of ' n " points: " pts ' is ───► ' A /*stick a fork in it, we're done*/
output   when using the default input:
polygon area of  5  points:  (3,4),(5,11),(12,8),(9,5),(5,6)   is ───►  30

Scala[edit]

case class Point( x:Int,y:Int ) { override def toString = "(" + x + "," + y + ")" }
 
case class Polygon( pp:List[Point] ) {
require( pp.size > 2, "A Polygon must consist of more than two points" )
 
override def toString = "Polygon(" + pp.mkString(" ", ", ", " ") + ")"
 
def area = {
 
// Calculate using the Shoelace Formula
val xx = pp.map( p => p.x )
val yy = pp.map( p => p.y )
val overlace = xx zip yy.drop(1)++yy.take(1)
val underlace = yy zip xx.drop(1)++xx.take(1)
 
(overlace.map( t => t._1 * t._2 ).sum - underlace.map( t => t._1 * t._2 ).sum).abs / 2.0
}
}
 
// A little test...
{
val p = Polygon( List( Point(3,4), Point(5,11), Point(12,8), Point(9,5), Point(5,6) ) )
 
assert( p.area == 30.0 )
 
println( "Area of " + p + " = " + p.area )
}
 
Output:
Area of Polygon( (3,4), (5,11), (12,8), (9,5), (5,6) ) = 30.0

zkl[edit]

By the "book":

fcn areaByShoelace(points){	// ( (x,y),(x,y)...)
xs,ys:=Utils.Helpers.listUnzip(points); // (x,x,...), (y,y,,,)
( xs.zipWith('*,ys[1,*]).sum(0) + xs[-1]*ys[0] -
xs[1,*].zipWith('*,ys).sum(0) - xs[0]*ys[-1] )
.abs().toFloat()/2;
}

or an iterative solution:

fcn areaByShoelace2(points){	// ( (x,y),(x,y)...)
xs,ys:=Utils.Helpers.listUnzip(points); // (x,x,...), (y,y,,,)
N:=points.len();
N.reduce('wrap(s,n){ s + xs[n]*ys[(n+1)%N] - xs[(n+1)%N]*ys[n] },0)
.abs().toFloat()/2;
}
points:=T(T(3,4), T(5,11), T(12,8), T(9,5), T(5,6));
areaByShoelace(points).println();
areaByShoelace2(points).println();
Output:
30
30