How to use the convex hull calculator
- Paste your points, one per line, as x and y separated by a comma, a space or a tab. Repeated points are counted once.
- Leave the box unticked to list only true corners. Tick it to count points that lie on an edge as corners too.
- Read the hull area, the perimeter, the number of corners, how many points are inside and how many lie on an edge.
- The table lists the corners in counterclockwise order starting from the leftmost point.
Formula
cross(o, a, b) = (a.x - o.x)(b.y - o.y) - (a.y - o.y)(b.x - o.x)
build the lower and upper chains over points sorted by x, dropping a point when the last three do not turn left
area = |sum(x_i y_(i+1) - x_(i+1) y_i)| / 2
perimeter = sum of the corner-to-corner distances
This is Andrew's monotone chain algorithm. Sorting dominates the work, so many thousands of points are no problem.
A rectangle with points inside and on its edges
The points (0, 0), (4, 0), (4, 3), (0, 3), (2, 1), (1, 2), (2, 3), (3, 1.5) and (4, 1) give a hull with the four corners of a 4 by 3 rectangle. The area is 12 and the perimeter is 14. Three points are inside, and two lie on the edges: (2, 3) on the top and (4, 1) on the right side.
With the corner box ticked, the hull has 6 corner points. A second set of eight different points, (0, 0), (3, 0), (5, 2), (4, 5), (1, 4), (2, 2), (3, 3) and (-1, 2), gives a six-corner hull with an area of 20 and a perimeter of 17.2175.
What a convex hull is
The convex hull of a set of points is the smallest convex shape that contains all of them. A way to picture it is a rubber band stretched around nails in a board: the band touches only the outermost nails, and those are the corners. A shape is convex if the straight line between any two of its points stays inside it.
The hull is useful for outlining a cloud of points, for finding the farthest pair of points, for the bounding area of survey or map points and for removing points that cannot matter. When every point lies on one line, the hull has no area, and the tool says so.
Collinear points
Points that lie exactly on an edge between two corners are a matter of choice. By default they are not corners, since removing them does not change the shape. The box lets you keep them. The area and perimeter are the same either way. For the area of a shape that is not convex, use the polygon area from coordinates calculator, and for regular shapes see the regular polygon properties calculator and the area calculator.
Assumptions and limits
- Coordinates are in a flat plane with one unit for both axes. Latitude and longitude are not converted.
- Up to 5,000 points are accepted, with at least 3.
- Points that match exactly are merged. Points a tiny fraction apart are treated as different.
- If all points are on one line, the area is 0 and the perimeter counts the segment twice.
Frequently asked questions
Does the order of the points matter?
No. The points are sorted first, so any order gives the same hull. The corners are always listed counterclockwise from the leftmost point.
Why is the perimeter of a line segment twice its length?
A hull with two corners is a segment that is walked there and back, so its perimeter counts both ways. The area of such a hull is zero.
Can I use map coordinates?
Only if they are in a flat system such as meters on a grid. Over short distances you can use latitude and longitude as plain numbers for the outline, but the area will not be in real units.
What is the difference between inside and on-edge points?
Inside points are strictly within the hull. On-edge points lie exactly on a side between two corners. Both are counted separately so that corners, edge points and inside points add up to the number of different points.