3D Geometry

Primitives

struct P3 {
    long long x, y, z;
    P3 operator+(const P3& o) const { return {x+o.x, y+o.y, z+o.z}; }
    P3 operator-(const P3& o) const { return {x-o.x, y-o.y, z-o.z}; }
};
 
long long dot(P3 a, P3 b) { return a.x*b.x + a.y*b.y + a.z*b.z; }
 
P3 cross(P3 a, P3 b) {
    return { a.y*b.z - a.z*b.y,
             a.z*b.x - a.x*b.z,
             a.x*b.y - a.y*b.x };
}
 
long long triple(P3 a, P3 b, P3 c) { return dot(a, cross(b, c)); }
long long norm2(P3 a) { return dot(a, a); }

The dot product is unchanged from 2D. The cross product becomes a vector: perpendicular to both inputs, with length equal to the parallelogram area, direction by the right-hand rule.

The scalar triple product

$[a,b,c]=a\cdot (b\times c)=\left|\begin{array}{ccc}{a}_x& a_y& a_z\\ b_x& b_y& b_z\\ c_x& c_y& c_z\end{array}\right|$

This is the 3D orientation test:

Value	Meaning
$>0$	$d$ is above the plane $abc$ (right-hand rule)
$=0$	the four points are coplanar
$<0$	below

And $|[a,b,c]|$ is 6× the tetrahedron volume, or the volume of the parallelepiped.

int orient3(P3 a, P3 b, P3 c, P3 d) {
    long long v = triple(b - a, c - a, d - a);
    return (v > 0) - (v < 0);
}

Overflow warning: this is a degree-3 expression. With coordinates up to $10^6$ it reaches $10^{19}$ — already past long long. Use __int128 unless the coordinates are small.

Planes

A plane is $\{p:n\cdot p=d\}$ with normal $n$. From three points: $n=(b-a)\times (c-a)$, $d=n\cdot a$.

Task	Formula
Signed distance from $p$	$\frac{n\cdot p-d}{|n|}$
Which side is $p$ on?	sign of $n\cdot p-d$ (exact in integers)
Projection of $p$ onto the plane	$p-\frac{n\cdot p-d}{|n{|}^2}n$
Reflection across the plane	$p-2\frac{n\cdot p-d}{|n{|}^2}n$
Line-plane intersection	solve for the parameter $t$; parallel iff $n\cdot d_{\text{line}}=0$
Plane-plane intersection	a line with direction $n_1\times n_2$
Angle between planes	the angle between the normals

Distances

Pair	Formula
Point to line	$\frac{|(p-a)\times d|}{|d|}$
Point to plane	$\frac{|n\cdot p-d|}{|n|}$
Line to line (skew)	$\frac{|(a_2-a_1)\cdot (d_1\times d_2)|}{|d_1\times d_2|}$
Point to segment / triangle	project and clamp
Point to sphere	$||p-c|-r|$

The skew-line formula is worth remembering: the common perpendicular direction is $d_1\times d_2$, and the distance is the projection of the connecting vector onto it. When $d_1\times d_2=0$ the lines are parallel and the point-to-line formula applies.

Volumes

Solid	Formula
Tetrahedron $abcd$	$\frac{1}{6}|[b-a,c-a,d-a]|$
Parallelepiped	$|[a,b,c]|$
Convex polyhedron	$\frac{1}{3}{\sum }_{\text{faces}}(\text{face centroid}\cdot \hat{n})A_{\text{face}}$ (divergence theorem)
Polyhedron from triangles	$\frac{1}{6}\sum \mathrm{triple}(a_i,b_i,c_i)$ over outward-oriented triangles
Sphere	$\frac{4}{3}\pi r^3$
Intersection of two spheres	a lens; two spherical caps

The triangle-sum volume formula is the 3D shoelace: sum the signed tetrahedron volumes from the origin to each face, and everything outside cancels.

3D convex hull

$O(n\log n)$ expected with randomised incremental construction plus a conflict graph; $O(n^2)$ with the simple incremental algorithm. Output is $O(n)$ faces (Euler: $V-E+F=2$).

Substantially harder than 2D — the degeneracies (coplanar points, collinear edges) are much nastier, and the in-sphere/orientation predicates overflow easily.

Payoff: the 3D hull of points lifted onto the paraboloid $(x,y)\to (x,y,x^2+y^2)$ projects to the 2D Delaunay triangulation.

Rotations

Representation	Note
Rotation matrix (3×3 orthogonal)	composes by multiplication; 9 numbers
Euler angles	intuitive but suffers gimbal lock
Axis-angle (Rodrigues)	$p^{\prime }=p\cos \theta +(k\times p)\sin \theta +k(k\cdot p)(1-\cos \theta )$
Quaternions	4 numbers, no gimbal lock, composes by quaternion multiplication, interpolates smoothly

Quaternions are the standard in graphics and robotics. In competitive programming, rotations by fixed axis-aligned amounts (90° about an axis) are much more common, and those are simple coordinate permutations with sign flips — there are 24 of them for a cube.

Spherical geometry

Task	Formula
Great-circle distance	$r\arccos (\hat{u}\cdot \hat{v})$, or the numerically better haversine formula
Spherical triangle area	$r^2(A+B+C-\pi )$ — the spherical excess
Convert lat/long to Cartesian	$(\cos \varphi \cos \lambda ,\cos \varphi \sin \lambda ,\sin \varphi )$

Use the haversine form for great-circle distance: acos of a dot product loses precision badly for nearby points.

See also: Vectors · Cross Product · Convex Hull