Computational Geometry Basics: Cross Products, Convex Hull, Line Intersection

Algorithm/Topic Statement#

Computational geometry studies algorithms that operate on points, lines, polygons, and other spatial structures. The big four primitives every interviewer expects you to know are the cross product orientation test, segment intersection, convex hull construction, and polygon area via the shoelace formula. The cross product, despite its name, is just a single integer expression that tells you whether three points turn left, turn right, or are collinear. From that single primitive you can derive almost every other geometric algorithm that appears in interviews and contests, including which side of a line a point lies on, whether two segments cross, and how Graham scan or Andrew's monotone chain build a convex hull in order n log n time.

Why This Topic Matters#

Self-driving cars, mapping software, robotics, computer vision, and games all rely on computational geometry. Companies that build location-based products, like Uber, DoorDash, Airbnb, and Lyft, ask geometry questions to test whether candidates can reason about space without devolving into floating point chaos. Geometry questions also reward candidates who use integer arithmetic, because keeping coordinates and cross products in 64-bit integers avoids almost every classical bug. Even at general tech companies, problems like erect the fence, max points on a line, and convex polygon detection appear in onsite rounds. Beyond interviews, the techniques here generalize to physics simulations, computer graphics, GIS systems, and machine learning models that work on geometric features.

The Core Insight (math intuition + proof sketch)#

The cross product of two vectors AB and AC is defined as the difference of two products: B minus A in the x direction times C minus A in the y direction, minus B minus A in the y direction times C minus A in the x direction. Geometrically this number equals the signed area of the parallelogram spanned by AB and AC, with positive meaning C is to the left of the directed line AB and negative meaning C is to the right. Zero means collinear. The proof comes from the determinant interpretation of two-dimensional vectors and the formula for the area of a triangle in terms of coordinates.

From this single primitive almost every test in two-dimensional geometry follows. Two segments AB and CD intersect strictly if A and B are on opposite sides of line CD and C and D are on opposite sides of line AB. The convex hull of a point set is the smallest convex polygon containing all the points, and Andrew's monotone chain algorithm builds it by sorting points and walking left to right while popping any point that produces a non-left turn. The proof of correctness uses the invariant that after processing each point, the partial hull is exactly the convex hull of all points seen so far. The shoelace formula computes a polygon's area as one half the absolute value of the alternating sum of cross products around its boundary, which follows from triangulating the polygon and summing signed triangle areas.

Visual Dry Run / Worked Example#

Take four points 0, 0, then 4, 0, then 4, 4, and 0, 4 forming a unit square scaled by four. To find the convex hull, sort by x then y: the order is already 0, 0, then 0, 4, then 4, 0, then 4, 4. Build the lower hull. Push 0, 0. Push 0, 4. Push 4, 0. Now check the cross product of the last three: from 0, 0 to 0, 4 to 4, 0. The cross is 0 minus 0 times 0 minus 0 minus 4 minus 0 times 4 minus 0, which is negative sixteen. Negative means right turn, so pop 0, 4. Push 4, 4. The lower hull is 0, 0, then 4, 0, then 4, 4. Build the upper hull in reverse: 0, 0, then 0, 4, then 4, 4. The full hull joins both pieces while removing duplicate endpoints, giving 0, 0, then 4, 0, then 4, 4, then 0, 4.

For polygon area on the same square, apply the shoelace. The alternating sum is 0 times 0 minus 4 times 0, then 4 times 4 minus 4 times 0, then 4 times 4 minus 0 times 4, then 0 times 0 minus 0 times 4. Sum the cross terms and take half the absolute value to get sixteen, the correct area.

Solution / Implementation#

Python (orientation, hull, area)#

def cross(O, A, B):
    return (A[0]-O[0])*(B[1]-O[1]) - (A[1]-O[1])*(B[0]-O[0])
 
def on_segment(A, B, P):
    if cross(A, B, P) != 0:
        return False
    return (min(A[0], B[0]) <= P[0] <= max(A[0], B[0])
            and min(A[1], B[1]) <= P[1] <= max(A[1], B[1]))
 
def convex_hull(points):
    points = sorted(set(map(tuple, points)))
    if len(points) <= 1:
        return points
    def build(pts):
        hull = []
        for p in pts:
            while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
                hull.pop()
            hull.append(p)
        return hull
    return build(points) + build(points[::-1])[1:-1]
 
def polygon_area(pts):
    n = len(pts)
    area = 0
    for i in range(n):
        j = (i + 1) % n
        area += pts[i][0] * pts[j][1] - pts[j][0] * pts[i][1]
    return abs(area) / 2

JavaScript#

function cross(O, A, B) {
  return (A[0]-O[0]) * (B[1]-O[1]) - (A[1]-O[1]) * (B[0]-O[0]);
}
 
function convexHull(points) {
  const pts = [...new Set(points.map(p => p.join(',')))]
    .map(s => s.split(',').map(Number))
    .sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  if (pts.length <= 1) return pts;
  const build = (arr) => {
    const hull = [];
    for (const p of arr) {
      while (hull.length >= 2 && cross(hull[hull.length-2], hull[hull.length-1], p) <= 0) {
        hull.pop();
      }
      hull.push(p);
    }
    return hull;
  };
  const lower = build(pts);
  const upper = build(pts.slice().reverse());
  return lower.concat(upper.slice(1, -1));
}

Convex hull is order n log n due to sorting. Cross product, on segment, and segment intersection tests are constant time. Shoelace area is order n.

Common Mistakes#

The deadliest mistake is using floating point coordinates when integers would do. Squared distances, cross products, and polygon areas all work in pure integer arithmetic and avoid the entire class of epsilon bugs. If you must use floats, define an epsilon and stick with it. Another trap is treating collinear points incorrectly in the convex hull. Decide upfront whether the cross product comparison is strict, less than zero, or non-strict, less than or equal to zero. The strict variant keeps collinear hull points; the non-strict variant removes them. Pick whichever matches the problem statement. Many candidates also forget that the shoelace formula returns a signed area, so taking absolute value at the end is required for unsigned area. Finally, segment intersection is subtle when endpoints overlap; always handle the collinear edge cases with explicit on-segment checks.

Interview Tips#

Lead with the cross product. When you state your approach, derive every other test from it, demonstrating you understand the underlying primitive rather than memorizing recipes. Ask whether the input has integer coordinates and clarify the bounds, because that determines whether you should use 64-bit integers or floats. For convex hull problems, walk the interviewer through the lower and upper hull construction. For point in polygon, mention both the ray casting algorithm and the winding number method, comparing tradeoffs. These narrations show senior-level computational geometry maturity that distinguishes you from rote candidates.

Follow-up Questions#

How would you compute the closest pair of points in order n log n using divide and conquer? Could you describe Andrew's monotone chain in your own words and prove its correctness? How does the half-plane intersection algorithm work, and what is its complexity? Can you implement a robust segment intersection routine that returns the intersection point, not just yes or no?

Key Takeaways#

• The cross product of three points tells you orientation: positive for left turn, negative for right turn, zero for collinear.
• Convex hull in order n log n uses Andrew's monotone chain or Graham scan, popping points whenever the cross product violates the desired turn direction.
• The shoelace formula computes polygon area as half the absolute value of the alternating sum of cross terms around the boundary.
• Prefer integer arithmetic for coordinates whenever the input allows, since it avoids almost all geometric bugs.
• Segment intersection requires both the cross product tests and explicit on-segment handling for collinear edge cases.
• These primitives unlock dozens of derived algorithms used in mapping, robotics, games, and computer vision.