Computational Geometry › Lesson

Orientation & the Cross Product

Orientation & the Cross Product 28 minThe sign of a 2D cross product tells you whether three points turn left, turn right, or lie on one line — the single test every other lesson in this section is built from

You're building a piece ofMeridian — service areas & coverage

This piece — orientation(): Classifies whether three points bend left, right, or lie on a straight line — the one test everything else here is built from.

Scenario Meridian's route planner needs one cheap test, run millions of times: given three stops in order, did the van bend left, bend right, or just carry straight on?

Your task

Build orientation(a, b, c). a, b and c are (x, y) tuples. Return 1 if the path a -> b -> c turns left (counter-clockwise), -1 if it turns right (clockwise), and 0 if a, b and c lie on one straight line. Do this by computing the cross product of vector (b - a) and vector (c - a), then returning its sign. No trig, no sqrt, no division. Example: orientation((0, 0), (4, 0), (4, 3)) -> 1.

Additional resources

ArticleCross product↗ArticleCurve orientation↗

Orientation & the Cross Product

In short: given three points a, b, c in order, the path a -> b -> c either bends left, bends right, or runs dead straight. The cross product of vector (b - a) and vector (c - a) answers this with one number: its sign is the turn direction, and its size is twice the area of the triangle the three points span. Positive means a left (counter-clockwise) turn, negative means a right (clockwise) turn, and exactly zero means the three points are collinear — they lie on one straight line. Every lesson in this section reduces to asking this one question about three points.

A triangle a, b, c on a coordinate plane with vector b-a drawn from a and vector c-a drawn from a, the parallelogram they span shaded green with a plus sign because c sits to the left of the line through a and b, and a second faint triangle below the line shaded red with a minus sign to show the mirrored case

Which way does the van turn?

Meridian's route planner reads three consecutive stops at a time and asks whether the van bends left or right between them:

step through it

1def orientation(a, b, c):

2 cross = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

3 if cross > 0:

4 return 1

5 if cross < 0:

6 return -1

7 return 0

9depot, warehouse, mall = (0, 0), (4, 0), (4, 3)

10print(orientation(depot, warehouse, mall))

depot -> warehouse runs straight east; mall sits north of warehouse, so the van bends left there — orientation returns 1. Swap mall for a stop south of the line, (2, -3), and the sign flips to -1: the van bends right. Nothing about the distance between the points matters here, only which side of the line a -> b the point c lands on.

Spotting a dead-straight stretch of road

A straight stretch is the one case where orientation has to say "neither":

What does this print?

def orientation(a, b, c):
    cross = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
    if cross > 0:
        return 1
    if cross < 0:
        return -1
    return 0

print(orientation((-3, -3), (0, 0), (3, 3)))

This works perfectly because every coordinate here is a whole number, so the cross product's arithmetic is exact. Real map data rarely is: stop positions usually arrive as floating-point latitude/longitude, and floating point arithmetic does not promise an exact zero even when three points are mathematically dead straight.

broken — fix it

Three genuinely collinear points report themselves as NOT collinear. Fix the comparison so it tolerates floating-point rounding.

With floats, "collinear" has to mean "close enough to zero", decided by an epsilon you choose on purpose — never left as a silent default. Too loose an epsilon calls a real turn collinear; too tight and real floating-point noise reads as a turn. Every example and every test in this section uses whole-number coordinates for exactly this reason: the results are exact, and the epsilon problem never has to be papered over to get a clean answer.

Quick practice

What does this print?

a, b, c = (0, 0), (0, 5), (5, 5)
cross = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
print(cross)

What does this print?

def orientation(a, b, c):
    cross = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
    if cross > 0:
        return 1
    if cross < 0:
        return -1
    return 0

print(orientation((2, 2), (2, 2), (2, 2)))

🎯 Your turn

Build orientation(a, b, c). Return 1 for a left turn, -1 for a right turn, 0 if the three points are collinear — using only the sign of the cross product.

orientation((0, 0), (4, 0), (4, 3)) → 1
orientation((0, 0), (4, 0), (2, -3)) → -1
orientation((0, 0), (4, 0), (2, 0)) → 0

Hint: cross = (b[0]-a[0]) * (c[1]-a[1]) - (b[1]-a[1]) * (c[0]-a[0]). Return 1 if cross > 0, -1 if cross < 0, otherwise 0.

Press ▶ Run, try the Live App chips, then ✓ Check.

Practice — level up

0/5 solved

Solve each in its own editor — Run to try, Check to grade. Stuck? Reveal a Hint, or the full Solution + walkthrough.

Warm-upThe raw cross product

Write cross_product(a, b, c), returning the raw signed value (b[0]-a[0]) * (c[1]-a[1]) - (b[1]-a[1]) * (c[0]-a[0]) — twice the signed area of the triangle a, b, c. cross_product((0, 0), (4, 0), (4, 3)) -> 12.

cross-product

DrillDo three points line up?

Write collinear(a, b, c), returning True if a, b and c lie on one straight line (in any order), using the sign of the cross product. collinear((0, 0), (2, 0), (5, 0)) -> True.

orientationcollinear

BuildClassify every turn on a path

Write turn_sequence(points), returning a list with one orientation value (1, -1 or 0) for every consecutive triple of points along the path. A path of n points has n - 2 turns. turn_sequence([(0,0), (4,0), (4,3), (0,3)]) -> [1, 1].

orientation

BossDoes this path only ever turn left?

Write is_simple_left_turn_path(points), returning True only if EVERY consecutive triple along the path is a left turn (orientation 1). A straight stretch (0) or any right turn (-1) fails it. is_simple_left_turn_path([(0,0), (4,0), (4,3), (0,3)]) -> True.

orientation

CapstoneWhich way does the patrol loop run?

Write patrol_direction(points) for a CLOSED loop (the last point connects back to the first). Check the orientation at every vertex, wrapping around. Return "counter-clockwise" if every non-zero turn is a left turn, "clockwise" if every non-zero turn is a right turn, "straight" if every turn is zero, and "mixed" otherwise. patrol_direction([(0,0), (4,0), (4,3), (0,3)]) -> "counter-clockwise".

orientationpolygon-area