Geometry & Convex Hull Visualizer

The convex hull is the shape a rubber band would take around a set of pins. The Convex Hull Visualizer computes it with Andrew's monotone chain, an O(n log n) sort followed by two linear passes, and redraws it the instant you click another point onto the canvas.

Points are sorted by x and then by y, and the algorithm builds the lower boundary left to right, discarding any point that would make a clockwise turn, then repeats right to left for the upper boundary. The two chains meet at the extremes, which is why the endpoints are dropped before joining them.

A checkbox controls whether points lying exactly on a hull edge count as vertices. Both conventions appear on competitive judges depending on the problem statement, and comparing your own output against a tool that picked one silently is a reliable way to lose an hour. Everything runs in the page.

Walkthrough: The Sample Point Set

1. The canvas opens on 10 points: eight form the hull and 2 sit inside it, drawn as small white circles rather than filled orange ones. Load Sample steps to the next stored point set.
2. Read the counters along the top: Points: 10, Hull: 8 and an area of 64500.0, computed by the shoelace formula over the hull vertices.
3. Click anywhere inside the shaded polygon. The point count rises, the hull count does not, and nothing about the outline moves.
4. Now click well outside one edge. That point becomes a vertex, and one or more former vertices may drop back to being interior, which is the behaviour that makes the algorithm worth watching rather than reading.
5. Take the Copy C++ button for a vector<pair<int,int>> initialiser of every point, ready to paste into a local test.

Tricky Inputs: Collinear and Degenerate Sets

• With the collinear box unticked, a point exactly on an edge is discarded, giving the minimal vertex set. Tick it and that point is retained, which some problems require and others reject.
• Three points in a straight line have no interior. Unticked, the hull reduces to the 2 extremes; ticked, all 3 are kept.
• Fewer than 2 points returns the input unchanged, and exactly 2 draws a line rather than a polygon, with no area reported.
• Duplicate points are not deduplicated. Clicking twice on the same pixel adds a second point at identical coordinates, which can appear as a repeated hull vertex.
• Coordinates are integers rounded from the click position within a 460 by 380 canvas, so the cross product stays in exact integer arithmetic and no floating-point tolerance is needed.
• Area is computed with the shoelace formula and is exact for integer coordinates, though it is reported to 2 decimals because a triangle on integer points can have a half-unit area.