Loading 3D scene...

Computational Geometry 3D

Quality:
The science

Convex hull. Incremental algorithm: a point is outside the current hull exactly when some face sees it, i.e. its signed volume with the face's outward normal, (b−a)·((c−a)×(p−a)), is positive. Visible faces are deleted and the horizon (edges between a visible and a hidden face) is joined to the new point. Expected hull size for random points is small; the worst case here is O(n²). Volume uses the divergence theorem V = (1/6) Σ pa·(pb×pc) over outward faces.

Delaunay by lifting. Mapping (x, y) to (x, y, x²+y²) turns "empty circumcircle" into "face on the underside of the convex hull", so the lower hull projected back down is the Delaunay triangulation. A set with n points and h on its 2D hull has exactly 2n − 2 − h triangles.

Closest pair. Sort by x, split, recurse, and compare only points within the best distance d of the split plane. In 3D the strip is checked exhaustively (the 2D "7 neighbours" bound does not carry over), which keeps it correct, though the worst case is no longer O(n log n).

Simplifications: floating-point predicates with a fixed tolerance (no exact arithmetic), so near-coplanar or near-cocircular inputs may misclassify a face; random point sets are in general position; sizes up to 90 points run instantly, timings are wall-clock in your browser.

Running numerical checks...

Made with 🟠 Blender · Three.js