17.25 Case Studies

Problem

Individual geometry algorithms are useful, but real systems usually require several of them working together.

A practical geometry task rarely says only:

compute a convex hull

or:

test one segment intersection

Instead, it asks for a result such as:

find all buildings inside a map region
detect collisions among moving objects
measure total occupied area
simplify a point cloud
plan a path through obstacles

These tasks combine predicates, indexing, sweep-line methods, polygon operations, and numeric policies.

This section walks through common end-to-end patterns.

Case Study 1: Finding Points Inside a Region

Suppose you have:

millions of points
one polygonal region

and need to find all points inside the polygon.

A brute-force solution applies point-in-polygon to every point:

O(nm)

where:

n = number of points
m = number of polygon vertices

A better pipeline is:

polygon bounding box
    ↓
spatial index query
    ↓
point-in-polygon exact test

Implementation sketch:

def points_inside_region(index, polygon):
    box = polygon.bounding_box

    candidates = index.range_query(box)

    return [
        point
        for point in candidates
        if classify_point_in_polygon(point, polygon) != "outside"
    ]

The spatial index removes most irrelevant points. The exact predicate preserves correctness.

Case Study 2: Broad-Phase Collision Detection

A game or simulation may need to detect possible collisions among many moving objects.

Checking every pair costs:

O(n²)

Instead, use a spatial hash.

Pipeline:

clear hash
insert object bounding boxes
generate candidate pairs
run exact collision tests

Sketch:

def collision_pairs(objects, cell_size):
    cells = build_spatial_hash(objects, cell_size)
    tested = set()
    result = []

    for bucket in cells.values():
        for i in range(len(bucket)):
            for j in range(i + 1, len(bucket)):
                a = bucket[i]
                b = bucket[j]

                key = pair_key(a, b)

                if key in tested:
                    continue

                tested.add(key)

                if exact_collision(a, b):
                    result.append((a, b))

    return result

The spatial hash provides candidates. The exact collision predicate decides the result.

This is the broad-phase then narrow-phase pattern.

Case Study 3: Measuring Map Coverage

Suppose a map system needs the total area covered by rectangular tiles, imagery patches, or bounding boxes.

Naively summing areas double-counts overlaps.

Use the rectangle union algorithm:

rectangles
    ↓
vertical sweep events
    ↓
active y-interval coverage
    ↓
area accumulation

For moderate inputs, recompute merged intervals at each step.

For large inputs, use coordinate compression plus a segment tree.

The important invariant is:

active y-intervals describe coverage between previous_x and current_x

This invariant keeps the implementation correct.

Case Study 4: Cleaning a Point Cloud

Point clouds often contain duplicates or near-duplicates.

Goal:

merge points closer than eps

Pipeline:

spatial hash with cell size eps
    ↓
nearby-cell search
    ↓
exact distance check
    ↓
merge or keep

Sketch:

def deduplicate_points(points, eps):
    index = SpatialHash(eps)
    result = []

    for point in points:
        duplicate = None

        for candidate in index.radius_query(point, eps):
            duplicate = candidate
            break

        if duplicate is None:
            result.append(point)
            index.insert(point)

    return result

This avoids comparing each point with every previously accepted point.

Case Study 5: Building an Autocomplete Map Boundary

Suppose you receive unordered GPS samples around a boundary and want a simple enclosing region.

One possible approximation:

points
    ↓
deduplicate
    ↓
convex hull
    ↓
optional rotating-calipers measurement

Sketch:

def enclosing_boundary(points):
    cleaned = deduplicate_exact(points)
    hull = convex_hull(cleaned)

    return hull

This produces a convex enclosure, not the true boundary. It is useful when the application needs a conservative outer shape.

For a concave boundary, use a different method, such as alpha shapes or polygon reconstruction.

The important lesson is to document the geometric meaning of the output.

Case Study 6: Nearest Facility Lookup

Given many facilities and many query locations, find the nearest facility for each query.

Possible choices:

KD-tree
Voronoi diagram
spatial hash

If you only need nearest-neighbor queries:

KD-tree

is usually simpler.

If you need visible service regions:

Voronoi diagram

is appropriate.

Pipeline with a KD-tree:

tree = build_kdtree(facilities)

for query in queries:
    facility, distance2 = nearest(tree, query)

Pipeline with Voronoi:

build diagram
locate query point in cell
return owning site

Both solve nearest-facility lookup, but they optimize for different needs.

Case Study 7: Polygon Intersection Queries

Suppose you have thousands of polygons and need to find which ones intersect a query polygon.

Pipeline:

R-tree over polygon bounding boxes
    ↓
candidate polygons
    ↓
exact polygon intersection

Sketch:

def intersecting_polygons(index, query_polygon):
    candidates = index.search(query_polygon.bounding_box)

    return [
        polygon
        for polygon in candidates
        if polygons_intersect(polygon, query_polygon)
    ]

This is a standard spatial-database pattern.

The index avoids scanning every polygon. The exact predicate avoids false positives.

Case Study 8: Segment Intersection Report

Given many line segments, report all intersections.

Brute force:

O(n²)

Sweep-line approach:

events
    ↓
active segment order
    ↓
neighbor checks
    ↓
reported intersections

For a small script, brute force may be acceptable and easier to verify.

For large input, use a sweep-line algorithm such as Bentley-Ottmann.

Decision rule:

small n or one-off tool: brute force
large n or repeated workload: sweep line

Do not pay implementation complexity unless the input size requires it.

Case Study 9: Mesh Preprocessing

A mesh pipeline often needs to:

remove duplicate vertices
detect degenerate triangles
compute triangle areas
build adjacency
validate orientation

Geometry primitives used:

distance comparison
area2
orientation
spatial hashing
bounding boxes

Sketch:

def triangle_area2(a, b, c):
    return abs(orientation(a, b, c))

Degenerate triangle:

def is_degenerate_triangle(a, b, c):
    return triangle_area2(a, b, c) == 0

If coordinates are floating-point, use a robust sign policy instead of direct equality.

Case Study 10: Path Planning with Obstacles

A simple visibility-graph planner uses:

obstacle vertices
start point
goal point
segment intersection
shortest path

Pipeline:

collect vertices
connect visible pairs
run Dijkstra

Visibility test:

def visible(a, b, obstacles):
    candidate = Segment(a, b)

    for obstacle in obstacles:
        for edge in obstacle.edges():
            if segments_intersect(candidate.start, candidate.end, edge.start, edge.end):
                return False

    return True

This is conceptually simple but can be slow.

Spatial indexes can speed up obstacle-edge lookup.

The final shortest path step belongs to graph algorithms, showing how geometry and graph algorithms combine.

Choosing the Right Tool

A useful decision table:

Task	Typical Tool
Outer boundary of points	Convex hull
Maximum distance on hull	Rotating calipers
Total rectangle coverage	Sweep line
Nearby point lookup	KD-tree or spatial hash
Polygon containment	Point-in-polygon
Collision broad phase	Spatial hash or BVH
Spatial database query	R-tree
Nearest service regions	Voronoi diagram
Mesh triangles	Delaunay triangulation
Exact segment crossing	Orientation tests

The table is a starting point, not a rulebook. Data size, update frequency, and numeric requirements still matter.

Building Reliable Pipelines

A reliable geometry pipeline usually follows this order:

normalize input
validate degeneracies
build cheap filters
run exact predicates
cache derived data
test boundary cases

Example:

raw polygons
    ↓
remove duplicate vertices
    ↓
compute bounding boxes
    ↓
build R-tree
    ↓
query candidates
    ↓
exact intersection

Each stage has a clear responsibility.

Common Pitfalls

Using a Heavy Algorithm Too Early

A brute-force reference may be enough for small input and is easier to test.

Skipping the Exact Predicate

Indexes and bounding boxes produce candidates, not final answers.

Forgetting Numeric Policy

Integer, floating-point, and rational geometry require different assumptions.

Returning an Approximation Without Saying So

A convex hull is not a concave boundary.

A bounding box is not a polygon.

A spatial hash result is not a nearest-neighbor proof.

Mixing Algorithmic Domains

Many end-to-end tasks combine geometry with graphs, sorting, dynamic programming, or indexing. Keep those boundaries explicit.

Discussion

Computational geometry becomes practical when algorithms are composed into pipelines. A spatial index narrows the search, a bounding box rejects impossible cases, a predicate makes the exact decision, and a graph or optimization algorithm may consume the result.

The central lesson of this chapter is consistency. Use a single orientation convention. Define boundary behavior. Separate candidates from exact answers. Preserve numeric assumptions. Test degenerate cases deliberately. These habits matter more than any single algorithm.

Geometry is unforgiving because tiny decisions can alter topology. It is also highly reusable because the same primitives appear everywhere. Once you trust your predicates, indexes, and boundary conventions, the rest of the system becomes much easier to build.