{{ summaryTitle }}
{{ summaryValue }}

{{ summaryLine }}

Algorithm{{ algorithmLabel }} Trace{{ resultsReady ? `${computation.values.step_index} / ${computation.values.step_count}` : '—' }} Checks{{ resultsReady ? computation.values.orientation_tests : '—' }}
The trace names every orientation decision made by the selected algorithm.
One x,y pair per line; duplicate coordinate pairs are rejected.
{{ stepReadout }}
Step 0 shows the ordered input; the last step shows the completed hull.
The neutral default keeps only each straight boundary run's extreme endpoints.
{{ chartExportStatus }}

The chart renderer is unavailable. The hull path and decision ledger remain available.

Hull trace
{{ row.label }}{{ row.display }}
Step {{ computation.values.step_index }} of {{ computation.values.step_count }}
{{ currentStep.title }}
{{ currentStep.message }}
{{ currentStep.turn }}
Working boundary: {{ currentStep.boundary.length ? currentStep.boundary.join(' → ') : 'Not started' }}
Candidate: {{ currentStep.candidate.join(' → ') }}
StepDecisionTurnBoundaryCopy
{{ row.step }}{{ row.decision }}{{ row.turn }}{{ row.boundary }}
{{ ledgerExportStatus }}
Pathfinding Algorithm Simulator Compare four pathfinding algorithms on an editable weighted grid and inspect route cost, exploration order, diagonal rules and no-path outcomes.
Minimum Spanning Tree Algorithm Simulator Compare Kruskal and Prim on weighted graphs with deterministic edge decisions, cycle rejections, and minimum spanning forest results.
Network Flow Algorithm Simulator Simulate Edmonds-Karp or Dinic on an editable capacity network and verify the maximum flow with residual traces and a minimum-cut certificate.
Sorting Algorithm Simulator Step through eight sorting algorithms on entered or seeded arrays with verified order, stability and operation counts for each deterministic run.

Draw the smallest convex boundary around a set of planar points and every point will lie inside it or on its edge. The result is the convex hull. A stretched rubber band around nails is a useful physical analogy, provided the band is not allowed to bend inward around an interior nail.

Hull algorithms agree on the enclosing polygon but reach it through different decisions. Monotone chain builds lower and upper boundaries after sorting by x then y. Graham scan chooses a low pivot, sorts the remaining points by angle, and maintains a stack. Jarvis march starts at an extreme point and repeatedly selects the next wrapping edge.

Algorithm Main structure Typical time growth Useful teaching focus
Monotone chain Lexicographic sort, lower chain, upper chain O(n log n) How left and right turns remove points from a partial boundary.
Graham scan Pivot, polar order, stack O(n log n) How angle order and stack pops enforce convexity.
Jarvis march Repeated next-edge search O(nh) How each hull vertex is chosen by comparing all points.

Here, n is the number of input points and h is the number of hull vertices. Jarvis march can be attractive when the hull is small relative to the point set, while the two sorting-based methods have predictable O(n log n) growth. A short educational trace should not be treated as a runtime benchmark because decision counts, language overhead, and coding details differ.

Collinear points create a policy choice rather than a single universally correct vertex list. Keeping only extreme vertices gives the shortest polygon representation. Keeping every boundary point retains samples that lie along straight hull edges. Both choices enclose the same region and usually have the same perimeter and area, but they produce different hull counts and paths.

Coordinates are treated as exact integers, so each orientation decision has an exact determinant rather than a floating-point tolerance. This makes the trace good for learning rule order. Real geographic or measured coordinates may need a precision-aware geometry library, projection choice, duplicate policy, and explicit tolerance before the same conclusions are safe.

How to Use This Tool:

Keep one point set fixed when comparing algorithms so the trace rather than the input explains the difference.

  1. Choose Monotone chain, Graham scan, or Jarvis march.
  2. Enter 3 to 30 distinct coordinate pairs, one integer x,y pair per line. Coordinates may run from -1,000,000 through 1,000,000.
  3. Select whether straight hull edges keep only their extreme vertices or every collinear boundary point.
  4. Move Trace step from the ordered input through each orientation decision. Use the point plane and decision ledger together to connect a determinant sign with the boundary change.
  5. At the final step, confirm the closed hull path and the invariant check before comparing hull count, orientation-test count, twice area, or perimeter.

Interpreting Results:

A positive orientation determinant is a left turn, a negative value is a right turn, and zero means the three tested points are collinear. The decision text explains whether the middle point stays or leaves under the selected algorithm and boundary policy.

  • Hull count changes when collinear edge points are included; it is not a measure of geometric area.
  • Orientation tests counts the tests reached by the selected trace step, not a portable measure of wall-clock speed.
  • Invariant OK checks that every input point lies on or to the left of each directed hull edge. It verifies enclosure for this result, not every possible algorithm property.
  • Twice area stays integral for integer coordinates. Divide it by 2 to obtain the polygon area in square coordinate units.

Technical Details:

The orientation predicate is the signed two-dimensional cross product of vectors from point a to points b and c. Because every coordinate is a bounded integer, the sign test is exact for the accepted input range.

Formula Core:

The determinant decides whether three ordered points turn left, turn right, or continue along one line.

turn(a,b,c) = (bx−ax) (cy−ay) − (by−ay) (cx−ax)

For ordered hull vertices p0 through ph-1, the shoelace sum gives twice the enclosed area, and Euclidean edge lengths give the perimeter.

TwiceArea = |∑i=0h−1(xiyi+1−yixi+1)| Perimeter = ∑i=0h−1xi+1−xi2+yi+1−yi2

Index i + 1 wraps to vertex 0 after the final vertex, closing the polygon.

Rule Core:

Mechanism Ordered rule
Monotone chain Sort by x then y. Build lower and upper chains; pop the middle point on a right turn, and also on a collinear turn when only extreme vertices are kept.
Graham scan Choose the lowest then leftmost pivot. Sort radially, breaking equal-angle ties by distance, and apply the same stack-pop rule.
Jarvis march Start at the leftmost point. Compare every other point to the current candidate and choose the outward wrapping edge; for a collinear tie, keep the farther candidate.
Final boundary policy Canonicalize the final hull with either turn ≤ 0 removing collinear middle points or turn < 0 retaining them. If every point is collinear, keep the two extremes or the full sorted line.

Worked Examples:

A point on a square edge

Use (0,0), (1,0), (2,0), (2,2), (0,2), and the interior point (1,1). Extreme-only policy returns the four square corners. Include-every-boundary-point policy also retains (1,0), giving five hull points. Both paths enclose area 4, report twice area 8, and have perimeter 8; the interior point never joins the hull.

References: