Convex Hull Calculator

Related Calculators

• Triangle Centers Calculator
• Voronoi Diagram Calculator
• Circle Packing Calculator
• Ellipse Calculator

What Is a Convex Hull?

A convex hull is the smallest convex shape that contains a set of points. In two dimensions, it is usually a polygon whose corners are chosen from the original points. A common way to picture it is to imagine stretching a rubber band around all the points and letting it snap tight. The points touched by the band become the hull vertices, while the remaining points lie inside the boundary or along edges that are not kept as separate vertices.

A shape is convex when a straight line segment between any two points in the shape stays completely inside the shape. That condition is what makes the convex hull useful: it gives the simplest outside boundary of a scattered point set without dents, holes, or inward bends.

For a set of 2D points, the convex hull answers questions such as:

• Which points form the outside boundary?
• How large is the enclosed polygon?
• How far is it around the boundary?
• How many points are not part of the outer hull?

In this calculator, coordinates are measured in the units you enter. The graph automatically scales and centers the point set so the hull stays visible, so a point such as \((120,80)\) is a data coordinate rather than a fixed screen pixel.

---

Why Convex Hulls Matter

Convex hulls are a basic tool in computational geometry because they turn a cloud of points into a simpler boundary. Once the outer boundary is known, many other geometric tasks become easier.

For example, a convex hull can help summarize the spread of plotted data, approximate the outer boundary of an object in an image, find extreme points in a set, create simple collision or containment tests, or prepare geometry for later calculations such as distance, area, or shape comparison.

Convex hulls are also useful for learning algorithms because they show how a small geometric test can build a larger structure. The key idea is not just drawing a polygon; it is deciding which points make valid turns around the outside of the set.

---

Key Terms to Know

• Point set: The collection of input points, usually written as coordinate pairs such as \((x,y)\).
• Convex polygon: A polygon with no inward dents. Every interior angle is at most \(180^\circ\).
• Convex hull: The smallest convex set or polygon that contains all input points.
• Hull vertex: A point from the input set that becomes a corner of the convex hull.
• Interior point: In this calculator, an input point that is not counted as a hull vertex. This may include points strictly inside the hull and, depending on the point arrangement, collinear points that lie along a hull edge.
• Collinear points: Points that lie on the same straight line.
• Orientation test: A cross-product calculation that tells whether three points make a left turn, a right turn, or a straight line.
• Graham scan: A convex hull algorithm that sorts points around a pivot and uses a stack to remove turns that do not belong on the hull.
• Jarvis march: Also called gift wrapping, an algorithm that walks around the outside of the point set by repeatedly choosing the next extreme point.
• Monotone chain: A convex hull method that sorts points by coordinate order, builds lower and upper hull chains, and joins them.
• Shoelace formula: A coordinate formula for the area of a polygon.

---

How a Convex Hull Works

A convex hull algorithm must separate boundary points from points that are inside the boundary. Most 2D hull methods do this with repeated orientation tests.

For three points \(o\), \(a\), and \(b\), the orientation value is:

This value is the signed area-like cross product of the two vectors from \(o\) to \(a\) and from \(o\) to \(b\). In a standard mathematical coordinate plane, the sign tells whether the turn is counterclockwise, clockwise, or collinear. On a canvas, the positive \(y\) direction points downward, so the visual direction may look flipped compared with a textbook graph. The calculation still works as long as the same coordinate system is used consistently.

Building the hull

Different algorithms use the orientation test in different ways.

Graham scan chooses a pivot point, sorts the other points by angle around that pivot, and then scans through the sorted list. When the newest point would create a turn that bends inward, the algorithm removes the previous point from the working stack. The remaining stack traces the hull boundary.

Jarvis march starts from an extreme point and “wraps” around the point set. At each step, it chooses the next point so that all other points lie on the same side of the current edge. This can be intuitive to watch because it resembles rotating a line around the outside of the set.

Monotone chain sorts points by \(x\) coordinate and then by \(y\) coordinate. It builds a lower chain and an upper chain, removing points that do not keep the boundary convex. The two chains are then joined to make the final hull.

The calculator displays playback steps for Graham scan or Jarvis march. The final measurement cards use a monotone chain hull, so the selected playback algorithm changes the animation and step explanation rather than the final area and perimeter values.

Measuring the perimeter

Once the hull vertices are known, the perimeter is the sum of the straight-line distances around the polygon. If the hull has \(h\) vertices, and the first vertex is repeated after the last one to close the loop, the perimeter is:

where \((x_{h+1},y_{h+1})=(x_1,y_1)\).

Measuring the area

The area is calculated from the ordered hull vertices with the shoelace formula:

The absolute value is used because the signed area changes sign depending on the order and orientation of the vertices. The calculator reports the magnitude of the enclosed area in square coordinate units.

Counting non-hull points

The calculator labels the remaining count as interior points. It is calculated as:

where \(n\) is the total number of input points and \(h\) is the number of hull vertices. Because collinear boundary points are not kept as separate hull vertices in the final measurement hull, this count is best read as “points not counted as hull vertices,” not always as “strictly inside the polygon.”

---

Examples of Convex Hulls in Practice

Example 1: A rectangle with one inside point

Suppose the input points are:

$$ (0,0),\ (4,0),\ (4,3),\ (0,3),\ (2,1) $$

The point \((2,1)\) is inside the rectangle formed by the other four points, so the hull vertices are:

$$ (0,0),\ (4,0),\ (4,3),\ (0,3) $$

The perimeter is the distance around the rectangle:

$$ P = 4 + 3 + 4 + 3 = 14 $$

The area is:

$$ A = 4 \times 3 = 12 $$

So the point set has \(5\) total points, \(4\) hull points, \(1\) non-hull point, perimeter \(14\) coordinate units, and area \(12\) square coordinate units.

---

Example 2: Estimating the spread of a pixel point cloud

Imagine marking several pixel locations around an object in an image:

$$ (40,40),\ (160,50),\ (150,120),\ (70,150),\ (100,80),\ (115,70) $$

The two middle points help describe the cloud, but they do not expand the outside boundary. The hull vertices are:

$$ (40,40),\ (160,50),\ (150,120),\ (70,150) $$

Using the distance formula around the boundary gives a perimeter of approximately:

$$ P \approx 390.58\ \text{units} $$

Using the shoelace formula gives:

$$ A = 9{,}100\ \text{units}^2 $$

This does not mean the real object covers exactly \(9{,}100\) physical square units. It means the convex polygon drawn around those coordinates encloses \(9{,}100\) square coordinate units.

---

Example 3: A collinear edge point

Suppose the input points are:

$$ (0,0),\ (2,0),\ (4,0),\ (4,2),\ (0,2) $$

The point \((2,0)\) lies on the bottom edge between \((0,0)\) and \((4,0)\). It is on the boundary of the geometric rectangle, but it is not needed as a corner. The hull vertices are:

$$ (0,0),\ (4,0),\ (4,2),\ (0,2) $$

The area is:

$$ A = 4 \times 2 = 8 $$

The perimeter is:

$$ P = 4 + 2 + 4 + 2 = 12 $$

The calculator may count \((2,0)\) as a non-hull point because the final measurement hull removes collinear boundary points. This is not an error; it is a common way to represent a convex polygon using only its necessary vertices.

---

How to Interpret the Result

Total points is the number of current input points in the point set.

Hull points is the number of vertices in the computed convex hull. A larger hull-point count means more of the input points are part of the outside boundary. A smaller hull-point count means many points are inside the boundary or lie along edges that are not kept as vertices.

Perimeter is the distance around the hull in coordinate units. It increases when outer points move farther apart or when the hull gains new corners that extend the boundary.

Area is the space enclosed by the hull in square coordinate units. It measures the area of the convex polygon, not the area of every visible object or cluster inside it.

Interior points means points that are not counted as hull vertices. In this calculator, it is a simple difference between the total point count and the hull vertex count.

Metric time is the local time needed to compute the final hull used for the measurement cards. It can vary by browser, device, and current workload. It should not be treated as a formal benchmark.

Algorithm steps show the selected Graham scan or Jarvis march playback. These steps are educational: they help you see how an algorithm reaches a hull boundary.

Algorithm comparison summarizes the selected algorithms by complexity and local step-generation time. Graham scan is shown with \(O(n\log n)\) complexity, while Jarvis march is shown with \(O(nh)\) complexity, where \(n\) is the total number of points and \(h\) is the number of hull points.

---

Common Mistakes and Misconceptions

Using fewer than three non-collinear points. A polygon hull needs at least three unique points that are not all on one line. One point, two points, duplicate points, or points along a single line cannot enclose polygon area.

Expecting duplicate coordinates to count as separate geometry. Repeating the same point does not expand the hull. In the editable table, duplicate rows are treated as invalid when their stored number values match after negative-zero normalization.

Confusing the displayed graph with a textbook coordinate plane. The canvas displays \(y\) increasing downward. This affects how turns look visually, although distances, area magnitude, and hull containment still make sense within the same coordinate system.

Treating coordinate units as real-world units. A perimeter of \(300\) coordinate units is not automatically \(300\) centimeters, inches, or meters. To convert to a physical length or area, you need a known scale outside the calculator.

Expecting every boundary point to appear as a hull vertex. A point that lies exactly along a hull edge may be removed because it is not needed as a polygon corner.

Assuming the playback choice changes the metric hull. The Graham scan and Jarvis march options control the animation and step cards. The final measurement values are based on the calculator’s final hull calculation.

Reading local timing too literally. A timing value in milliseconds is affected by the device, browser, and momentary system load. It is useful for comparison and learning, not for rigorous performance testing.

---

When to Use Convex Hulls

Use a convex hull when you want to identify or measure the outside boundary of a 2D point set. Common uses include:

• Finding the outer points of a scatter plot or coordinate set.
• Studying computational geometry algorithms in a visual way.
• Estimating the spread of marked pixels or screen coordinates.
• Comparing how different point sets change area and perimeter.
• Creating a simple enclosing shape before doing more detailed geometry work.
• Demonstrating how orientation tests, sorting, and stack-based algorithms work together.

A convex hull is most helpful when a simple outer envelope is enough. It is less appropriate when you need a concave outline that follows inward notches or detailed shape boundaries.

---

Limitations and Things to Keep in Mind

This calculator works with 2D coordinate pairs only. It does not support 3D coordinates, geographic coordinates, map projections, or physical unit conversion.

Finite entered coordinates, including negative and outside-canvas values, are preserved and the graph auto-fits them. Values that cannot be represented as finite JavaScript numbers are rejected.

The final area and perimeter are reported in coordinate units and square coordinate units. They are not real-world measurements unless your entered coordinates already use a real-world unit or you separately convert them using a reliable scale.

A valid polygon hull requires at least three non-collinear unique points. If the points are all collinear, the hull can describe a line segment, but it cannot enclose polygon area.

Collinear boundary points are not retained as separate hull vertices in the final measurement hull. This keeps the polygon representation minimal, but it can surprise users who expect every point on the edge to appear in the hull count.

Area and perimeter are normally displayed with up to \(2\) decimal places; nonzero representable values outside that display range use scientific notation. A nonzero area too small for binary64 is labeled not representable (nonzero), and magnitudes beyond the available number range are labeled not representable. Timing values are displayed with up to \(3\) decimal places. Editable point values preserve their stored number value, and duplicate detection compares those stored values exactly after normalizing negative zero.

Orientation tests scale the three finite coordinates before multiplying and retain the exact stored binary sign if that scaling erases both products. Their usual tolerance is \(256\,\text{Number.EPSILON}\) times the local normalized product scale. Points that are extremely close to collinear may be handled as collinear for practical display and calculation purposes.

For engineering, surveying, GIS, robotics, manufacturing, or safety-critical work, use a coordinate system, precision model, and software workflow appropriate to the project. This visual calculator is best for learning and quick exploration.

---

How to Use This Calculator

1. Enter \(X\) and \(Y\) coordinates in the point table, or click the canvas to add points.
2. Drag points on the canvas to reposition them, or use the add and delete controls to adjust the point table.
3. Paste coordinate pairs into the import area if you already have a list of points. Use one point per nonblank line, with coordinates separated by a comma, space, or tab.
4. Generate a random point set by entering a random point count. Counts below \(5\) or above \(80\) are clamped to the supported range.
5. Choose Graham scan or Jarvis march to control the animation playback.
6. Use Step, Play/Pause, and Reset to inspect the algorithm steps.
7. Review the total points, hull points, perimeter, area, interior points, and metric time.
8. Use the comparison table to compare algorithm complexity and local step-generation time.
9. Download the canvas as a PNG if you want to save the current visualization.

---

Frequently Asked Questions

---

Sources and References

• Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Computational Geometry: Algorithms and Applications, 3rd ed., Springer, especially the chapters on computational geometry foundations and convex hulls. Springer book page
• Franco P. Preparata and Michael Ian Shamos, Computational Geometry: An Introduction, Springer, especially the chapters “Convex Hulls: Basic Algorithms” and “Convex Hulls: Extensions and Applications.” Springer book page
• Joseph O’Rourke, Computational Geometry in C, 2nd ed., Cambridge University Press, especially the material on convex hulls and geometric algorithms. Google Books preview
• CGAL, “2D Convex Hulls and Extreme Points,” user manual, for convex hull definitions, hull vertices as extreme points, and algorithm complexity comparisons. CGAL documentation
• Robert Sedgewick and Kevin Wayne, Algorithms, 4th Edition booksite, “Convex Hull,” for orientation testing, convex hull exercises, and algorithm-analysis context. Princeton Algorithms booksite
• Eric W. Weisstein, “Shoelace Formula,” MathWorld—A Wolfram Resource, for the polygon area formula from vertex coordinates. MathWorld
• WHATWG, HTML Standard, “The canvas element,” for the default 2D canvas coordinate system with origin at the top left, \(x\) increasing right, and \(y\) increasing downward. HTML Standard