Convex Polygon (LeetCode 469)
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.
Worked Examples
points = [[0,0],[0,5],[5,5],[5,0]]true(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.points = [[0,0],[0,10],[10,10],[10,0],[5,5]]false(0,10), (10,10) and (10,0) are right turns, but at (5,5) the edge turns left: that corner points into the shape, so it has a dent. This turn is one of the two that close the loop, found only by wrapping around from the last point to the first.⚖️Formal Constraints & Bounds
3 <= points.length <= 104points[i].length == 2-104 <= xi, yi <= 104All the given points are unique.
Core Insight
One integer, cross(o, a, b), says whether the edge turns left or right at a corner. A polygon is convex exactly when every non-zero turn has the same sign, and a turn of 0 (a straight corner) changes nothing.
Real-World Scenario & Production Applications
A map or CAD tool checking that a drawn outline (a building footprint, a delivery zone, a collision shape in a game) has no dent before handing it to an algorithm that only works on convex shapes, such as a fast point-in-polygon test or a separating-axis collision check.
Step-by-Step Execution Trace Table
Example 2, points = [[0,0],[0,10],[10,10],[10,0],[5,5]] (n = 5):
| Step | i | Corner points[(i + 1) % n] | turn | prev before | Result |
|---|---|---|---|---|---|
| 1 | 0 | (0,10) | cross((0,0), (0,10), (10,10)) = -100 | 0 | first turn: prev = -100 (right) |
| 2 | 1 | (10,10) | cross((0,10), (10,10), (10,0)) = -100 | -100 | same sign: prev = -100 |
| 3 | 2 | (10,0) | cross((10,10), (10,0), (5,5)) = -50 | -100 | same sign: prev = -50 |
| 4 | 3 | (5,5) | cross((10,0), (5,5), (0,0)) = 50 | -50 | opposite sign: return False |
The dent is found at i = 3, whose third point points[(3 + 2) % 5] is points[0]: without the wrap-around the loop would stop at i = 2 and answer true.
The Math, Step by Step
1. The number that measures a turn
Walk from point to point , and then on to point . At you turn left, turn right, or go straight on. The code measures this with the cross product of the two vectors that start at , and :
The result is a whole number, because every coordinate is a whole number.
2. What the sign says
Only the sign of the cross product matters here:
cross(o, a, b) | The path | At corner |
|---|---|---|
| greater than 0 | turns counterclockwise | a left turn |
| less than 0 | turns clockwise | a right turn |
| equal to 0 | stays on one line | no turn |
The value is twice the signed area of the triangle . The area is positive when the corners go around counterclockwise, and negative when they go clockwise. It is 0 when the three points lie on one line and the triangle is flat.
A quick check: , and walk right and then up, which is a left turn. The cross product is .
3. Why one sign everywhere means convex
A simple polygon is convex exactly when a walk around its edge always turns the same way. If it turns left at some corners and right at others, a corner with the other direction points into the shape, which makes a dent.
So the code computes the turn at every corner and compares their signs. For corner number , the three points are points[i], points[(i + 1) % n] and points[(i + 2) % n]. The % n joins the last points back to the first ones. So the loop checks all corners, including the two where the walk closes the loop.
4. Straight corners, and the first real turn
A turn of 0 is a straight corner. It does not change the shape, so it cannot make the polygon non-convex. It also says nothing about the direction. So the code skips it with continue, and prev keeps the last turn that was not 0.
prev starts at 0, meaning "no direction seen yet". The first non-zero turn sets the direction. From then on, a turn with the other sign returns False. The test (turn > 0) != (prev > 0) compares only the signs, never the sizes.
5. Example 2 by hand
points = [[0,0],[0,10],[10,10],[10,0],[5,5]], so .
The picture shows the five corners as dots, labelled by index. It does not draw the edges. Join the dots in index order: from 0 up to 1, across to 2, down to 3, then to point 4 in the middle at , and back to 0. Point 4 lies inside the square formed by the first four points, so the polygon has a dent at point 4.
i | (the corner) | turn | Result | ||||
|---|---|---|---|---|---|---|---|
| 0 | first turn: right | ||||||
| 1 | right, same sign | ||||||
| 2 | right, same sign | ||||||
| 3 | left: return False |
At i = 3 the third point is points[(3 + 2) % 5] = points[0], so this turn is found only because % n wraps around to the first point. Its sign differs from the three right turns before it. The code returns false, the expected output.
6. Example 1 by hand
points = [[0,0],[0,5],[5,5],[5,0]], a square walked clockwise. All four turns are . For example, at i = 0 the vectors are and , so the turn is . No sign ever changes, so the loop ends and the code returns true, the expected output.
7. From the math to the code
| Math | In the code |
|---|---|
| with , | return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) |
| the turn at corner | turn = cross(points[i], points[(i + 1) % n], points[(i + 2) % n]) |
| a straight corner says nothing | if turn == 0: followed by continue |
| no direction seen yet | prev = 0 |
| a turn of the other sign is a dent | if prev != 0 and (turn > 0) != (prev > 0): followed by return False |
| remember the direction | prev = turn |
The loop computes one cross product per corner, so it takes time and space.
| 1 | The sign of `cross(o, a, b)` tells which way `o -> a -> b` turns: positive left, negative right, 0 straight. A convex polygon turns the same way at every corner. |
| 2 | Keep `prev`, the last non-zero turn; the polygon is convex exactly when no non-zero `turn` has the opposite sign. |
| 3 | For `i` in `range(n)`: `turn = cross(points[i], points[(i + 1) % n], points[(i + 2) % n])`; skip a 0; return `False` if `prev != 0 and (turn > 0) != (prev > 0)`; else `prev = turn`. Return `True` after the loop. |
| 4 | The trap: `if turn == 0: continue` before any comparison, and never store a 0 in `prev`: a straight corner is allowed, and forgetting the direction there lets a dent right after it slip through. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Convexity sounds like a question about angles, but it only needs directions: a polygon is convex exactly when walking along its edge you always turn the same way. The Cross Product measures a turn with one integer and no angle: cross(o, a, b) is positive when the path o -> a -> b turns left, negative when it turns right, and 0 when the three points lie on one line. So is_convex walks the corners once, computes turn at each one, and keeps prev, the last non-zero turn: the first turn whose sign differs from prev is a dent.
🚗 The Analogy: Driving Around a Block
Picture driving once around a city block that has no dents: at every corner you turn the same way, say always right. If you ever have to turn left, the block must bend inward there. Driving straight through a junction is no turn at all, so it tells you nothing: you keep remembering that your turns so far were right turns. The cross product is the steering wheel read as a number: positive for a left turn, negative for a right turn, zero when you go straight on.
🔑 Why It Works
cross(o, a, b) is (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]), twice the signed area of the triangle o, a, b. Its sign changes exactly when b moves from one side of the line through o and a to the other, so it measures the turn at a with integer multiplication and subtraction only: no division by zero on a vertical edge, no rounding. The % n indices make the last two turns, at points[n - 1] and points[0], part of the same loop. A turn of 0 is skipped before prev is touched, so a straight corner can neither be mistaken for a dent nor erase the direction the edge was turning.
Straight corners: write
if turn == 0: continuebefore comparing. A straight corner is allowed, and storing its 0 inprevoverwrites the last known direction: in[[6,6],[4,12],[0,12],[0,0],[12,0],[12,12],[8,12],[7,9]]the dent at[6,6], checked right after the straight corner[7,9], would pass.No wrap-around: use
points[(i + 1) % n]andpoints[(i + 2) % n]. The last two turns sit atpoints[n - 1]andpoints[0], and in[[0,0],[0,10],[10,10],[10,0],[5,5]]the dent at[5,5]is one of them.Multiplying signs: compare with
(turn > 0) != (prev > 0), notprev * turn < 0. Each cross product reaches about 8 * 10^8, so the product of two overflows a 32-bit integer in Java or C++.Slopes or angles:
dy / dxdivides by zero on a vertical edge andatan2rounds; the cross product stays in exact integers.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Each point is joined to the next one, and the last point is joined back to the first", "you always turn the same way (only left turns, or only right turns)", "a straight corner is not a turn", and whole-number corners [x, y]: a question about which way the edge turns between points in the plane. That is the signal for the Cross Product: one integer per corner says left, right or straight, with no angle and no division.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
The decision at each corner: skip a turn of 0; a non-zero turn with (turn > 0) != (prev > 0) while prev != 0 is a dent, so return False; otherwise prev = turn.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap:
if turn == 0: continueruns beforeprevis compared or changed (gotcha 1 shows the dent a stored 0 hides).Leading straight corners are harmless:
prevstays 0 until the first real turn, and theprev != 0test lets every corner pass until then.The statement promises a simple polygon, and the test relies on it: a self-crossing star such as
[[0,10],[6,-8],[-10,3],[10,3],[-6,-8]]turns the same way at every corner, sois_convexreturnsTruefor it. Don't add a crossing check; the promise makes it unnecessary.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use the Cross Product orientation test. For three points o, a and b, the cross product of a minus o with b minus o is positive when the path turns left, negative when it turns right, and zero when the three points are on one line. A polygon is convex exactly when its edge always turns the same way, so I walk the corners once, compute the turn at each one, and wrap around with modulo n so the two turns that close the loop are checked too. I keep prev, the last non-zero turn, and return false the moment a turn has the opposite sign. The trap is a turn of zero: that's a straight corner, which is allowed, so I skip it instead of calling it a dent or letting it erase prev. Everything stays in integers, with no division and no angles. That's
O(N)time andO(1)extra space.
Complexity & Mathematical Proof
O(N)
Count the work in is_convex. The loop for i in range(n) runs once per corner, N times. Each pass calls cross once, which does four subtractions, two multiplications and one more subtraction: O(1) whatever the coordinates. The test turn == 0, the sign comparison with prev and the assignment prev = turn are O(1) too. Nothing else loops, so the total is at most N passes of constant work: O(N). A dent can stop the loop early, but a convex polygon (the worst case) visits every corner.
O(1)
is_convex keeps n, i, turn and prev, and each call to cross keeps three references and returns one integer: O(1). The % n indices read points[0] and points[1] again instead of copying them to the end of a new list, so nothing grows with N.
T(N) = N · (one cross product + two comparisons) = O(N)
Derivation Progression
N
for i in range(n) runs once per corner; the % n indices reach the two turns that close the loop without a second pass.
O(1)
cross does a fixed number of subtractions and two multiplications, whatever the coordinates.
O(1)
turn == 0 and (turn > 0) != (prev > 0) are two comparisons; prev = turn is one assignment.
O(N)
N passes of constant work; a dent can only stop the loop sooner.
Variable Definitions
Number of corners, len(points) (at most 10^4)
Memory Architecture & Bounds
O(1): one call to cross at a time, no recursion
O(1): n, i, turn, prev
O(1): one boolean
Boundary Best / Worst Cases
: the second turn already goes the other way
: a convex polygon, where every corner is checked
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "you always turn the same way", "no dent", "a straight corner is not a turn", whole-number corners [x, y] joined in order. A question about the direction of turns between integer points: Cross Product, the sign of one integer per corner.
Up to corners with coordinates in . Each difference is below , so one cross product stays below and fits a 32-bit integer, but the product of two does not. One pass is cross products; testing every corner against every edge would be .
Real coordinates (GPS, CAD, game physics) are floating-point numbers: the cross product of three nearly collinear points can round to the wrong sign, so two tests can disagree about the same corner. Production geometry code uses exact or adaptive-precision arithmetic for this test, or snaps coordinates to an integer grid first, instead of a loose tolerance. A polygon streamed from disk only needs its first two corners (for the wrap-around) and the current three in memory.
Core Algorithmic State Invariants
- Why the Sign Flips at the Line
With o and a fixed, cross(o, a, b) is a linear function of b: it is 0 for every b on the line through o and a, and it only grows on one side and only shrinks on the other. So its sign changes exactly when b crosses that line, never anywhere else.
Convex Polygon (LeetCode 469)
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.
Worked Examples
points = [[0,0],[0,5],[5,5],[5,0]]true(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.points = [[0,0],[0,10],[10,10],[10,0],[5,5]]false(0,10), (10,10) and (10,0) are right turns, but at (5,5) the edge turns left: that corner points into the shape, so it has a dent. This turn is one of the two that close the loop, found only by wrapping around from the last point to the first.⚖️Formal Constraints & Bounds
3 <= points.length <= 104points[i].length == 2-104 <= xi, yi <= 104All the given points are unique.
Core Insight
One integer, cross(o, a, b), says whether the edge turns left or right at a corner. A polygon is convex exactly when every non-zero turn has the same sign, and a turn of 0 (a straight corner) changes nothing.
Real-World Scenario & Production Applications
A map or CAD tool checking that a drawn outline (a building footprint, a delivery zone, a collision shape in a game) has no dent before handing it to an algorithm that only works on convex shapes, such as a fast point-in-polygon test or a separating-axis collision check.
Step-by-Step Execution Trace Table
Example 2, points = [[0,0],[0,10],[10,10],[10,0],[5,5]] (n = 5):
| Step | i | Corner points[(i + 1) % n] | turn | prev before | Result |
|---|---|---|---|---|---|
| 1 | 0 | (0,10) | cross((0,0), (0,10), (10,10)) = -100 | 0 | first turn: prev = -100 (right) |
| 2 | 1 | (10,10) | cross((0,10), (10,10), (10,0)) = -100 | -100 | same sign: prev = -100 |
| 3 | 2 | (10,0) | cross((10,10), (10,0), (5,5)) = -50 | -100 | same sign: prev = -50 |
| 4 | 3 | (5,5) | cross((10,0), (5,5), (0,0)) = 50 | -50 | opposite sign: return False |
The dent is found at i = 3, whose third point points[(3 + 2) % 5] is points[0]: without the wrap-around the loop would stop at i = 2 and answer true.
The Math, Step by Step
1. The number that measures a turn
Walk from point to point , and then on to point . At you turn left, turn right, or go straight on. The code measures this with the cross product of the two vectors that start at , and :
The result is a whole number, because every coordinate is a whole number.
2. What the sign says
Only the sign of the cross product matters here:
cross(o, a, b) | The path | At corner |
|---|---|---|
| greater than 0 | turns counterclockwise | a left turn |
| less than 0 | turns clockwise | a right turn |
| equal to 0 | stays on one line | no turn |
The value is twice the signed area of the triangle . The area is positive when the corners go around counterclockwise, and negative when they go clockwise. It is 0 when the three points lie on one line and the triangle is flat.
A quick check: , and walk right and then up, which is a left turn. The cross product is .
3. Why one sign everywhere means convex
A simple polygon is convex exactly when a walk around its edge always turns the same way. If it turns left at some corners and right at others, a corner with the other direction points into the shape, which makes a dent.
So the code computes the turn at every corner and compares their signs. For corner number , the three points are points[i], points[(i + 1) % n] and points[(i + 2) % n]. The % n joins the last points back to the first ones. So the loop checks all corners, including the two where the walk closes the loop.
4. Straight corners, and the first real turn
A turn of 0 is a straight corner. It does not change the shape, so it cannot make the polygon non-convex. It also says nothing about the direction. So the code skips it with continue, and prev keeps the last turn that was not 0.
prev starts at 0, meaning "no direction seen yet". The first non-zero turn sets the direction. From then on, a turn with the other sign returns False. The test (turn > 0) != (prev > 0) compares only the signs, never the sizes.
5. Example 2 by hand
points = [[0,0],[0,10],[10,10],[10,0],[5,5]], so .
The picture shows the five corners as dots, labelled by index. It does not draw the edges. Join the dots in index order: from 0 up to 1, across to 2, down to 3, then to point 4 in the middle at , and back to 0. Point 4 lies inside the square formed by the first four points, so the polygon has a dent at point 4.
i | (the corner) | turn | Result | ||||
|---|---|---|---|---|---|---|---|
| 0 | first turn: right | ||||||
| 1 | right, same sign | ||||||
| 2 | right, same sign | ||||||
| 3 | left: return False |
At i = 3 the third point is points[(3 + 2) % 5] = points[0], so this turn is found only because % n wraps around to the first point. Its sign differs from the three right turns before it. The code returns false, the expected output.
6. Example 1 by hand
points = [[0,0],[0,5],[5,5],[5,0]], a square walked clockwise. All four turns are . For example, at i = 0 the vectors are and , so the turn is . No sign ever changes, so the loop ends and the code returns true, the expected output.
7. From the math to the code
| Math | In the code |
|---|---|
| with , | return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) |
| the turn at corner | turn = cross(points[i], points[(i + 1) % n], points[(i + 2) % n]) |
| a straight corner says nothing | if turn == 0: followed by continue |
| no direction seen yet | prev = 0 |
| a turn of the other sign is a dent | if prev != 0 and (turn > 0) != (prev > 0): followed by return False |
| remember the direction | prev = turn |
The loop computes one cross product per corner, so it takes time and space.
| 1 | The sign of `cross(o, a, b)` tells which way `o -> a -> b` turns: positive left, negative right, 0 straight. A convex polygon turns the same way at every corner. |
| 2 | Keep `prev`, the last non-zero turn; the polygon is convex exactly when no non-zero `turn` has the opposite sign. |
| 3 | For `i` in `range(n)`: `turn = cross(points[i], points[(i + 1) % n], points[(i + 2) % n])`; skip a 0; return `False` if `prev != 0 and (turn > 0) != (prev > 0)`; else `prev = turn`. Return `True` after the loop. |
| 4 | The trap: `if turn == 0: continue` before any comparison, and never store a 0 in `prev`: a straight corner is allowed, and forgetting the direction there lets a dent right after it slip through. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Convexity sounds like a question about angles, but it only needs directions: a polygon is convex exactly when walking along its edge you always turn the same way. The Cross Product measures a turn with one integer and no angle: cross(o, a, b) is positive when the path o -> a -> b turns left, negative when it turns right, and 0 when the three points lie on one line. So is_convex walks the corners once, computes turn at each one, and keeps prev, the last non-zero turn: the first turn whose sign differs from prev is a dent.
🚗 The Analogy: Driving Around a Block
Picture driving once around a city block that has no dents: at every corner you turn the same way, say always right. If you ever have to turn left, the block must bend inward there. Driving straight through a junction is no turn at all, so it tells you nothing: you keep remembering that your turns so far were right turns. The cross product is the steering wheel read as a number: positive for a left turn, negative for a right turn, zero when you go straight on.
🔑 Why It Works
cross(o, a, b) is (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]), twice the signed area of the triangle o, a, b. Its sign changes exactly when b moves from one side of the line through o and a to the other, so it measures the turn at a with integer multiplication and subtraction only: no division by zero on a vertical edge, no rounding. The % n indices make the last two turns, at points[n - 1] and points[0], part of the same loop. A turn of 0 is skipped before prev is touched, so a straight corner can neither be mistaken for a dent nor erase the direction the edge was turning.
Straight corners: write
if turn == 0: continuebefore comparing. A straight corner is allowed, and storing its 0 inprevoverwrites the last known direction: in[[6,6],[4,12],[0,12],[0,0],[12,0],[12,12],[8,12],[7,9]]the dent at[6,6], checked right after the straight corner[7,9], would pass.No wrap-around: use
points[(i + 1) % n]andpoints[(i + 2) % n]. The last two turns sit atpoints[n - 1]andpoints[0], and in[[0,0],[0,10],[10,10],[10,0],[5,5]]the dent at[5,5]is one of them.Multiplying signs: compare with
(turn > 0) != (prev > 0), notprev * turn < 0. Each cross product reaches about 8 * 10^8, so the product of two overflows a 32-bit integer in Java or C++.Slopes or angles:
dy / dxdivides by zero on a vertical edge andatan2rounds; the cross product stays in exact integers.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Each point is joined to the next one, and the last point is joined back to the first", "you always turn the same way (only left turns, or only right turns)", "a straight corner is not a turn", and whole-number corners [x, y]: a question about which way the edge turns between points in the plane. That is the signal for the Cross Product: one integer per corner says left, right or straight, with no angle and no division.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
The decision at each corner: skip a turn of 0; a non-zero turn with (turn > 0) != (prev > 0) while prev != 0 is a dent, so return False; otherwise prev = turn.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap:
if turn == 0: continueruns beforeprevis compared or changed (gotcha 1 shows the dent a stored 0 hides).Leading straight corners are harmless:
prevstays 0 until the first real turn, and theprev != 0test lets every corner pass until then.The statement promises a simple polygon, and the test relies on it: a self-crossing star such as
[[0,10],[6,-8],[-10,3],[10,3],[-6,-8]]turns the same way at every corner, sois_convexreturnsTruefor it. Don't add a crossing check; the promise makes it unnecessary.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use the Cross Product orientation test. For three points o, a and b, the cross product of a minus o with b minus o is positive when the path turns left, negative when it turns right, and zero when the three points are on one line. A polygon is convex exactly when its edge always turns the same way, so I walk the corners once, compute the turn at each one, and wrap around with modulo n so the two turns that close the loop are checked too. I keep prev, the last non-zero turn, and return false the moment a turn has the opposite sign. The trap is a turn of zero: that's a straight corner, which is allowed, so I skip it instead of calling it a dent or letting it erase prev. Everything stays in integers, with no division and no angles. That's
O(N)time andO(1)extra space.
Complexity & Mathematical Proof
O(N)
Count the work in is_convex. The loop for i in range(n) runs once per corner, N times. Each pass calls cross once, which does four subtractions, two multiplications and one more subtraction: O(1) whatever the coordinates. The test turn == 0, the sign comparison with prev and the assignment prev = turn are O(1) too. Nothing else loops, so the total is at most N passes of constant work: O(N). A dent can stop the loop early, but a convex polygon (the worst case) visits every corner.
O(1)
is_convex keeps n, i, turn and prev, and each call to cross keeps three references and returns one integer: O(1). The % n indices read points[0] and points[1] again instead of copying them to the end of a new list, so nothing grows with N.
T(N) = N · (one cross product + two comparisons) = O(N)
Derivation Progression
N
for i in range(n) runs once per corner; the % n indices reach the two turns that close the loop without a second pass.
O(1)
cross does a fixed number of subtractions and two multiplications, whatever the coordinates.
O(1)
turn == 0 and (turn > 0) != (prev > 0) are two comparisons; prev = turn is one assignment.
O(N)
N passes of constant work; a dent can only stop the loop sooner.
Variable Definitions
Number of corners, len(points) (at most 10^4)
Memory Architecture & Bounds
O(1): one call to cross at a time, no recursion
O(1): n, i, turn, prev
O(1): one boolean
Boundary Best / Worst Cases
: the second turn already goes the other way
: a convex polygon, where every corner is checked
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "you always turn the same way", "no dent", "a straight corner is not a turn", whole-number corners [x, y] joined in order. A question about the direction of turns between integer points: Cross Product, the sign of one integer per corner.
Up to corners with coordinates in . Each difference is below , so one cross product stays below and fits a 32-bit integer, but the product of two does not. One pass is cross products; testing every corner against every edge would be .
Real coordinates (GPS, CAD, game physics) are floating-point numbers: the cross product of three nearly collinear points can round to the wrong sign, so two tests can disagree about the same corner. Production geometry code uses exact or adaptive-precision arithmetic for this test, or snaps coordinates to an integer grid first, instead of a loose tolerance. A polygon streamed from disk only needs its first two corners (for the wrap-around) and the current three in memory.
Core Algorithmic State Invariants
- Why the Sign Flips at the Line
With o and a fixed, cross(o, a, b) is a linear function of b: it is 0 for every b on the line through o and a, and it only grows on one side and only shrinks on the other. So its sign changes exactly when b crosses that line, never anywhere else.