4 kyu

Convex hull area

134 of 177kingcobra

Description:

Let's say you have a bunch of points, and you want to round them all up and calculate the area of the smallest polygon containing all of the points (nevermind why, you just want a challenge). What you're looking for is the area of the convex hull of these points. Here is an example, delimited in blue :

Your task

Implement a function that will compute the area covered by the convex hull that can be formed from an array of points, the area being rounded to two decimal places. The points are given as (x,y), like in an orthonormal coordinates system.

points = [(0, 0), (0, 3), (4, 0)]
convex_hull_area(points) == 6.00
double[][] points = {{0, 0}, {0, 3}, {4, 0}};
assertEquals(6, ConvexHull.getArea(points), 1e-14);

Note : In Python, the scipy module has a ready made solution for this. Of course, if you use it here, you are lame.

P. S. : If you enjoy this kata, you may also like this one, which asks you to compute a convex hull, without finding its area.

Geometry
Algorithms

Stats:

CreatedSep 20, 2017
PublishedSep 25, 2017
Warriors Trained958
Total Skips444
Total Code Submissions906
Total Times Completed177
Python Completions134
Java Completions46
Total Stars35
% of votes with a positive feedback rating93% of 69
Total "Very Satisfied" Votes62
Total "Somewhat Satisfied" Votes4
Total "Not Satisfied" Votes3
Total Rank Assessments3
Average Assessed Rank
4 kyu
Highest Assessed Rank
4 kyu
Lowest Assessed Rank
5 kyu
Ad
Contributors
  • kingcobra Avatar
  • smile67 Avatar
  • Blind4Basics Avatar
  • hobovsky Avatar
Ad