17.20 Geometry Libraries and Practical Patterns

Problem

Most real-world geometry software is not built from a single algorithm.

A mapping system may use:

point-in-polygon
spatial indexes
polygon clipping
bounding boxes
coordinate transforms

A CAD application may use:

line intersections
half-plane constraints
mesh generation
topological validation

A game engine may use:

collision detection
broad-phase indexing
ray casting
convex hulls

The challenge is not merely implementing individual algorithms. The challenge is combining them into reliable geometric systems.

Solution

Treat geometric algorithms as reusable building blocks.

Throughout this chapter, a small number of primitives have appeared repeatedly:

orientation
cross product
dot product
distance comparison
bounding-box tests
line intersection

Many advanced algorithms differ primarily in how they combine these primitives.

A practical geometry library should emphasize:

robust predicates
clear data structures
consistent coordinate semantics
reusable components

rather than isolated algorithms.

Core Geometric Types

Most libraries begin with a small set of geometric types.

from dataclasses import dataclass

@dataclass(frozen=True)
class Point:
    x: float
    y: float

Vector operations:

@dataclass(frozen=True)
class Vector:
    x: float
    y: float

Rectangles:

@dataclass(frozen=True)
class Rectangle:
    left: float
    bottom: float
    right: float
    top: float

Segments:

@dataclass(frozen=True)
class Segment:
    start: Point
    end: Point

Polygons:

@dataclass
class Polygon:
    vertices: list[Point]

Keep the primitives simple.

Complexity belongs in algorithms, not data containers.

Centralizing Predicates

Avoid scattering orientation logic throughout the codebase.

Instead:

def orientation(a, b, c):
    return (
        (b.x - a.x) * (c.y - a.y)
        -
        (b.y - a.y) * (c.x - a.x)
    )

Then reuse it everywhere:

convex hull
segment intersection
point-in-polygon
rotating calipers
half-plane intersection

A bug fixed in one place automatically improves every dependent algorithm.

Bounding Boxes First

Many expensive geometric operations can be preceded by a cheap bounding-box test.

For segments:

def segment_box(segment):
    return Rectangle(
        min(segment.start.x, segment.end.x),
        min(segment.start.y, segment.end.y),
        max(segment.start.x, segment.end.x),
        max(segment.start.y, segment.end.y)
    )

Before computing a precise intersection:

if not boxes_intersect(
    segment_box(a),
    segment_box(b)
):
    return False

This pattern appears constantly in practical geometry software.

Layered Query Architecture

A common architecture:

spatial index
    ↓
bounding-box filter
    ↓
exact predicate

Example:

R-tree
    ↓
candidate polygons
    ↓
point-in-polygon

Or:

spatial hash
    ↓
candidate objects
    ↓
exact collision test

This separation improves performance without compromising correctness.

Convex vs General Geometry

Many algorithms become dramatically simpler on convex inputs.

For example:

Problem	General Polygon	Convex Polygon
Point containment	O(n)	O(log n) possible
Diameter	Complex	Rotating calipers
Intersection	More difficult	Simpler
Optimization	Harder	Easier

Whenever possible:

general geometry
        ↓
convex decomposition
        ↓
convex algorithms

This strategy appears in physics engines and optimization systems.

Immutable Geometry Objects

Geometry objects often benefit from immutability.

@dataclass(frozen=True)
class Point:
    x: float
    y: float

Advantages:

thread safety
easier debugging
predictable behavior
hashability

Mutable structures are usually reserved for performance-critical code.

Separating Predicates and Constructions

Consider segment intersection.

Predicate:

segments_intersect(a, b)

Construction:

segment_intersection_point(a, b)

Do not combine them unnecessarily.

Many algorithms need only:

yes/no

answers.

Computing intersection coordinates every time wastes work and increases numerical exposure.

A useful design:

if segments_intersect(a, b):
    point = segment_intersection_point(a, b)

The expensive operation happens only when necessary.

Coordinate Systems

Many geometry bugs arise from mixed coordinate systems.

Examples:

screen coordinates
world coordinates
tile coordinates
geographic coordinates

A geometry library should clearly define:

units
origin
axis directions
projection assumptions

For example:

screen:
y increases downward

mathematics:
y increases upward

Mixing the two silently can invert orientation tests.

Geometry Pipelines

Practical applications often follow a geometric pipeline.

Example:

raw points
    ↓
deduplicate
    ↓
convex hull
    ↓
diameter

Or:

polygons
    ↓
spatial index
    ↓
candidate selection
    ↓
exact intersection

Or:

GPS coordinates
    ↓
projection
    ↓
spatial query
    ↓
visualization

Thinking in pipelines simplifies system design.

Testing Geometric Software

Geometry requires more than ordinary unit tests.

Include:

duplicate points
collinear points
large coordinates
small coordinates
touching boundaries
overlapping objects
empty inputs
single-point inputs
degenerate polygons

Randomized testing is especially useful.

Example:

for _ in range(10000):
    points = random_points()

    assert (
        convex_hull(points)
        ==
        reference_convex_hull(points)
    )

Comparing against a slower reference implementation often reveals subtle bugs.

Using Existing Libraries

For production systems, consider established geometry libraries rather than implementing everything from scratch.

Examples include:

entity["software","CGAL","Computational Geometry Algorithms Library"]
entity["software","GEOS","Geometry Engine Open Source"]
entity["software","JTS Topology Suite","Java geometry library"]
entity["software","Shapely","Python geometry library"]
entity["software","Boost.Geometry","C++ geometry library"]

These libraries provide:

robust predicates
polygon operations
spatial indexes
topological validation
coordinate transforms

and have received extensive real-world testing.

Common Design Patterns

Several patterns appear repeatedly.

Broad Phase Then Narrow Phase

spatial index
    ↓
candidate set
    ↓
exact geometry

Filter Then Refine

bounding box
    ↓
precise test

Convex Reduction

general shape
    ↓
convex pieces
    ↓
simpler algorithms

Coordinate Compression

large coordinates
    ↓
compressed coordinates
    ↓
efficient data structure

Exact Predicate, Approximate Construction

robust decision
    ↓
approximate coordinate output

This pattern often yields the best balance between correctness and performance.

Complexity Awareness

Geometry libraries should expose algorithmic expectations.

Examples:

Operation	Complexity
Orientation	O(1)
Segment intersection	O(1)
Convex hull	O(n log n)
Closest pair	O(n log n)
KD-tree query	O(log n) average
Point-in-polygon	O(n)
Polygon area	O(n)

Making these costs visible helps users select the appropriate algorithm.

Common Pitfalls

Reimplementing Everything

Many geometric operations are surprisingly subtle.

Mixing Integer and Floating Arithmetic

Conversions should be explicit.

Ignoring Degenerate Inputs

Real-world data is rarely ideal.

Coupling Algorithms Too Tightly

Reusable predicates and utilities reduce duplication.

Assuming Visual Correctness

Rendered output may appear correct while topology is invalid.

Discussion

Practical computational geometry is less about individual algorithms and more about composition. Convex hulls rely on orientation tests. Sweep-line algorithms rely on interval structures. Spatial indexes rely on bounding boxes. Voronoi diagrams connect naturally to Delaunay triangulations. The same small collection of predicates and representations appears repeatedly.

A well-designed geometry library reflects this structure. It provides reliable primitives, keeps geometric decisions centralized, separates filtering from exact computation, and treats robustness as a first-class concern. With those foundations in place, even sophisticated geometric systems become manageable.