# Area of a 2D convex hull

You are given an array/list/vector of pairs of integers representing cartesian coordinates $$\(x, y)\$$ of points on a 2D Euclidean plane; all coordinates are between $$\−10^4\$$ and $$\10^4\$$, duplicates are allowed. Find the area of the convex hull of those points, rounded to the nearest integer; an exact midpoint should be rounded to the closest even integer. You may use floating-point numbers in intermediate computations, but only if you can guarantee that the final result will be always correct. This is , so the shortest correct program wins.

The convex hull of a set of points $$\P\$$ is the smallest convex set that contains $$\P\$$. On the Euclidean plane, for any single point $$\(x,y)\$$, it is the point itself; for two distinct points, it is the line containing them, for three non-collinear points, it is the triangle that they form, and so forth.

A good visual explanation of what a convex hulls, is best described as imagining all points as nails in a wooden board, and then stretching a rubber band around them to enclose all the points:

Some test cases:

Input: [[50, -13]]
Result: 0

Input: [[-25, -26], [34, -27]]
Result: 0

Input: [[-6, -14], [-48, -45], [21, 25]]
Result: 400

Input: [[4, 30], [5, 37], [-18, 49], [-9, -2]]
Result: 562

Input: [[0, 16], [24, 18], [-43, 36], [39, -29], [3, -38]]
Result: 2978

Input: [[19, -19], [15, 5], [-16, -41], [6, -25], [-42, 1], [12, 19]]
Result: 2118

Input: [[-23, 13], [-13, 13], [-6, -7], [22, 41], [-26, 50], [12, -12], [-23, -7]]
Result: 2307

Input: [[31, -19], [-41, -41], [25, 34], [29, -1], [42, -42], [-34, 32], [19, 33], [40, 39]]
Result: 6037

Input: [[47, 1], [-22, 24], [36, 38], [-17, 4], [41, -3], [-13, 15], [-36, -40], [-13, 35], [-25, 22]]
Result: 3908

Input: [[29, -19], [18, 9], [30, -46], [15, 20], [24, -4], [5, 19], [-44, 4], [-20, -8], [-16, 34], [17, -36]]
Result: 2905

• Do you have any test cases? – Maltysen Apr 14 at 22:12
• Not counting whitespace in code golf is a bad idea, it leads to submissions with massive strings of whitespace plus generic code to convert the string to code and execute it. – xnor Apr 14 at 22:47
• an exact midpoint should be rounded to the closest even integer: just wondering what's the reasoning behind that? – Arnauld Apr 15 at 8:47
• @nwellnhof True. But enforcing this rule is just an annoyance for languages that don't do it that way (and I think Python 2 doesn't round-to-even either). I don't think we should round at all anyway. The triangle [[0, 0], [1, 1], [0, 1]] really should yield $1/2$ rather than $0$. – Arnauld Apr 15 at 11:49
• Usually challenges are self-contained, but this one isn't. Could you explain what a convex hull is, and how to compute it? Or point to some reference online resource? – Olivier Grégoire Apr 15 at 12:04

# SQL Server 2012+, 84 bytes

SELECT Round(Geometry::ConvexHullAggregate(Geometry::Point(x,y,0)).STArea(),0)FROM A


Makes use of the geometry functions and aggregates in SQL Server. Coordindates are from table A with columns x and y.

# Java 10, 405...didn't fit anymore; see edit history..317 316 bytes

P->{int n=P.length,l=0,i=0,p,q,t[],h[][]=P.clone(),s=0;for(;++i<n;)l=P[i][0]<P[l][0]?i:l;p=l;do for(h[s++]=P[p],q=-~p%n,i=-1;++i<n;q=(t[1]-P[p][1])*(P[q][0]-t[0])<(t[0]-P[p][0])*(P[q][1]-t[1])?i:q)t=P[i];while((p=q)!=l);for(p=i=0;i<s;p-=(t[0]+h[++i%s][0])*(t[1]-h[i%s][1]))t=h[i];return Math.round(.5*p/~(p%=2))*~p;}


-52 bytes thanks to @OlivierGrégoire
-3 bytes thanks to @PeterTaylor
-7 bytes thanks to @ceilingcat

Try it online.

Explanation:

There are three steps to do:

1. Calculate the points for the Convex Hull based on the input-coordinates (using Jarvis' Algorithm/Wrapping)
2. Calculate the area of this Convex Hull
3. Banker's rounding..

To calculate the coordinates that are part of the Convex Hull, we use the following approach:

Set point $$\l\$$ and $$\p\$$ to the left-most coordinate. Then calculate the next point $$\p\$$ in a counterclockwise rotation; and continue doing so until we've reached back at the initial point $$\l\$$. Here a visual for this:

As for the code:

P->{                      // Method with 2D integer array as parameter & long return-type
int n=P.length,         //  Integer n, the amount of points in the input
l=0,                //  Integer l, to calculate the left-most point
i=0,                //  Index-integer i
p,                  //  Integer p, which will be every next counterclockwise point
q,                  //  Temp integer q
t[],                //  Temp integer-array/point
h[][]=P.clone(),    //  Initialize an array of points h for the Convex Hull
s=0;                //  And a size-integer for this Convex Hull array, starting at 0
for(;++i<n;)            //  Loop i in the range [1, n):
l=                    //   Change l to:
P[i][0]<P[l][0]?    //   If i.x is smaller than l.x:
i                  //    Replace l with the current i
:l;                 //   Else: leave l unchanged
p=l;                    //  Now set p to this left-most coordinate l
do                      //  Do:
for(h[s++]=P[p],      //   Add the p'th point to the 2D-array h
q=-~p%n,          //   Set q to (p+1) modulo-n
i=-1;++i<n;       //    Loop i in the range [0, n):
;q=               //      After every iteration: change q to:
//       We calculate: (i.y-p.y)*(q.x-i.x)-(i.x-p.x)*(q.y-i.y),
//       which results in 0 if the three points are collinear;
//       a positive value if they are clockwise;
//       or a negative value if they are counterclockwise
(t[1]-P[p][1])*(P[q][0]-t[0])<(t[0]-P[p][0])*(P[q][1]-t[1])?
//       So if the three points are counterclockwise:
i             //        Replace q with i
:q)            //       Else: leave q unchanged
t=P[i];             //     Set t to the i'th Point (to save bytes)
while((p=q)             //  And after every while-iteration: replace p with q
!=l);        //  Continue the do-while as long as p is not back at the
//  left-most point l yet
// Now step 1 is complete, and we have our Convex Hull points in the List h

for(p=i=0;              //  Set p (the area) to 0
i<s                 //  Loop i in the range [0, s):
;p-=                //    After every iteration: Decrease the area p by:
(t[0]+h[++i%s][0])//     i.x+(i+1).x
*(t[1]-h[i%s][1]))//     Multiplied by i.y-(i+1).y
t=h[i];               //   Set t to the i'th point (to save bytes)
return Math.round(.5*p/~(p%=2))*~p;}
//  And return p/2 rounded to integer with half-even


# Wolfram Language (Mathematica), 27 bytes

Round@*Area@*ConvexHullMesh


Try it online!

# JavaScript (ES6),  191  189 bytes

Implements the Jarvis march (aka gift wrapping algorithm).

P=>(r=(g=p=>([X,Y]=P[p],Y*h-X*v)+(P.map(([x,y],i)=>q=(y-Y)*(P[q][0]-x)<(x-X)*(P[q][1]-y)?i:q,q=P[++p]?p:0,h=X,v=Y)|q?g(q):V*h-H*v))(v=h=0,([[H,V]]=P.sort(([x],[X])=>x-X)))/2)+(r%1&&r&1)/2|0


Try it online!

Or 170 bytes without the cumbersome rounding scheme.

• Rounding was just a red herring because twice the area is always exactly integer. – Vladimir Reshetnikov Apr 15 at 14:00
• @VladimirReshetnikov Out of curiosity: if you knew rounding was a red herring, then why add it to distract from the otherwise good challenge?.. Not all languages have builtin Banker's rounding, not even well-known languages like JS and Java apparently. I like the challenge in general and enjoyed writing my Java answer, but the rounding and lack of explanation what Convex Hull is to make the challenge self-contained refrained me from upvoting it, tbh.. PS: Sorry @Arnauld to do this as a comment in your answer.. – Kevin Cruijssen Apr 15 at 14:24

# R, 8581 78 bytes

function(i,h=chull(i),j=c(h,h[1]))round((i[h,1]+i[j[-1],1])%*%diff(-i[j,2])/2)


Try it online!

Takes input as a 2-column matrix - first for x, second for y. R's round actually uses banker's rounding method, so we are quite lucky here.

The code uses a built-in function to determine, which points form the convex hull, and then applies the standard formula $$\\sum_{i}{(x_{i-1}+x)\cdot(y_{i-1}-y_i)}/2\$$ to get the polygon surface area.

Thanks to Giuseppe for -3 bytes.

# [R + sp package], 55 bytes

function(x)round(sp::Polygon(x[chull(x),,drop=F])@area)


Try it at RDRR

A function which takes a n x 2 matrix and returns the rounded area. This uses the sp package. The drop=F is needed to handle the one co-ordinate case. RDRR used for demo since TIO lacks the sp package.