📘 CodingMarble Learn

Computational Geometry: Cross Product, Polygon Area and Convex Hull

A computer can solve shape problems using only coordinates and one small trick: the cross product. For two arrows u and v, cross = ux·vy − uy·vx. Its size is the area of the parallelogram they make and its sign tells left or right turn. Adding triangle areas gives the area of any polygon, and keeping only left turns gives the convex hull.

🎬 Step-by-step story

  1. Here are three points A, B and C on a grid. Each point is a pair of numbers (x, y). The arrows AB and AC are also pairs: end minus start.
  2. Use the two arrows as two sides of a parallelogram. Its area is the cross product: ABx × ACy − ABy × ACx. The triangle ABC is exactly half of it.
  3. Walk from A to B, then on to C. Now C moves below the line AB. The cross product turns negative. Positive means a left turn, negative means a right turn, zero means a straight line.
  4. A polygon is a set of triangles. Cut it from one corner. Find each triangle's area with the cross product, then add them up to get the polygon's area.
  5. Hammer nails into a board and stretch a rubber band round them. The band touches only the outer nails. This outer shape is the convex hull. Every corner of the band is a left turn.
  6. Free play. Move point C with the two sliders. Watch the cross product, the area and the turn word change. Try to make it exactly zero.

Tip: drag the 3D scene to turn it. Use two fingers to zoom.

🤔 Common doubts, cleared

What are those arrows made of?

Each arrow is two numbers: end point minus start point. AB = (7, 1) means 7 to the right and 1 up.

Why is the cross product an area, and why is the triangle half of it?

Two arrows from the same corner make a parallelogram. Its area works out to a·d − b·c. A diagonal splits it into two equal triangles, so the amber triangle is half. The blue shape and the labels show both numbers.

How does a sign tell left from right?

When the second arrow is anticlockwise from the first, the signed area is positive. Move C below AB and it becomes clockwise, so the number turns negative.

Does the polygon trick work for any polygon?

Yes, for any polygon whose sides do not cross. Convex ones fan neatly from one corner. For ones with a dent, the signed pieces cancel the overlaps and the total is still right.

Why are some nails not on the hull?

A nail inside the band does not touch it. The blue nails stand inside the outer shape, so they are not part of the hull.

What happens when I make the cross product exactly 0?

All three points lie on one line, the triangle is flat and its area is 0. Move the sliders until the marker turns grey.

Points and arrows (vectors)

On a grid every point has two numbers, (x, y). An arrow from point P to point Q is also two numbers: (Qx − Px, Qy − Py). It tells you how far to go right and how far to go up. Arrows are also called vectors.

Example: A = (−4, −2) and B = (3, −1). The arrow AB = (3 − (−4), −1 − (−2)) = (7, 1).

The cross product of two arrows

For two arrows u = (a, b) and v = (c, d) the cross product is one number:

u × v = a·d − b·c

Draw u and v from the same point and complete a parallelogram. Its area is |u × v|. So the cross product is a signed area. The triangle made by the same two arrows has half of that area.

Turn direction: left, right or straight

Take three points A, B, C. Compute cross = (B − A) × (C − A). This also equals (B − A) × (C − B), so it is the turn you make at B when you walk A → B → C.

No angles, no square roots, no division. Only whole-number maths, so a computer makes no rounding error.

Area of a polygon

Pick one corner V0. Join it to the other corners. A polygon with n corners splits into n − 2 triangles (V0, Vk, Vk+1). Add the signed areas:

Area = ½ × (sum of cross(V0, Vk, Vk+1))

If the corners go anticlockwise, every term is positive. If they go clockwise, the answer is negative, so take the absolute value. The shoelace formula gives the same number: ½ |Σ (xi·yi+1 − xi+1·yi)|, going once round the corners. It works for any polygon whose sides do not cross, even one with a dent.

Convex hull

A shape is convex if a line between any two points inside it stays inside it. The convex hull of a set of points is the smallest convex shape that holds all of them. Picture nails in a board with a stretched rubber band round them.

Monotone chain method: 1) Sort the points by x (then y). 2) Build the lower chain from left to right: add each point, and while the last three points do not make a left turn, remove the middle one. 3) Do the same from right to left for the upper chain. 4) Join the two chains. The time needed is about n log n, because of the sorting.

Try it: nails and string

Draw 10 dots on paper, or push 10 pins into a cork board. Predict which dots will be on the hull. Then wrap a string or rubber band round them and check. For one corner of the band, pick the three dots A, B, C and compute the cross product: it should be positive when you walk anticlockwise.

Key formulas and definitions

Worked examples

1. Find u × v for u = (2, 1) and v = (1, 3). What does the sign tell you?

u × v = 2×3 − 1×1 = 6 − 1 = 5. It is positive, so v is turned anticlockwise (to the left) from u. The parallelogram area is 5.

2. Walk A(0, 0) → B(4, 1) → C(6, −2). Left or right turn at B?

AB = (4, 1), BC = (2, −3). cross = 4×(−3) − 1×2 = −12 − 2 = −14. Negative, so it is a right turn.

3. Are A(1, 1), B(3, 2), C(7, 4) on one straight line?

AB = (2, 1), AC = (6, 3). cross = 2×3 − 1×6 = 0. Zero, so the three points are collinear.

4. Find the area of the triangle with A(1, 1), B(6, 2), C(3, 5).

AB = (5, 1), AC = (2, 4). cross = 5×4 − 1×2 = 18. Area = 18 / 2 = 9 square units.

5. Find the area of the polygon (0,0), (5,0), (5,3), (2,4), (0,3) using triangles from (0,0).

T1 = (0,0),(5,0),(5,3): cross (5,0)×(5,3) = 15, area 7.5. T2 = (0,0),(5,3),(2,4): cross (5,3)×(2,4) = 20 − 6 = 14, area 7. T3 = (0,0),(2,4),(0,3): cross (2,4)×(0,3) = 6, area 3. Total = 7.5 + 7 + 3 = 17.5 square units.

6. Which points are on the convex hull of (0,0), (4,0), (2,1), (4,4), (0,4), (1,2), (3,3)?

The four corners (0,0), (4,0), (4,4), (0,4) form a square. The other three points, (2,1), (1,2) and (3,3), all lie inside it. So the hull is those 4 corners, in order (0,0) → (4,0) → (4,4) → (0,4). Each turn on the way round is a left turn.

7. A, B, C are (0,0), (6,0), (3,−2). Compute the area, and say if the order A, B, C is clockwise.

AB = (6, 0), AC = (3, −2). cross = 6×(−2) − 0×3 = −12. Area = 12 / 2 = 6. A negative cross means A → B → C is clockwise.

Common mistakes

Practice quiz

1. A positive cross product of (B − A) and (C − A) means:
2. u = (3, 2), v = (1, 4). What is u × v?
3. The area of a triangle is what part of the parallelogram made by the same two arrows?
4. The convex hull of a set of points is like:
5. A polygon with 6 corners splits into how many triangles from one corner?

Practice: answer these yourself

Type or choose your answer, then press Check. Use a hint if you are stuck; the full solution appears after you answer.

Frequently asked questions

What is computational geometry in simple words?

It is the study of how a computer can answer questions about points, lines and shapes using only numbers and fast steps. For example: which side of a line is a point on, how big is this plot, which points make the outer boundary?

Why do we use the cross product instead of angles?

Angles need sine, cosine and square roots, which give small rounding errors. The cross product only uses multiplication and subtraction, so with whole numbers it is exact and fast.

Is the convex hull the same as the polygon area?

No. The hull is the outer boundary of a set of points. The polygon area is a number that tells how much flat space a polygon covers. You can find the area of the hull after you find the hull.

Learn first

Related lessons

All Computer Science lessons