Computational Geometry Basics: Orientation, Line Intersection, and Convex Hull

Why Geometric Problems Need Their Own Techniques

Problems involving points, lines, and polygons in the plane cannot be solved using the comparison-based techniques covered throughout most of this series. Instead, computational geometry relies heavily on a small set of basic geometric primitives, most importantly a test for the relative orientation of points, from which nearly all more complex geometric algorithms are built.

The Cross Product and the Orientation Test

Given three points p1, p2, and p3, a fundamental question is whether the path from p1 to p2 to p3 turns left (counterclockwise), turns right (clockwise), or the three points are collinear. This is determined using the Cross Product of the two vectors formed by these points.

Define vectors:
v1 = p2 - p1 = (p2.x - p1.x, p2.y - p1.y)
v2 = p3 - p1 = (p3.x - p1.x, p3.y - p1.y)

Cross product (a scalar in 2D):
cross(v1, v2) = v1.x · v2.y - v1.y · v2.x

If cross > 0: the turn from p1→p2→p3 is counterclockwise (left turn)
If cross < 0: the turn from p1→p2→p3 is clockwise (right turn)
If cross == 0: the three points are collinear

This single test, computable in O(1) time using only multiplication and subtraction (no expensive trigonometric functions or square roots needed), is the fundamental building block for nearly every algorithm covered in this article.

Determining Whether Two Line Segments Intersect

Given two line segments, determining whether they cross can be solved elegantly using the orientation test twice, checking whether each segment's endpoints straddle the line containing the other segment.

SEGMENTS-INTERSECT(p1, p2, p3, p4):
  d1 = ORIENTATION(p3, p4, p1)
  d2 = ORIENTATION(p3, p4, p2)
  d3 = ORIENTATION(p1, p2, p3)
  d4 = ORIENTATION(p1, p2, p4)
  
  if ((d1 > 0 and d2 < 0) or (d1 < 0 and d2 > 0)) and
     ((d3 > 0 and d4 < 0) or (d3 < 0 and d4 > 0)):
      return TRUE       // segments properly cross
  
  // handle collinear special cases (boundary touching) separately
  if d1 == 0 and ON-SEGMENT(p3, p4, p1): return TRUE
  if d2 == 0 and ON-SEGMENT(p3, p4, p2): return TRUE
  if d3 == 0 and ON-SEGMENT(p1, p2, p3): return TRUE
  if d4 == 0 and ON-SEGMENT(p1, p2, p4): return TRUE
  
  return FALSE

The core insight is intuitive: two segments cross if and only if each segment's two endpoints lie on opposite sides of the line containing the other segment. The orientation test computed twice for each segment (checking both endpoints of the other segment against it) determines exactly this condition, with special-case handling needed only for the boundary case of collinear points, where the simple sign-based test alone is insufficient.

The Convex Hull Problem

The Convex Hull of a set of points is the smallest convex polygon that contains all of them — intuitively, the shape formed by stretching a rubber band around all the points and letting it snap tight. This has practical applications in collision detection, pattern recognition, and geographic boundary computation.

Graham's Scan: Computing the Convex Hull

Graham's Scan computes the convex hull efficiently using a sorting step followed by a single scan that relies entirely on the orientation test introduced above.

GRAHAM-SCAN(Q):
  let p0 be the point in Q with the lowest y-coordinate
  (breaking ties by lowest x-coordinate)

  sort the remaining points by polar angle relative to p0,
  counterclockwise (using the orientation test to compare angles
  without needing to compute actual angle values)

  let ⟨p1, p2, ..., pn⟩ be the sorted points
  push p0, then p1 onto a stack S
  for i = 2 to n:
      while the last three points on S (with pi) make a
            non-left turn (orientation ≤ 0):
          pop the top of S
      push pi onto S
  return S    // the stack now contains exactly the hull vertices,
              // in counterclockwise order

Why This Algorithm Works

Sorting points by angle around the lowest point ensures they are processed in an order that a correct hull traversal would naturally follow. As each new point is considered, the algorithm checks whether adding it would create a "right turn" or straight line with the previous two points on the stack — if so, the previous point cannot be part of the convex hull (it lies inside the shape formed by the surrounding points) and is removed. This process, using the orientation test at every step, correctly identifies and retains only the points that form the actual boundary of the convex shape.

Example intuition:
If points A, B, C are being considered in order,
and the turn from A to B to C is clockwise (a "right turn"),
then B lies inside the hull relative to A and C,
and must be removed from consideration

Analyzing the Running Time

Sorting the points by polar angle takes O(n log n) time, using the comparison-based sorting algorithms discussed earlier in this series. The scanning phase, despite containing a nested while loop, runs in O(n) total time: each point is pushed onto the stack exactly once and popped at most once, giving O(n) total stack operations across the entire scan, using the amortized analysis reasoning discussed earlier in this series. The overall running time is therefore O(n log n), dominated by the initial sort.

Why Computational Geometry Relies So Heavily on One Simple Test

The orientation test introduced at the start of this article is, remarkably, the single computational primitive underlying nearly every algorithm in this field: segment intersection, convex hull construction, point-in-polygon testing, and many more advanced algorithms not covered here all reduce to repeated, careful application of this one simple cross-product calculation. This is a striking example of a recurring theme across this entire series: identifying the right small, efficient primitive operation is often the key that unlocks solutions to an entire family of more complex problems.

Why These Algorithms Matter in Practice

Convex hull algorithms are used in computer graphics for collision detection and mesh simplification, in geographic information systems for computing minimal bounding regions, and in robotics for path planning around obstacles. Line segment intersection detection is fundamental to computer-aided design software, video game physics engines, and map-rendering systems that need to determine how roads, boundaries, or shapes overlap. Together, these algorithms exemplify how geometric problems, despite their visual