Skip to content
Tutorials Center
My learning

Topics

Lesson 186 of 225 ยท Math and Bit Manipulation

Computational Geometry Basics

Learn computational geometry in Python: the cross product, orientation tests, segment intersection, Andrew's convex hull and the shoelace polygon area.

Geometry problems look different from arrays and graphs, but they are solved with the same habits: find a small primitive operation, make it exact, and build everything on top of it. Maps, games, collision detection, drawing programs and robotics all depend on a handful of questions. Are these three points in a straight line? Do these two roads cross? What is the smallest fence that surrounds all the trees? How big is this plot of land?

Almost all of those questions can be answered with one tiny formula, the cross product. In this lesson you will learn it, use it to decide on which side of a line a point lies (the orientation test), check whether two segments intersect, build a convex hull with Andrew's monotone chain algorithm in O(n log n), and compute the area of a polygon with the shoelace formula.

Points and vectors

A point is a pair (x, y). A vector from point a to point b is (b.x - a.x, b.y - a.y). We will use plain tuples and keep all coordinates integers whenever possible. Floating-point numbers accumulate rounding errors, and a geometry test that asks "is this exactly zero?" gets unreliable quickly. Integer arithmetic in Python is exact and never overflows.

TEXT
y
4 |            b
3 |          /
2 |        /
1 |   a --+
0 +--------------- x
     0 1 2 3 4

vector a->b = (b.x - a.x, b.y - a.y)

The cross product and orientation

For two vectors u = (ux, uy) and v = (vx, vy), the 2D cross product is a single number:

cross(u, v) = ux * vy - uy * vx

Its sign tells you how v turns relative to u:

  • positive: v is counter-clockwise from u (a left turn),
  • negative: v is clockwise from u (a right turn),
  • zero: the vectors are parallel (the three points are collinear).

The magnitude is the area of the parallelogram the vectors span, which we use later for polygon areas.

For three points a, b, c, the orientation is the cross product of a->b and a->c. It answers: walking from a to b, do I turn left, right, or go straight to reach c?

TEXT
 left turn (+)        right turn (-)       collinear (0)

      c                  a ---- b          a -- b -- c
     /                          \
 a -- b                          c
Python Orientation of three points

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The orientation test uses only subtraction and multiplication, no division and no square root. That is why it is exact with integers. Whenever you can phrase a geometry question as "what is the sign of a cross product?", do it.

Do two segments intersect?

Segment p1-p2 and segment p3-p4 cross when the endpoints of each segment lie on opposite sides of the other segment's line. In orientation terms:

  • p3 and p4 give different signs with respect to p1->p2, and
  • p1 and p2 give different signs with respect to p3->p4.

That covers the general case. The special cases come from collinear points: if an orientation is zero, the endpoint touches the other line, and you must check whether it actually falls between the endpoints of the segment (a bounding-box test on x and y).

TEXT
 proper crossing           touching at an end        collinear overlap
   p1     p4                 p1                       p1 ----- p2
     \   /                     \                          p3 ----- p4
      \ /                       p3-----p4
      / \                       /
    p3   p2                   p2
Python Segment intersection with the collinear cases

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This is O(1): a fixed number of multiplications. Checking every pair among n segments is O(n^2); a sweep-line algorithm (Shamos-Hoey) can detect whether any pair crosses in O(n log n), but that is beyond this lesson.

Convex hull

The convex hull of a set of points is the smallest convex polygon that contains them all. Picture hammering a nail at every point and stretching a rubber band around them: when the band snaps tight, the nails it touches are the hull vertices.

TEXT
  .       *---------*          hull = the starred points
     .  /           \          the dots inside are ignored
  *   .               *
   \      .          /
     *---------------*

Brute force first

A pair of points (a, b) is a hull edge if all other points lie on the same side of the line a-b. Test every pair against every point: O(n^2) pairs times O(n) checks = O(n^3). It works, but 1,000 points mean a billion checks.

Andrew's monotone chain

Andrew's algorithm (1979) builds the hull in O(n log n):

  1. Sort the points by x (and by y to break ties). The leftmost point and the rightmost point are on the hull.
  2. Build the lower hull from left to right: for each point, while the last two points of the chain and the new point do not make a left (counter-clockwise) turn, pop the last point. Then push the new point.
  3. Build the upper hull the same way going right to left.
  4. Join both chains, dropping the duplicated end points.

The popping is the heart of it. A non-left turn means the middle point lies inside, or on the edge of, the shape and cannot be a hull vertex. Using cross <= 0 as the pop condition also removes collinear points on the edges, so the hull contains only true corners.

Python Convex hull with the monotone chain

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Trace on a tiny input. Take (0,0), (1,1), (2,0), (1,-1). Sorted: (0,0), (1,-1), (1,1), (2,0). Lower chain: push (0,0), push (1,-1); for (1,1), the turn (0,0)->(1,-1)->(1,1) is a left turn (cross is 2), so we keep and push it; for (2,0) the turn (1,-1)->(1,1)->(2,0) has cross -2, a right turn, so we pop (1,1), then check (0,0),(1,-1),(2,0), cross 2, a left turn, push (2,0). Lower chain: (0,0),(1,-1),(2,0). The upper chain mirrors it through (1,1). The hull is the diamond with four corners.

Complexity. Sorting costs O(n log n). Each point is pushed at most once and popped at most once in each pass, so the two scans cost O(n) in total. Space is O(n). The overall time is O(n log n), which is also a lower bound for the problem.

Polygon area: the shoelace formula

For a polygon with vertices (x0, y0), ..., (x(n-1), y(n-1)) listed in order around the boundary, the area is:

area = |sum of (xi * y(i+1) - x(i+1) * yi)| / 2

with the index wrapping around from the last vertex to the first. Each term is the cross product of two position vectors, which is twice the signed area of a triangle with the origin. Triangles on one side add area and triangles on the other side subtract, so what remains is the true area. The sign of the sum also reveals the direction: positive means the vertices run counter-clockwise.

Work with the doubled area (an integer) and halve only at the end, so the answer stays exact.

Python Shoelace formula and orientation of a polygon

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The shoelace formula is O(n) and works for any simple polygon, convex or not (a polygon whose edges do not cross each other).

Point in polygon

To test whether a point is inside a polygon, shoot a ray from the point to the right and count how many edges it crosses: an odd count means inside, even means outside. This works for any simple polygon, convex or not, in O(n).

The ray test needs care at vertices. The standard fix is to count an edge only when one endpoint is strictly above the ray and the other is on or below it (the test (a[1] > y) != (b[1] > y)), so a ray passing exactly through a vertex is counted once, not twice or zero times. Check for the boundary first with the cross product: a point is on an edge when the orientation is 0 and the point lies within the edge's bounding box.

Python Inside, outside or on the boundary

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The notch of the arrow at (2, 3) is correctly reported as outside even though it sits between the polygon's corners. For a convex polygon given counter-clockwise there is a simpler test: the point must be on the left of (or on) every edge, that is, every orientation is non-negative.

Quickhull

Andrew's monotone chain sorts the points and sweeps. Quickhull is the divide-and-conquer alternative, and it looks like quicksort. Take the leftmost point a and the rightmost point b (both are on the hull). The line a-b splits the rest into points on each side. For one side, find the point far farthest from the line: it is a hull vertex. The triangle a, far, b contains many points that cannot be on the hull, so throw them away. Recurse on the points outside edge a-far and outside edge far-b.

On average it takes O(n log n), like quicksort; with an unlucky split, such as points all lying on a circle, it degrades to O(n^2). The monotone chain has no such weakness, which is why it is the usual choice.

Python Quickhull checked against the monotone chain

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The all(...) line proves that both algorithms return the same set of vertices on 300 random point sets, and the 4 x 4 grid shows that collinear points on the boundary are left out.

Angular sweep: how many points fit in a view?

A different geometric pattern: stand at a point and look in some direction with a field of view of f degrees. What is the largest number of points you can see by choosing the best direction? Convert every point to its angle around you (atan2), sort the angles, and slide a window of width f around the circle. Duplicate the list with 360 added to every angle so the window can wrap past 360. A two-pointer scan then finds the best window in O(n log n), dominated by the sort. Points that coincide with the center are always visible and are counted separately, because their angle is undefined.

Python Angular sweep versus brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A wider field of view can only see more points, and a full 359-degree view sees all seven. The last line is a brute-force check that tries every point's angle as the start of the window; it agrees with the sweep.

Common mistakes

  • Using floats. 0.1 + 0.2 is not 0.3. If you must use floats, compare with a small tolerance (abs(x) < 1e-9), and expect rare bugs anyway.
  • Forgetting collinear cases. Most wrong segment-intersection code works on random tests and fails on touching or overlapping segments.
  • Mixing the sign convention. Positive cross means counter-clockwise only when the y axis points up. On a screen where y grows downward, the picture appears mirrored. The math stays correct.
  • Duplicate points in the hull. Remove duplicates before the scan, or the stack logic can produce repeated vertices.
  • Wrong cross product origin. cross(o, a, b) uses vectors from o. Passing the points in the wrong order flips the sign.

When to use these tools

The cross product is your first reach for any "left or right", "collinear", "inside", "crossing" or "area" question. Use the convex hull when you need the outer boundary of a point cloud, the diameter of a point set (a farthest pair is always on the hull), or a bounding shape for collision tests. If you need heavy geometry, such as many shapes with floating-point coordinates, a library like Shapely is usually wiser than a hand-written solution.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. cross(o, a, b) is negative. What does that mean for the turn o -> a -> b (y axis pointing up)?

    A negative cross product means b is clockwise from the direction o->a, a right turn. Positive is a left turn and zero means the three points lie on one line.
  2. 2. Why do geometry programs prefer integer coordinates when possible?

    Floating-point rounding can turn an exact zero into a tiny nonzero value. Integers avoid that, and Python integers never overflow.
  3. 3. What is the running time of Andrew's monotone chain for n points?

    Sorting is O(n log n). The two scans push and pop each point at most once, which is O(n), so sorting dominates.
  4. 4. In the monotone chain, why is a point popped when cross(second last, last, new) <= 0?

    A right turn or a straight continuation shows that the last point is not a real corner of the lower (or upper) hull and gets removed.
  5. 5. The shoelace sum for a polygon is -40. What can you conclude?

    The sum is the signed doubled area. Its magnitude halved is the area (20), and the negative sign means the vertices are listed clockwise. It says nothing about convexity.

Summary

  • The 2D cross product ux * vy - uy * vx gives the turn direction of three points: positive is left, negative is right, zero is collinear. It uses only integer arithmetic and is exact.
  • Two segments intersect when each straddles the other's line, plus special collinear cases handled with a bounding-box check.
  • The convex hull is the rubber band around the points; brute force is O(n^3), Andrew's monotone chain is O(n log n) with O(n) extra space.
  • The shoelace formula gives a polygon's area in O(n); keep the doubled area as an integer and halve it last.
  • Prefer integers, test the collinear cases, and keep the sign convention straight.

Next: Skip Lists