Cross Product Orientation Test (Turn Direction, Collinearity, Convexity)
points lists the corners of a polygon in the order you meet them when you walk along its edge: each point is joined to the next one, and the last point is joined back to the first. The polygon is guaranteed to be simple: every corner touches exactly two edges, and no two edges meet or cross anywhere else.
Return true if the polygon is convex and false if it is not. A convex polygon has no dent: walking around it, you always turn the same way (only left turns, or only right turns). Three corners in a row may lie on one straight line; such a straight corner is not a turn, so it never makes the polygon non-convex.
(0,0) up to (0,5), across to (5,5), down to (5,0) and back, every corner is a right turn, so there is no dent.Cross Product
three points ➔ sign of the cross product ➔ left turn, right turn or straight line| 1 | def cross(o: list[int], a: list[int], b: list[int]) -> int: |
| 2 | """Orientation test: > 0 when o -> a -> b turns left, < 0 when it turns right, 0 when the points are collinear.""" |
| 3 | # cross is twice the signed area of triangle o, a, b: its sign alone gives the turn direction. |
| 4 | return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) |
| 5 | |
| 6 | |
| 7 | def is_convex(points: list[list[int]]) -> bool: |
| 8 | """Convex Polygon: every turn along the boundary has the same cross-product sign. |
| 9 | Time: O(N) | Space: O(1) |
| 10 | """ |
| 11 | n = len(points) |
| 12 | prev = 0 # prev: the last non-zero turn seen so far; 0 means no turn has been seen yet |
| 13 | for i in range(n): |
| 14 | # 1. Compute the Turn at the Next Corner: |
| 15 | # cross() gives the sign of the turn o -> a -> b in one integer; % n wraps the index, so the |
| 16 | # two turns that close the polygon are checked in the same pass as every other corner. |
| 17 | turn = cross(points[i], points[(i + 1) % n], points[(i + 2) % n]) |
| 18 | |
| 19 | # 2. Classify the Turn (the trap): |
| 20 | # A turn of 0 is a straight corner: it is allowed and tells nothing about direction, so it |
| 21 | # is skipped before prev is touched. A later non-zero turn with the opposite sign means the |
| 22 | # boundary bent back on itself, a dent, so the polygon is not convex. |
| 23 | if turn == 0: |
| 24 | continue |
| 25 | if prev != 0 and (turn > 0) != (prev > 0): |
| 26 | return False |
| 27 | |
| 28 | # 3. Remember the Direction: |
| 29 | # Save this non-zero turn so the next corner's turn can be compared against it. |
| 30 | prev = turn |
| 31 | return True |
cross(o, a, b) is positive exactly when o -> a -> b turns left, negative when it turns right and 0 when the three points lie on one line; prev always holds the last non-zero turn.The cross product cross(o, a, b) = (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) answers "which way does the path o -> a -> b turn?" with one integer: positive for a left (counter-clockwise) turn, negative for a right turn, 0 when the three points lie on one line. A polygon is convex exactly when its boundary always turns the same way, so is_convex computes turn at every corner, wrapping around with % n so the two turns that close the loop are checked too, and returns False the first time a turn's sign differs from prev. This is correct because the value is twice the signed area of the triangle o, a, b: its sign flips exactly when b crosses from one side of the line through o and a to the other, and it uses only integer multiplication and subtraction, so there is no division by zero on a vertical edge and no rounding error. The trap is a turn of 0: three points in a row on one line make a straight corner, which is allowed and says nothing about the direction, so continue past it. Treating it as a change of direction rejects convex polygons that have extra points along an edge, and storing it in prev overwrites the record of which way the boundary was turning, so a dent right after a straight corner slips through.
See it run
Convex Polygon: the turn at every corner of 8 points
i -turn -prev 0
Each column is one point. The middle row is the turn at that corner, and the bottom row is prev after that corner.
reada point used in the cross productturnthe cross product for this cornerprevthe direction saved for the next cornerdenta turn with the opposite signlostprev if the straight corner were stored
The polygon has 8 points. prev = 0, which means no turn has been seen yet. Each step checks one corner, and % n wraps the last two corners around to the first points.
Gotcha 1 of 4
- The trap
Gotcha 1: Leaving out
if turn == 0: continueMistakeif prev != 0 and (turn > 0) != (prev > 0):Fixif turn == 0: continue if prev != 0 and (turn > 0) != (prev > 0):What happens: A turn of 0 is a straight corner. It is allowed, and it says nothing about the direction. Without
continue, the 0 reaches the sign test. After a right turn, the test passes, andprev = turnsetsprevto 0. The last known direction is lost. A dent right after the straight corner is then not caught. After a left turn, the same 0 fails the test, so a convex polygon is rejected.Example: points = [[6,6],[8,12],[12,12],[12,0],[0,0],[0,12],[4,12],[5,9]]Mistake: returns TrueFix: returns False
- You must count how many points share each line, as in Max Points on a Line (LC 149): a cross product only tests one triple at a time, while hashing each pair's reduced slope groups every line through a point in one pass. See Canonical Key
Deep Dive
What the sign of the cross product says
cross(o, a, b) takes two edge vectors that start at o: the vector from o to a, and the vector from o to b. It returns (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]).
The value is twice the signed area of the triangle o, a, b. The area is positive when o -> a -> b goes counter-clockwise, which is a left turn. It is negative for a right turn. It is 0 when the three points lie on one line, because the triangle has no area.
Example: o = [0, 0], a = [4, 0], b = [4, 3]. The value is 4 * 3 - 0 * 4 = 12, which is a left turn, and the triangle has area 6. Swap a and b, and the value is -12, a right turn. The sign flips because the order of the points is reversed.
From one turn to a convex polygon
Walk around a polygon and look at the turn at every corner. A convex polygon always bends in the same direction. A dent, which is a corner that bends the other way, makes the polygon not convex.
The picture checks the polygon [6,6], [8,12], [12,12], [12,0], [0,0], [0,12], [4,12], [5,9]. The turns at corners 0 to 5 are -24, -48, -144, -144, -48, -12. All are negative, so prev = -12.
Corner 6 reads the points [4,12], [5,9], [6,6]. They lie on one line, and the turn is 0. The code continues, and prev stays -12. Corner 7 reads [5,9], [6,6], [8,12], and the turn is 12. It is positive and prev is negative, so the function returns False.
The index uses % n. For i = 6 and i = 7, the points (i + 1) % n and (i + 2) % n wrap to the first points. So the two corners that close the loop are checked in the same loop as all others. range(n - 2) would skip them.
Why a turn of 0 must be skipped before prev changes
A turn of 0 is a straight corner. A convex polygon may have extra points along an edge, so a straight corner is allowed. It also says nothing about the direction.
If the code stored the 0 in prev, the record of the direction would be lost. In the picture, corner 6 would set prev = 0. Then corner 7 has turn 12 and prev != 0 is false, so the test does not run. The function returns True for a polygon that is not convex.
If the code compared the 0 with the sign test, (0 > 0) != (prev > 0) is False != True after a left turn. A convex polygon with a point on an edge would be rejected. So the if turn == 0: continue line runs first, and only non-zero turns reach prev.
The test (turn > 0) != (prev > 0) compares only the signs. Multiplying prev * turn gives the same answer in Python. In Java or C++ with coordinates up to 10^4, one cross product can reach 8 * 10^8, and the product of two can reach 6.4 * 10^17, which overflows a 32-bit integer.
What the check does not cover, and the other uses
is_convex assumes the polygon does not cross itself. Convex Polygon (LC 469) guarantees this. The five points of a pentagram, visited in the order that draws the star, all have the same sign of turn. The function returns True for them, but the star is not convex. A polygon that may cross itself needs an extra check.
The cost is O(N) time, with one cross product per corner. The space is O(1).
The same function solves smaller questions. Valid Boomerang (LC 1037) asks whether cross of the three points is not 0. Check If It Is a Straight Line (LC 1232) asks whether cross(points[0], points[1], p) is 0 for every other point p. Largest Triangle Area (LC 812) takes the largest abs(cross(o, a, b)) / 2 over all triples. For [[0,0],[0,1],[1,0],[0,2],[2,0]], this is 2.0.
The sign of cross(o, a, p) also tells which side of the line through o and a the point p is on. A slope test needs a division, and it raises ZeroDivisionError on a vertical edge. cross uses only integer multiplication and subtraction, so it has no division and no rounding error.
60-Second Pitch
"I use the cross product of o -> a and o -> b. Its sign gives the turn: positive is left, negative is right, and 0 means the three points lie on one line. It is twice the signed area of the triangle, and it uses only integer arithmetic. A polygon is convex when every corner turns the same way. I compute the turn at every corner, and % n wraps the two closing corners around. A turn of 0 is a straight corner, so I skip it without changing prev. When a non-zero turn has the opposite sign to prev, I return False. This takes O(N) time and O(1) space. The input must be a polygon that does not cross itself."
Common Questions
- Why is the cross product better than comparing slopes?
A slope needs a division. A vertical edge has
dx = 0, so the division raisesZeroDivisionError. With large coordinates, two different slopes can also round to the same float. The cross product uses only integer multiplication and subtraction, so it is exact.- What does a cross product of 0 mean, and why is it skipped in
is_convex? It means the three points lie on one line. In a polygon, this is a straight corner. It is allowed, and it gives no direction. The code continues before it touches
prev, so the last known direction is kept.- What are the time and space complexity of
is_convex? O(N)time, because there is one cross product per corner, andO(1)space. The function stores onlyprev.- Does the same-sign test prove convexity for every polygon?
No. It works when the polygon does not cross itself, which Convex Polygon (LC 469) guarantees. A pentagram has the same sign at all five corners, and it is not convex. For input that may cross itself, check that no two edges intersect as well.
SWE Reasoning
Spot it
- The input is points with integer coordinates, and the question is about direction: left or right turn, same line, which side, convex, or the size of a triangle.
- A slope test would divide by
dx, and a vertical edge hasdx = 0. - The question is about every corner of a polygon, and the answer must be the same at all of them.
- Three points are given, and the task asks whether they lie on one line, as in Valid Boomerang (LC 1037).
- The coordinates are integers, so an exact answer is possible without floating-point numbers.
The invariant, step by step
cross(o, a, b)is positive for a left turn, negative for a right turn, and 0 for three points on one line.prevstarts at 0. This means no turn has been seen yet.- For each
i,turn = cross(points[i], points[(i + 1) % n], points[(i + 2) % n])is the turn at the next corner. The% nmakes the last two corners wrap around. - If
turn == 0, the corner is straight. The code continues, andprevis not changed. - If
prev != 0and the sign ofturndiffers from the sign ofprev, the boundary bends back. The function returnsFalse. - Otherwise
prev = turn. After allncorners, every non-zero turn had the same sign, and the function returnsTrue.
Traps
- No
if turn == 0: continue. A 0 reachesprev, and the saved direction is lost. For the 8-point polygon in the picture, the function returnsTrueinstead ofFalse. range(n - 2). The two closing corners are not checked. For[[0,0],[0,10],[10,10],[10,0],[5,5]], the dent at[5,5]is missed and the function returnsTrue.- A slope test.
(a[1] - o[1]) / (a[0] - o[0])divides by 0 on a vertical edge and raisesZeroDivisionError. Usecross(o, a, b) == 0. - Multiplying two cross products. The product can overflow a 32-bit integer in Java or C++. Compare the two signs instead.
- Self-crossing input. Equal signs at every corner do not prove convexity for a polygon that crosses itself. A pentagram passes the check.
Practice
Cross Product Orientation Test (Turn Direction, Collinearity, Convexity)
points lists the corners of a polygon in the order you meet them when you walk along its edge: each point is joined to the next one, and the last point is joined back to the first. The polygon is guaranteed to be simple: every corner touches exactly two edges, and no two edges meet or cross anywhere else.
Return true if the polygon is convex and false if it is not. A convex polygon has no dent: walking around it, you always turn the same way (only left turns, or only right turns). Three corners in a row may lie on one straight line; such a straight corner is not a turn, so it never makes the polygon non-convex.
(0,0) up to (0,5), across to (5,5), down to (5,0) and back, every corner is a right turn, so there is no dent.Cross Product
three points ➔ sign of the cross product ➔ left turn, right turn or straight line| 1 | def cross(o: list[int], a: list[int], b: list[int]) -> int: |
| 2 | """Orientation test: > 0 when o -> a -> b turns left, < 0 when it turns right, 0 when the points are collinear.""" |
| 3 | # cross is twice the signed area of triangle o, a, b: its sign alone gives the turn direction. |
| 4 | return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) |
| 5 | |
| 6 | |
| 7 | def is_convex(points: list[list[int]]) -> bool: |
| 8 | """Convex Polygon: every turn along the boundary has the same cross-product sign. |
| 9 | Time: O(N) | Space: O(1) |
| 10 | """ |
| 11 | n = len(points) |
| 12 | prev = 0 # prev: the last non-zero turn seen so far; 0 means no turn has been seen yet |
| 13 | for i in range(n): |
| 14 | # 1. Compute the Turn at the Next Corner: |
| 15 | # cross() gives the sign of the turn o -> a -> b in one integer; % n wraps the index, so the |
| 16 | # two turns that close the polygon are checked in the same pass as every other corner. |
| 17 | turn = cross(points[i], points[(i + 1) % n], points[(i + 2) % n]) |
| 18 | |
| 19 | # 2. Classify the Turn (the trap): |
| 20 | # A turn of 0 is a straight corner: it is allowed and tells nothing about direction, so it |
| 21 | # is skipped before prev is touched. A later non-zero turn with the opposite sign means the |
| 22 | # boundary bent back on itself, a dent, so the polygon is not convex. |
| 23 | if turn == 0: |
| 24 | continue |
| 25 | if prev != 0 and (turn > 0) != (prev > 0): |
| 26 | return False |
| 27 | |
| 28 | # 3. Remember the Direction: |
| 29 | # Save this non-zero turn so the next corner's turn can be compared against it. |
| 30 | prev = turn |
| 31 | return True |
cross(o, a, b) is positive exactly when o -> a -> b turns left, negative when it turns right and 0 when the three points lie on one line; prev always holds the last non-zero turn.The cross product cross(o, a, b) = (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) answers "which way does the path o -> a -> b turn?" with one integer: positive for a left (counter-clockwise) turn, negative for a right turn, 0 when the three points lie on one line. A polygon is convex exactly when its boundary always turns the same way, so is_convex computes turn at every corner, wrapping around with % n so the two turns that close the loop are checked too, and returns False the first time a turn's sign differs from prev. This is correct because the value is twice the signed area of the triangle o, a, b: its sign flips exactly when b crosses from one side of the line through o and a to the other, and it uses only integer multiplication and subtraction, so there is no division by zero on a vertical edge and no rounding error. The trap is a turn of 0: three points in a row on one line make a straight corner, which is allowed and says nothing about the direction, so continue past it. Treating it as a change of direction rejects convex polygons that have extra points along an edge, and storing it in prev overwrites the record of which way the boundary was turning, so a dent right after a straight corner slips through.
See it run
Convex Polygon: the turn at every corner of 8 points
i -turn -prev 0
Each column is one point. The middle row is the turn at that corner, and the bottom row is prev after that corner.
reada point used in the cross productturnthe cross product for this cornerprevthe direction saved for the next cornerdenta turn with the opposite signlostprev if the straight corner were stored
The polygon has 8 points. prev = 0, which means no turn has been seen yet. Each step checks one corner, and % n wraps the last two corners around to the first points.
Gotcha 1 of 4
- The trap
Gotcha 1: Leaving out
if turn == 0: continueMistakeif prev != 0 and (turn > 0) != (prev > 0):Fixif turn == 0: continue if prev != 0 and (turn > 0) != (prev > 0):What happens: A turn of 0 is a straight corner. It is allowed, and it says nothing about the direction. Without
continue, the 0 reaches the sign test. After a right turn, the test passes, andprev = turnsetsprevto 0. The last known direction is lost. A dent right after the straight corner is then not caught. After a left turn, the same 0 fails the test, so a convex polygon is rejected.Example: points = [[6,6],[8,12],[12,12],[12,0],[0,0],[0,12],[4,12],[5,9]]Mistake: returns TrueFix: returns False
- You must count how many points share each line, as in Max Points on a Line (LC 149): a cross product only tests one triple at a time, while hashing each pair's reduced slope groups every line through a point in one pass. See Canonical Key
Deep Dive
What the sign of the cross product says
cross(o, a, b) takes two edge vectors that start at o: the vector from o to a, and the vector from o to b. It returns (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]).
The value is twice the signed area of the triangle o, a, b. The area is positive when o -> a -> b goes counter-clockwise, which is a left turn. It is negative for a right turn. It is 0 when the three points lie on one line, because the triangle has no area.
Example: o = [0, 0], a = [4, 0], b = [4, 3]. The value is 4 * 3 - 0 * 4 = 12, which is a left turn, and the triangle has area 6. Swap a and b, and the value is -12, a right turn. The sign flips because the order of the points is reversed.
From one turn to a convex polygon
Walk around a polygon and look at the turn at every corner. A convex polygon always bends in the same direction. A dent, which is a corner that bends the other way, makes the polygon not convex.
The picture checks the polygon [6,6], [8,12], [12,12], [12,0], [0,0], [0,12], [4,12], [5,9]. The turns at corners 0 to 5 are -24, -48, -144, -144, -48, -12. All are negative, so prev = -12.
Corner 6 reads the points [4,12], [5,9], [6,6]. They lie on one line, and the turn is 0. The code continues, and prev stays -12. Corner 7 reads [5,9], [6,6], [8,12], and the turn is 12. It is positive and prev is negative, so the function returns False.
The index uses % n. For i = 6 and i = 7, the points (i + 1) % n and (i + 2) % n wrap to the first points. So the two corners that close the loop are checked in the same loop as all others. range(n - 2) would skip them.
Why a turn of 0 must be skipped before prev changes
A turn of 0 is a straight corner. A convex polygon may have extra points along an edge, so a straight corner is allowed. It also says nothing about the direction.
If the code stored the 0 in prev, the record of the direction would be lost. In the picture, corner 6 would set prev = 0. Then corner 7 has turn 12 and prev != 0 is false, so the test does not run. The function returns True for a polygon that is not convex.
If the code compared the 0 with the sign test, (0 > 0) != (prev > 0) is False != True after a left turn. A convex polygon with a point on an edge would be rejected. So the if turn == 0: continue line runs first, and only non-zero turns reach prev.
The test (turn > 0) != (prev > 0) compares only the signs. Multiplying prev * turn gives the same answer in Python. In Java or C++ with coordinates up to 10^4, one cross product can reach 8 * 10^8, and the product of two can reach 6.4 * 10^17, which overflows a 32-bit integer.
What the check does not cover, and the other uses
is_convex assumes the polygon does not cross itself. Convex Polygon (LC 469) guarantees this. The five points of a pentagram, visited in the order that draws the star, all have the same sign of turn. The function returns True for them, but the star is not convex. A polygon that may cross itself needs an extra check.
The cost is O(N) time, with one cross product per corner. The space is O(1).
The same function solves smaller questions. Valid Boomerang (LC 1037) asks whether cross of the three points is not 0. Check If It Is a Straight Line (LC 1232) asks whether cross(points[0], points[1], p) is 0 for every other point p. Largest Triangle Area (LC 812) takes the largest abs(cross(o, a, b)) / 2 over all triples. For [[0,0],[0,1],[1,0],[0,2],[2,0]], this is 2.0.
The sign of cross(o, a, p) also tells which side of the line through o and a the point p is on. A slope test needs a division, and it raises ZeroDivisionError on a vertical edge. cross uses only integer multiplication and subtraction, so it has no division and no rounding error.
60-Second Pitch
"I use the cross product of o -> a and o -> b. Its sign gives the turn: positive is left, negative is right, and 0 means the three points lie on one line. It is twice the signed area of the triangle, and it uses only integer arithmetic. A polygon is convex when every corner turns the same way. I compute the turn at every corner, and % n wraps the two closing corners around. A turn of 0 is a straight corner, so I skip it without changing prev. When a non-zero turn has the opposite sign to prev, I return False. This takes O(N) time and O(1) space. The input must be a polygon that does not cross itself."
Common Questions
- Why is the cross product better than comparing slopes?
A slope needs a division. A vertical edge has
dx = 0, so the division raisesZeroDivisionError. With large coordinates, two different slopes can also round to the same float. The cross product uses only integer multiplication and subtraction, so it is exact.- What does a cross product of 0 mean, and why is it skipped in
is_convex? It means the three points lie on one line. In a polygon, this is a straight corner. It is allowed, and it gives no direction. The code continues before it touches
prev, so the last known direction is kept.- What are the time and space complexity of
is_convex? O(N)time, because there is one cross product per corner, andO(1)space. The function stores onlyprev.- Does the same-sign test prove convexity for every polygon?
No. It works when the polygon does not cross itself, which Convex Polygon (LC 469) guarantees. A pentagram has the same sign at all five corners, and it is not convex. For input that may cross itself, check that no two edges intersect as well.
SWE Reasoning
Spot it
- The input is points with integer coordinates, and the question is about direction: left or right turn, same line, which side, convex, or the size of a triangle.
- A slope test would divide by
dx, and a vertical edge hasdx = 0. - The question is about every corner of a polygon, and the answer must be the same at all of them.
- Three points are given, and the task asks whether they lie on one line, as in Valid Boomerang (LC 1037).
- The coordinates are integers, so an exact answer is possible without floating-point numbers.
The invariant, step by step
cross(o, a, b)is positive for a left turn, negative for a right turn, and 0 for three points on one line.prevstarts at 0. This means no turn has been seen yet.- For each
i,turn = cross(points[i], points[(i + 1) % n], points[(i + 2) % n])is the turn at the next corner. The% nmakes the last two corners wrap around. - If
turn == 0, the corner is straight. The code continues, andprevis not changed. - If
prev != 0and the sign ofturndiffers from the sign ofprev, the boundary bends back. The function returnsFalse. - Otherwise
prev = turn. After allncorners, every non-zero turn had the same sign, and the function returnsTrue.
Traps
- No
if turn == 0: continue. A 0 reachesprev, and the saved direction is lost. For the 8-point polygon in the picture, the function returnsTrueinstead ofFalse. range(n - 2). The two closing corners are not checked. For[[0,0],[0,10],[10,10],[10,0],[5,5]], the dent at[5,5]is missed and the function returnsTrue.- A slope test.
(a[1] - o[1]) / (a[0] - o[0])divides by 0 on a vertical edge and raisesZeroDivisionError. Usecross(o, a, b) == 0. - Multiplying two cross products. The product can overflow a 32-bit integer in Java or C++. Compare the two signs instead.
- Self-crossing input. Equal signs at every corner do not prove convexity for a polygon that crosses itself. A pentagram passes the check.