Vectors

A point and a vector are the same pair of numbers; the difference is interpretation. Treating points as position vectors and differences as direction vectors removes most of the case analysis from geometry code.

Operations

P a{1, 2}, b{3, 4};
a + b            // translate
a - b            // the vector from b to a
a * k            // scale
dot(a, b)        // a.x*b.x + a.y*b.y
cross(a, b)      // a.x*b.y - a.y*b.x
norm2(a)         // dot(a, a) = squared length
abs_(a)          // sqrt(norm2(a))

The two products

	Dot $a \cdot b$	Cross $a \times b$
Formula	$a_{x} b_{x} + a_{y} b_{y}$	$a_{x} b_{y} - a_{y} b_{x}$
Geometric	$∣ a ∣ ∣ b ∣ cos θ$	$∣ a ∣ ∣ b ∣ sin θ$
Zero when	perpendicular	parallel
Sign tells you	acute / obtuse	left turn / right turn
Also computes	projection length	twice the triangle area

Between them they answer almost every “where is this relative to that” question — with exact integer arithmetic when the input is integral.

Standard transformations

P perp(P a)      { return {-a.y, a.x}; }             // rotate 90 degrees CCW
P rotate(P a, double t) {                            // rotate by angle t
    return {a.x*cos(t) - a.y*sin(t), a.x*sin(t) + a.y*cos(t)};
}
P scaleTo(P a, double len) { double d = abs_(a); return {a.x*len/d, a.y*len/d}; }
P reflectAcross(P p, P a, P b) {                     // reflect p across line ab
    P d = b - a;
    double t = (double)dot(p - a, d) / norm2(d);
    P proj = a + d * t;
    return proj * 2 - p;
}

perp is exact in integers and is the most useful of these — perpendicular bisectors, normals, and half-plane directions all come from it.

Complex numbers as points

std::complex<double> gives vector arithmetic for free:

using P = complex<double>;
double dot(P a, P b)   { return (conj(a) * b).real(); }
double cross(P a, P b) { return (conj(a) * b).imag(); }
P rotate(P a, double t){ return a * polar(1.0, t); }
abs(a); arg(a); norm(a);                             // length, angle, squared length

Multiplication by $e^{i θ}$ is rotation, which makes rotation code trivial. The drawbacks: it forces floating point (losing integer exactness), and norm means squared length, which surprises people. Use it for rotation-heavy problems, a plain struct otherwise.

Projection and decomposition

Project $p$ onto the direction $d$ :

$proj_{d} (p) = \frac{p \cdot d}{d \cdot d} d, perpendicular part = p - proj_{d} (p) .$

double t = (double)dot(p - a, b - a) / norm2(b - a);   // parameter along segment ab
P closest = a + (b - a) * t;                            // closest point on the LINE
double tc = max(0.0, min(1.0, t));                      // clamp for the SEGMENT

Clamping $t$ to $[0, 1]$ is the difference between “closest point on the line” and “closest point on the segment” — a one-line change that is easy to forget.

Signed area

$[△ ab c] = \frac{1}{2} cross (b - a, c - a) .$

Positive when $a, b, c$ are counter-clockwise. Summing over a polygon’s edges gives the shoelace formula — see Polygon Area.

Angular sorting

Sorting vectors by angle comes up constantly (radial sweeps, Graham scan, visibility). Do not use atan2: it is slow and imprecise. Sort by half-plane, then by cross product:

int half(P p) { return (p.y < 0 || (p.y == 0 && p.x < 0)); }
sort(v.begin(), v.end(), [](P a, P b) {
    int ha = half(a), hb = half(b);
    if (ha != hb) return ha < hb;
    long long c = cross(a, b);
    return c != 0 ? c > 0 : norm2(a) < norm2(b);
});

Exact for integer coordinates, and about 5× faster.

3D vectors

The dot product generalises directly. The cross product becomes a vector:

$a \times b = (a_{y} b_{z} - a_{z} b_{y}, a_{z} b_{x} - a_{x} b_{z}, a_{x} b_{y} - a_{y} b_{x}),$

whose length is the parallelogram area and whose direction is the normal. The scalar triple product $a \cdot (b \times c)$ is six times the tetrahedron volume and is the 3D orientation test. See 3D Geometry.

See also: Dot Product · Cross Product · Geometry Basics

whoashish's cp notes

Directory