Computational Geometry Basics: Cross Product, Segments, Polygons and Convex Hull

Interview geometry is mostly about one operation: the 2D cross product. It tells you which way three points turn, whether two segments cross, how large a polygon is, and which points form the convex hull. With integer coordinates, all of it can be done exactly, without a single floating-point comparison.

Intuition

Treat points as vectors. For vectors u = (ux, uy) and v = (vx, vy):

• Dot product ux*vx + uy*vy = |u| |v| cos(angle): positive for an acute angle, zero for perpendicular, negative for obtuse. Useful for projections and right-angle checks.
• Cross product ux*vy - uy*vx = |u| |v| sin(angle): the signed area of the parallelogram spanned by u and v. Positive when v is counter-clockwise from u, negative when clockwise, zero when they are parallel.

For three points, cross(o, a, b) is the cross product of a - o and b - o. Its sign is the orientation: a left turn (counter-clockwise), a right turn, or collinear. Everything below is built from that one sign.

• Segment intersection: segments AB and CD properly cross iff C and D are on opposite sides of line AB and A and B are on opposite sides of line CD. Touching and overlapping cases reduce to "is an endpoint on the other segment".
• Polygon area (shoelace formula): summing cross(origin, p[i], p[i+1]) over the edges gives twice the signed area; it is positive for counter-clockwise vertex order.
• Point in polygon (ray casting): shoot a ray to the right; it crosses the boundary an odd number of times iff the point is inside.
• Convex hull (Andrew's monotone chain): sort points by x, then sweep left to right building the lower hull and right to left building the upper hull, popping the last point whenever it would make a clockwise turn.

When to use it in interviews / OAs

• "Do these segments/rectangles intersect", "is the polygon convex", "are these points collinear".
• "Area of a polygon given its vertices", "smallest fence around all trees" (convex hull).
• "Max points on a line" (orientation or normalized slopes), "valid square", "minimum area rectangle" (dot/cross products and squared distances).
• Any time a solution compares slopes or angles with floats: rewrite it with cross products.

Template: primitives

def cross(o, a, b) -> int:
    # cross product of (a - o) and (b - o): > 0 left turn, < 0 right turn, 0 collinear
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])


def dot(o, a, b) -> int:
    # dot product of (a - o) and (b - o): > 0 acute angle at o, 0 right angle, < 0 obtuse
    return (a[0] - o[0]) * (b[0] - o[0]) + (a[1] - o[1]) * (b[1] - o[1])


def orientation(a, b, c) -> int:
    v = cross(a, b, c)
    return (v > 0) - (v < 0)


def on_segment(p, a, b) -> bool:
    # p lies on the closed segment a-b
    return (cross(a, b, p) == 0
            and 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 segments_intersect(p1, p2, p3, p4) -> bool:
    d1, d2 = orientation(p3, p4, p1), orientation(p3, p4, p2)
    d3, d4 = orientation(p1, p2, p3), orientation(p1, p2, p4)
    if d1 * d2 < 0 and d3 * d4 < 0:
        return True  # a proper crossing
    # otherwise they meet only if an endpoint lies on the other segment
    return on_segment(p1, p3, p4) or on_segment(p2, p3, p4) or on_segment(p3, p1, p2) or on_segment(p4, p1, p2)

Template: polygons

def polygon_area2(poly) -> int:
    # twice the signed area (shoelace formula); positive for counter-clockwise order
    n = len(poly)
    return sum(poly[i][0] * poly[(i + 1) % n][1] - poly[(i + 1) % n][0] * poly[i][1] for i in range(n))


def polygon_area(poly) -> float:
    return abs(polygon_area2(poly)) / 2


def point_in_polygon(p, poly) -> int:
    # 1 inside, 0 on the boundary, -1 outside; works for any simple polygon
    inside = False
    n = len(poly)
    for i in range(n):
        a, b = poly[i], poly[(i + 1) % n]
        if on_segment(p, a, b):
            return 0
        if (a[1] > p[1]) != (b[1] > p[1]):  # the edge straddles the horizontal line through p
            # the crossing is to the right of p iff p is left of the upward-directed edge
            if (cross(a, b, p) > 0) == (b[1] > a[1]):
                inside = not inside
    return 1 if inside else -1

The half-open test (a.y > p.y) != (b.y > p.y) counts a vertex lying exactly on the ray once, not twice, which is the usual source of ray-casting bugs.

Template: convex hull

def convex_hull(points, keep_collinear: bool = False):
    # Andrew's monotone chain; hull vertices in counter-clockwise order
    pts = sorted(set(points))
    if len(pts) <= 2:
        return pts
    limit = 0 if keep_collinear else 1  # pop on clockwise turns (and on straight ones unless kept)

    def chain(seq):
        out = []
        for p in seq:
            while len(out) >= 2 and cross(out[-2], out[-1], p) < limit:
                out.pop()
            out.append(p)
        return out

    lower, upper = chain(pts), chain(reversed(pts))
    hull = lower[:-1] + upper[:-1]  # each chain ends where the other one starts
    return list(dict.fromkeys(hull))  # all-collinear input makes the chains overlap

keep_collinear=True keeps points that lie on hull edges (needed when every fence post on the boundary must be reported); the default returns only the corners.

Complexity

Orientation, intersection and on-segment tests are O(1). Area and point-in-polygon are O(n) for n vertices. The convex hull is O(n log n) for the sort plus O(n) for the two sweeps, since every point is pushed and popped at most once per chain.

Common pitfalls

• Floating point: comparing slopes or angles with == fails; integer cross products are exact. If coordinates are up to 10^9, products reach 10^18, which still fits in a signed 64-bit integer, but sums of them may not.
• Vertical lines: slope-based code needs special cases; cross products do not.
• Collinear and touching cases: segments that share an endpoint or overlap along a line are intersections; test them with on_segment.
• Orientation of the polygon: the shoelace sum is negative for clockwise input; take the absolute value for the area.
• Hull degeneracies: duplicate points, fewer than three points, or all points on one line. Deduplicate first and decide whether collinear boundary points belong in the answer.
• Ray casting through vertices: use the half-open rule above instead of counting both edges at a shared vertex.

Interview variations

• Erect the fence (all trees on the boundary): convex hull with collinear points kept.
• Check if it is a straight line: every cross(p0, p1, pi) is zero.
• Convex polygon check: all consecutive cross products have the same sign.
• Valid square: among the six squared distances, four equal sides and two equal, longer diagonals.
• Rectangle overlap / area: axis-aligned boxes overlap iff their x-ranges and y-ranges both overlap.
• Minimum area rectangle from points: diagonal pairs with equal midpoints and lengths (or perpendicular sides via dot products).
• Max points on a line: count collinear points per anchor with normalized directions or cross products.