Computational Geometry Algorithms

10-page quick guide for points, distances, orientation, hulls, and geometry edge cases.

Purpose: a compact 10-page study guide for students who want to recognize, choose, and implement common
algorithm ideas.
How to use it: read one page, trace the example, then solve the quick practice before moving on.

Symbol Meaning

n input size: number of items, characters, nodes, or records

O(...) upper-bound growth rate used to compare algorithms

stable keeps equal items in their original relative order

in-place uses only small extra memory beyond the input array

Computational Geometry Algorithms Page 1

 1. Computational Geometry Basics
Computational geometry algorithms solve problems involving points, lines, polygons, distances, and shapes. They
appear in games, maps, robotics, CAD, and computer vision.

- Always define the coordinate system before coding.

- Floating-point errors can change equality checks; use tolerance when appropriate.
- Many algorithms depend on orientation: clockwise, counterclockwise, or collinear.
- A good diagram often reveals the algorithm.

Object Common representation

Point (x, y)

Vector difference between two points

Line segment two endpoints

Polygon ordered list of vertices

Quick practice
- Draw points A(0,0), B(3,0), C(3,2).
- Is the polygon vertex order clockwise or counterclockwise?

Computational Geometry Algorithms Page 2

 2. Distance and Norms
Distance formulas compare points. Different applications use different distance rules.

- Euclidean distance is the straight-line distance.

- Manhattan distance counts horizontal plus vertical movement, useful for grids.
- Squared distance avoids square root and is enough for comparing which point is closer.
- Be careful with overflow if coordinates are large in fixed-size languages.

Distance Formula idea

Euclidean sqrt(dx^2 + dy^2)

Squared dx^2 + dy^2

Manhattan abs(dx) + abs(dy)

def dist2(a, b):

dx = a[0] - b[0]
dy = a[1] - b[1]
return dx*dx + dy*dy

Quick practice
- Compute squared distance from (0,0) to (3,4).
- Why can squared distance compare closeness?

Computational Geometry Algorithms Page 3

 3. Orientation Test
The orientation test tells whether three points make a left turn, right turn, or straight line. It is a core building block.

- Use the cross product sign of vectors AB and AC.

- Positive usually means counterclockwise, depending on coordinate convention.
- Zero means the points are collinear.
- Orientation is used in convex hull, segment intersection, and polygon tests.
def orientation(a, b, c):
value = (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])
if value > 0: return "ccw"
if value < 0: return "cw"
return "collinear

Quick practice
- Check orientation of (0,0), (1,0), (1,1).
- What does value 0 mean geometrically?

Computational Geometry Algorithms Page 4

 4. Segment Intersection
Two line segments intersect if their endpoints are on opposite sides of each other, with special handling for
collinear overlap.

- Use orientation tests for both segments.

- General case: segment AB straddles CD and CD straddles AB.
- Special case: collinear endpoints may lie on the other segment.
- This is useful for collision detection and map geometry.

Case Meaning

proper intersection segments cross at one interior point

touching one endpoint lies on the other segment

overlap collinear segments share many points

disjoint no shared point

Quick practice
- Draw two crossing segments and label the four endpoints.
- Why do collinear cases need extra checks?

Computational Geometry Algorithms Page 5

 5. Point in Polygon
Point-in-polygon algorithms decide whether a point is inside a polygon. A common method is ray casting.

- Cast a ray from the point to the right.

- Count how many polygon edges the ray crosses.
- Odd crossings means inside; even crossings means outside.
- Boundary cases, such as the point lying exactly on an edge, must be handled separately.
# Idea only:
# crossings = number of polygon edges crossing a horizontal ray
# if point_on_boundary: return 'boundary'
# return 'inside' if crossings % 2 == 1 else 'outside'

Quick practice
- Use a triangle and test one point inside and one outside.
- What should the algorithm return if the point is on an edge?

Computational Geometry Algorithms Page 6

 6. Convex Hull
The convex hull is the smallest convex polygon containing all points. It is like stretching a rubber band around a
set of nails.

- Graham scan and monotonic chain are common hull algorithms.

- Sort points, then maintain a stack of hull vertices.
- Remove points that create the wrong turn.
- Convex hull is used in shape analysis, collision, and geographic boundaries.

Algorithm Typical complexity

Gift wrapping O(nh), good when hull has few points

Graham scan O(n log n) because of sorting

Monotonic chain O(n log n), simple to implement

Quick practice
- Draw five points and sketch the rubber-band outline.
- Why does sorting appear in many hull algorithms?

Computational Geometry Algorithms Page 7

 7. Sweep Line Idea
Sweep line algorithms move an imaginary line across the plane while maintaining active objects. They turn
geometry into ordered events.

- Events may be segment starts, segment ends, or intersection points.

- The active set stores objects currently touched by the sweep line.
- Sorting events is usually the first step.
- Sweep line is powerful for detecting intersections and closest pairs.

Part Role

event important x-coordinate or y-coordinate to process

active set objects currently near the sweep line

invariant condition kept true after each event

complexity often O(n log n) plus output size

Quick practice
- Imagine sweeping left to right over three segments.
- What changes when the sweep line passes a segment endpoint?

Computational Geometry Algorithms Page 8

 8. Closest Pair of Points
The closest pair problem finds the two points with the smallest distance. A divide-and-conquer solution runs in O(n
log n).

- Sort points by x-coordinate.

- Recursively solve left and right halves.
- Check only a narrow strip near the dividing line.
- Geometry limits how many nearby points must be checked in the strip.
# High-level pattern:
# closest(points):
# split points into left and right
# d = min(closest(left), closest(right))
# check strip around the middle with width d
# return best pair

Quick practice
- Why can you ignore points farther than d from the split line?
- What sorting order is useful inside the strip?

Computational Geometry Algorithms Page 9

 9. Geometry Implementation Tips
Geometry bugs are often caused by equality, precision, and unclear conventions. Write helper functions and test
edge cases.

- Use named functions such as cross, dot, dist2, orientation, and on_segment.
- Prefer integer arithmetic when coordinates are integers and formulas allow it.
- For floats, compare abs(a-b) < epsilon instead of a == b.
- Test collinear points, duplicate points, vertical lines, and boundary points.

Risk Safer habit

floating equality use epsilon tolerance

overflow use larger integer type if needed

unclear orientation document coordinate convention

edge cases write unit tests for boundary inputs

Quick practice
- List three edge cases for segment intersection.
- Why is vertical line slope dangerous to compute directly?

Computational Geometry Algorithms Page 10