Geometric Algorithms

Nievergelt & Hinrichs · Ch. 8 · Algorithms and Data Structures

Convex hull wraps a point set in the smallest convex polygon. Graham scan does it in O(n log n). Line intersection, closest pair, and Voronoi diagrams extend these ideas to richer geometric problems.

Cross product orientation test

The foundation of computational geometry. Given three points P, Q, R: the cross product (Q-P) x (R-P) tells you whether R is left of, right of, or on the line PQ. Positive = left turn, negative = right turn, zero = collinear.

Scheme

; Cross product: orientation test
; (Q-P) x (R-P) > 0 means left turn (counterclockwise)

(define (cross px py qx qy rx ry)
  (- (* (- qx px) (- ry py))
     (* (- qy py) (- rx px))))

; Three points: P=(0,0), Q=(1,0), R=(0,1)
(display "P(0,0) Q(1,0) R(0,1): ")
(display (cross 0 0 1 0 0 1)) (newline)  ; positive = left turn

(display "P(0,0) Q(1,0) R(0,-1): ")
(display (cross 0 0 1 0 0 -1)) (newline)  ; negative = right turn

(display "P(0,0) Q(1,0) R(2,0): ")
(display (cross 0 0 1 0 2 0))  ; zero = collinear

Graham scan

Sort points by polar angle around the lowest point. Walk through the sorted points, keeping only left turns. O(n log n) for the sort, O(n) for the scan.

Scheme

; Graham scan: convex hull in O(n log n)
; Simplified version using sorted-by-x approach

(define points
  (list (list 0 0) (list 1 3) (list 2 1) (list 3 4)
        (list 4 2) (list 5 0) (list 2 2) (list 3 1)))

(define (cross-val p q r)
  (- (* (- (car q) (car p)) (- (cadr r) (cadr p)))
     (* (- (cadr q) (cadr p)) (- (car r) (car p)))))

; Sort by x, then y
(define sorted
  (sort points (lambda (a b)
    (or (< (car a) (car b))
        (and (= (car a) (car b)) (< (cadr a) (cadr b)))))))

; Build upper and lower hulls
(define (build-half pts)
  (fold-left
    (lambda (hull p)
      (let loop ((h hull))
        (if (and (>= (length h) 2)
                 (<= (cross-val (list-ref h (- (length h) 2))
                                (list-ref h (- (length h) 1))
                                p) 0))
            (loop (reverse (cdr (reverse h))))
            (append h (list p)))))
    (list) pts))

(define upper (build-half sorted))
(define lower (build-half (reverse sorted)))

(define hull (append (reverse (cdr (reverse upper)))
                     (reverse (cdr (reverse lower)))))

(display "Hull: ") (display hull)

; Graham scan: convex hull in O(n log n)
; Simplified version using sorted-by-x approach

(define points
  (list (list 0 0) (list 1 3) (list 2 1) (list 3 4)
        (list 4 2) (list 5 0) (list 2 2) (list 3 1)))

(define (cross-val p q r)
  (- (* (- (car q) (car p)) (- (cadr r) (cadr p)))
     (* (- (cadr q) (cadr p)) (- (car r) (car p)))))

; Sort by x, then y
(define sorted
  (sort points (lambda (a b)
    (or (< (car a) (car b))
        (and (= (car a) (car b)) (< (cadr a) (cadr b)))))))

; Build upper and lower hulls
(define (build-half pts)
  (fold-left
    (lambda (hull p)
      (let loop ((h hull))
        (if (and (>= (length h) 2)
                 (<= (cross-val (list-ref h (- (length h) 2))
                                (list-ref h (- (length h) 1))
                                p) 0))
            (loop (reverse (cdr (reverse h))))
            (append h (list p)))))
    (list) pts))

(define upper (build-half sorted))
(define lower (build-half (reverse sorted)))

(define hull (append (reverse (cdr (reverse upper)))
                     (reverse (cdr (reverse lower)))))

(display "Hull: ") (display hull)

Neighbors

Cross-references

∫ Calculus Ch.10 — vectors: the linear algebra behind cross products and projections
june.kim/power-diagrams-ad-auctions — Voronoi diagrams with weighted sites partition embedding space for ad targeting
june.kim/keywords-are-tiny-circles — keywords as degenerate Voronoi cells in continuous space

← Shortest Paths by june.kim Dynamic Programming →