Algorithm · Artificial Intelligence

Andrew's Monotone Chain and Incremental Construction for 2D and 3D Convex Hulls

By 李伟_Li慢慢 · Aug 1, 2026

Read original on juejin.cn ↗ Google Translate ↗ Alt translation

Convex hulls are workhorse geometry primitives for collision detection, bounding-volume generation, and model simplification. Having a clean, numerically stable implementation of both the 2D monotone chain and the 3D incremental method means an engineer can drop them into a physics engine or mesh tool without debugging edge-case orientation bugs.

Summary

Two foundational convex hull algorithms get a direct, code-forward treatment. For 2D point sets, Andrew's Monotone Chain sorts by x-coordinate, then walks left-to-right for the lower hull and right-to-left for the upper hull, discarding points that break convexity via cross-product checks. The result is a numerically stable O(n log n) implementation that avoids the polar-angle pitfalls of Graham Scan.

The 3D approach switches to incremental construction. It first finds the four points that maximize tetrahedron volume, builds outward-facing triangular faces, then processes every remaining point. For each point outside the current hull, the algorithm identifies visible faces, extracts the horizon edges where visible and invisible faces meet, deletes the visible faces, and stitches new triangles from the horizon to the point. A final outward-normal pass keeps all face orientations consistent.

Both implementations are shown in full TypeScript, with helper functions for cross products, orientation tests, deduplication, and centroid calculation. The 3D code includes a validation routine that checks every vertex lies inside or on every face.

Takeaways

— Andrew's Monotone Chain sorts points by x (then y), builds the lower hull left-to-right and the upper hull right-to-left, and merges them in O(n log n).

— A cross-product check during chain construction discards any middle point that would create a non-convex (right) turn.

— The 3D incremental method seeds the hull with the four points that produce the largest tetrahedron volume, found by maximizing pairwise distance, then triangle area, then tetrahedron volume.

— For each new point, visible faces are those where the orientation determinant is positive; invisible faces are kept, and the horizon edges between them are connected to the new point to form fresh triangles.

— All face normals are forced outward by testing the orientation against the polyhedron's centroid and swapping two vertices if the normal points inward.

— A final validation pass confirms every vertex lies on or inside every face, guarding against floating-point drift.

Conclusions

Andrew's Monotone Chain is preferred in production graphics code over Graham Scan specifically because coordinate sorting sidesteps the floating-point instability of polar-angle comparisons.

The 3D incremental algorithm's use of a maximum-volume initial tetrahedron is a practical heuristic that reduces the chance of degenerate starting configurations, though the code still guards against collinear and coplanar point sets.

Tracking face visibility via a sorted vertex-ID key rather than geometric hashing is a robust pattern that avoids floating-point equality checks when identifying shared edges and faces.

Concepts & terms

Convex Hull

The smallest convex set that contains a given set of points. In 2D, it is the polygon formed by the outermost points; in 3D, it is the smallest convex polyhedron enclosing all points.

Andrew's Monotone Chain

A 2D convex hull algorithm that sorts points by x-coordinate, constructs a lower and an upper chain separately, and merges them. It runs in O(n log n) and is numerically more stable than Graham Scan because it avoids polar-angle sorting.

Incremental Construction (Beneath-Beyond)

A 3D convex hull algorithm that starts with a tetrahedron and adds points one by one. For each new point, it removes faces visible from that point and retriangulates the horizon boundary, growing the hull incrementally.

Orientation Determinant

A scalar computed as the dot product of a cross product and a vector. In 3D, orient(a,b,c,p) > 0 means point p lies on the outside of the triangle formed by a, b, and c, assuming an outward-facing normal.

Horizon Edges

In incremental 3D convex hull construction, the closed loop of edges that separate faces visible from a new point and faces not visible. New triangles are formed by connecting the horizon to the new point.

Source: juejin.cn ↗ Google Translate ↗ Backup ↗