Computational Geometry

Points, Segments, Polygons

Tesla Full Self-Driving processes a LiDAR point cloud of 100,000 points 10 times per second. Within 100 ms, a convex hull grows around every obstacle - and the car decides: steer around or brake. The foundation is the same cross product Gauss used to compute land parcel areas in 1795. Three primitives: point, segment, polygon. Everything else is built from them.

**Unity/Unreal (GJK algorithm):** collision detection between hitboxes uses the Gilbert-Johnson-Keerthi algorithm, which relies on convex polygons and the cross product; runs tens of thousands of times per frame
**SLAM in autonomous vehicles:** LiDAR points become convex obstacle hulls; real-time path planning in Tesla FSD, Waymo, and Boston Dynamics robots
**GPS trilateration:** intersection of three spheres (three segments in projection) - the fundamental geometric primitive in every smartphone
**AlphaFold2 (DeepMind):** protein structure prediction is a computational geometry problem in the 3D coordinate space of atoms

Points and Distances

**GPS trilateration** is the intersection of three spheres in 3D space, projected into a planar geometry problem. Unreal Engine's physics is collision detection between convex polyhedra, 60 times per second. AlphaFold2 from DeepMind predicts the 3D coordinates of protein atoms. Everything starts with the simplest object - a **point** in the plane and a pair of numbers (x, y).

A **point** in the plane is a pair of coordinates (x, y) ∈ R². Core operations: distance between points, vector from one point to another, orientation check for a triple of points.

The **cross product** is the primary tool of computational geometry. For two 2D vectors u = (ux, uy) and v = (vx, vy): u × v = ux·vy - uy·vx. The result is a scalar whose sign reveals **orientation**. The GJK algorithm in Unity and Unreal calls exactly this computation thousands of times per frame during collision detection.

Cross product	Sign	Orientation	Visually
u × v > 0	Positive	CCW (counter-clockwise)	r is to the left of p→q
u × v < 0	Negative	CW (clockwise)	r is to the right of p→q
u × v = 0	Zero	Collinear	p, q, r are on one line

For points P(0,0), Q(1,0), R(0,1): what is the cross product (Q-P) × (R-P)?

Segment Intersection

Two segments in the plane - do they intersect? The problem seems simple, but the devil is in the details: collinear segments, shared endpoints, touching at a single point. These edge cases are exactly what breaks naive implementations in game engines and causes characters to clip through walls at high FPS. The **cross product** is again the primary tool.

Segment AB intersects segment CD if points C and D lie on opposite sides of line AB, **and** points A and B lie on opposite sides of line CD. Testing "opposite sides" uses the sign of the cross product.

**Floating-point arithmetic is unreliable!** Comparing a cross product to zero with `==` can fail due to floating-point errors. Production code uses epsilon comparisons or integer arithmetic.

The algorithm runs in O(1) - constant time for a single pair of segments. But for n segments, the naive check of all pairs is O(n²). How to do better - that is what the sweep line lesson covers.

Two segments lie on the same line and partially overlap. Which of the 4 orientation tests does NOT detect the intersection?

Polygons and the Shoelace Formula

A land parcel, a building footprint on a map, a character's hitbox in a game, a predicted protein contour from AlphaFold2 - all of these are **polygons**. How do we represent a polygon in code and compute its area in a single pass?

A **simple polygon** is a closed polyline without self-intersections. It is represented as an ordered list of vertices (v₁, v₂, ..., vₙ). Edges: v₁v₂, v₂v₃, ..., vₙv₁.

Why "shoelace"? Writing the coordinates in two columns and connecting them crosswise produces a pattern that resembles a shoe's lacing.

Operation	Complexity	Algorithm
Polygon area	O(n)	Shoelace formula
Point inside polygon	O(n)	Ray casting
Polygon perimeter	O(n)	Sum of edge lengths
Triangulation	O(n log n)	Ear clipping / Monotone

The shoelace formula for the polygon with vertices (0,0), (2,0), (2,2), (0,2) gives area:

Polygon Convexity

Stretch a rubber band around a set of nails on a board. The shape the band forms is a **convex polygon**. All vertices are on the outside, none are pushed inward. Tesla FSD builds a convex hull around every detected car and pedestrian - precisely because convex gives O(log n) instead of O(n), and the car cannot afford to wait.

A **convex polygon** is one in which the segment connecting any two interior points lies entirely inside the polygon. Equivalently: all interior angles are less than 180°, or every consecutive triple of vertices has the same orientation.

Operation	Convex polygon	Arbitrary polygon
Point inside?	O(log n) - binary search	O(n) - ray casting
Intersection of two polygons	O(n + m)	O(n·m) in general
Minimum distance	O(log n) - rotating calipers	O(n) or O(n log n)
Area	O(n) - shoelace formula	O(n) - shoelace formula

Convexity unlocks algorithmic advantages: binary search over angles, the rotating calipers technique, fast intersection. SLAM systems in Boston Dynamics robots and Waymo self-driving cars build convex obstacle hulls for exactly this speed - the next lesson covers how.

The three primitives from the opening - point, segment, polygon - are the foundation of everything. The cross product is the universal orientation tool, running inside GJK collision detection, GPS trilateration, and SLAM systems. The shoelace formula turns coordinates into area in one pass - Gauss invented it in 1795, GIS systems use it today.

Testing segment intersection is straightforward - just solve the system of line equations

Segment intersection is full of edge cases: collinear segments, overlapping segments, touching at a single point, shared endpoints. Each case requires separate handling, and floating-point arithmetic adds precision problems.

Solving line equations ignores that segments are BOUNDED portions of lines: the intersection point must lie on both segments. Collinear segments produce a degenerate system (0/0) - a separate branch is required. That is why real physics engines (Bullet, PhysX) have tens of lines of code for a single intersection test, not three.

Is the polygon with vertices (0,0), (4,0), (4,3), (2,1), (0,3) convex?

Key Takeaways

**Cross product** u × v = ux·vy - uy·vx - one scalar, three cases: CCW / CW / collinear. The backbone of GJK collision detection in Unity and Unreal
**Segment intersection** - 4 orientation tests for the general case, plus a separate branch for collinear segments; float arithmetic requires epsilon comparisons
**Shoelace formula** - polygon area in O(n) from vertex coordinates; the same math GIS systems use for cadastral surveying
**Convex polygons** - O(log n) point-in-polygon vs O(n); SLAM systems build convex obstacle hulls specifically for this speed advantage

Вопросы для размышления

Why is the cross product more important than the dot product in computational geometry? In which problems is the dot product indispensable (for example, in shader lighting calculations)?
Shoelace formula for a polygon with a hole (annular): how should the algorithm be adapted so the hole is subtracted from the area?
Float arithmetic introduces errors when comparing against zero (epsilon). How does the GJK algorithm in Unity handle this in production code?

Связанные уроки

alg-01-big-o — Geometric algorithms are analyzed with the same tools: O-notation, worst/average case
ds-01-arrays — Spatial structures (k-d tree, segment tree) store geometric objects for fast queries
la-01-vectors-intro — Cross product for orientation, dot product for projections - linear algebra is everywhere in geometry
cgeom-02 — Basic primitives (points, segments) are building blocks for convex hulls and Delaunay triangulations
la-04-lines-planes