17.1 Points and Vectors

You need a mathematical representation for locations, directions, distances, and geometric relationships.

algorithmsgeometry

17.1 Points and Vectors

Problem

You need a mathematical representation for locations, directions, distances, and geometric relationships. Nearly every computational geometry algorithm depends on a small set of operations involving points and vectors. Before implementing line intersections, convex hulls, closest-pair searches, or polygon algorithms, you must understand how points and vectors are represented and manipulated.

Solution

Represent a point as a coordinate in space and represent a vector as a displacement between two points.

In two-dimensional geometry:

Point A = (2, 3)
Point B = (7, 5)

The vector from A to B is:

AB = B - A
   = (7 - 2, 5 - 3)
   = (5, 2)

A point represents a position.

A vector represents a direction and magnitude.

Although they may share the same coordinate representation in code, they serve different conceptual purposes.

A common implementation is:

from dataclasses import dataclass
from math import sqrt

@dataclass
class Point:
    x: float
    y: float

@dataclass
class Vector:
    x: float
    y: float

Basic vector operations:

def add(a: Vector, b: Vector) -> Vector:
    return Vector(a.x + b.x, a.y + b.y)

def subtract(a: Vector, b: Vector) -> Vector:
    return Vector(a.x - b.x, a.y - b.y)

def multiply(v: Vector, k: float) -> Vector:
    return Vector(v.x * k, v.y * k)

Creating a vector from two points:

def vector_between(a: Point, b: Point) -> Vector:
    return Vector(b.x - a.x, b.y - a.y)

Understanding Vector Length

The length of a vector measures its magnitude.

For vector:

v = (x, y)

the length is:

genui{"math_block_widget_always_prefetch_v2":{"content":"\sqrt{x^2+y^2}"}}

Example:

v = (3, 4)

Length:

sqrt(3² + 4²)
= sqrt(9 + 16)
= sqrt(25)
= 5

Implementation:

def length(v: Vector) -> float:
    return sqrt(v.x * v.x + v.y * v.y)

Computing square roots is relatively expensive. Many algorithms compare squared distances instead.

def length_squared(v: Vector) -> float:
    return v.x * v.x + v.y * v.y

This technique appears frequently in nearest-neighbor searches and closest-pair algorithms.

Dot Product

The dot product measures alignment between vectors.

For vectors:

a = (ax, ay)
b = (bx, by)

the dot product is:

a · b = axbx + ayby

Implementation:

def dot(a: Vector, b: Vector) -> float:
    return a.x * b.x + a.y * b.y

Example:

a = (3, 4)
b = (5, 2)

a · b
= 3×5 + 4×2
= 15 + 8
= 23

Applications include:

  • Angle computation
  • Projection
  • Orthogonality testing
  • Distance to lines
  • Closest-point problems

Two vectors are perpendicular when:

a · b = 0

Example:

(1, 0) · (0, 1) = 0

Cross Product in Two Dimensions

The three-dimensional cross product produces a vector.

In computational geometry, the two-dimensional cross product is commonly represented by a scalar:

cross(a, b)
=
axby − aybx

Implementation:

def cross(a: Vector, b: Vector) -> float:
    return a.x * b.y - a.y * b.x

Example:

a = (4, 0)
b = (2, 3)

cross(a, b)
=
4×3 − 0×2
=
12

The sign of the result contains important geometric information.

Result Meaning
Positive Counterclockwise turn
Negative Clockwise turn
Zero Collinear

This operation forms the foundation of orientation testing, convex hull algorithms, segment intersection detection, polygon area computation, and many sweep-line algorithms.

Distance Between Points

Given points:

A = (x1, y1)
B = (x2, y2)

Distance is computed from the vector:

AB = (x2 − x1, y2 − y1)

and then:

def distance(a: Point, b: Point) -> float:
    dx = b.x - a.x
    dy = b.y - a.y
    return sqrt(dx * dx + dy * dy)

For large-scale geometric algorithms, squared distance is often preferred:

def distance_squared(a: Point, b: Point) -> float:
    dx = b.x - a.x
    dy = b.y - a.y
    return dx * dx + dy * dy

Vector Normalization

Many algorithms require a unit vector whose length equals one.

Given vector:

v = (x, y)

normalize by dividing each coordinate by the vector length:

def normalize(v: Vector) -> Vector:
    l = length(v)
    return Vector(v.x / l, v.y / l)

Example:

(3, 4)

becomes:

(0.6, 0.8)

Normalization is widely used in graphics, physics simulation, and motion planning.

Translation

Adding a vector to a point moves the point.

Example:

Point P = (2, 5)

Vector v = (4, -1)

Result:
(6, 4)

Implementation:

def translate(p: Point, v: Vector) -> Point:
    return Point(
        p.x + v.x,
        p.y + v.y
    )

Many geometric transformations are built from repeated applications of translation.

Common Pitfalls

Confusing Points and Vectors

The representation may be identical in memory, but their meanings differ.

Point     = location
Vector    = displacement

Keeping separate types often prevents logical errors.

Using Floating Point Equality

Avoid:

a == b

for geometric calculations.

Instead:

EPS = 1e-9

abs(a - b) < EPS

Computing Square Roots Unnecessarily

When only comparisons are needed:

d1 < d2

compare squared distances instead.

d1² < d2²

This avoids expensive square root operations.

Ignoring Overflow

When coordinates are large:

x² + y²

may overflow integer types.

Use sufficiently large numeric representations.

Discussion

Points and vectors form the alphabet of computational geometry. Every major algorithm in this chapter eventually reduces to a sequence of vector additions, dot products, cross products, and distance calculations. Convex hull construction depends on cross products. Closest-pair algorithms depend on distance computations. Polygon algorithms depend on orientation tests derived from vectors. Sweep-line methods repeatedly evaluate geometric predicates built from these primitive operations.

A strong understanding of points and vectors simplifies every subsequent topic. Once these operations become familiar, more advanced geometric algorithms often appear as elegant combinations of a surprisingly small set of basic tools.