Which side of a line a point falls on, whether two segments cross, which way a polygon is wound, whether a corner survives on a hull: all of them are the sign of the same determinant. The magnitude is twice the area of a triangle and is worth knowing, but almost every algorithm here throws it away and keeps the sign. The lab computes that one number by three different routes so that a transposed term shows up as a disagreement rather than as a plausible answer.
Core ideas
One idea, and two things that follow from it. The determinant is a signed area; the sign answers a question about sides; and both of those are only true if the arithmetic is exact, which is what the rest of this module is about.
Put b − a and c − a side by side as the columns of a 2×2 matrix. Its determinant, (bx − ax)(cy − ay) − (by − ay)(cx − ax), is twice the area of the triangle a b c, and it carries a sign. On the lab's opening points (0, 0), (4, 0), (2, 3) it is 12, so the triangle has area 6 and the turn from a to b to c is to the left. Nothing about that needs a picture; it is an integer computed from six integers.
A convex-hull step asks “did that turn go the wrong way”; a segment test asks “are these two endpoints on opposite sides”; a polygon's winding asks “is the total signed area positive”. Each of those is a comparison of the determinant against zero, and the magnitude is discarded. That is why this course cares enormously about whether the sign is right and hardly at all about whether the value is close.
The lab refuses a coordinate with a decimal point rather than rounding it, and refuses anything past 2⁵³. The second refusal is the interesting one: the determinant of huge integers is fine in arbitrary precision, but a coordinate beyond 2⁵³ is already the wrong number before any determinant is taken, so an exact answer about it would be an exact answer to a question nobody asked.
The material
The definition, the area theorem, the three routes the lab computes it by, and what each of them is for.
For points a, b, c in the plane, orient(a, b, c) is (bx − ax)(cy − ay) − (by − ay)(cx − ax). Its sign is 1 when the path a → b → c turns left (counter-clockwise), −1 when it turns right, and 0 when the three points lie on one line. All three of a, b, c are ordered arguments: swapping any two negates the determinant.
Two properties are worth having in hand before anything else. Negating on a swap means orient(a, b, c) = −orient(b, a, c), so “left of the line through a and b” and “right of the line through b and a” are the same statement. And the determinant depends only on the DIFFERENCES b − a and c − a, so translating all three points by the same vector changes nothing at all.
For any three points, |orient(a, b, c)| equals twice the area of the triangle a b c. In particular the determinant is zero exactly when the triangle is degenerate, which is exactly when the three points are collinear.
Translate so that a is the origin; the determinant is unchanged and so is the area. Write u = b − a and v = c − a. The parallelogram spanned by u and v has area |u| |v| sin θ, where θ is the angle from u to v, and the triangle is half of it.
Now |u| |v| sin θ is exactly ux·vy − uy·vx up to sign: expand |u| |v| sin(β − α) with u = |u|(cos α, sin α) and v = |v|(cos β, sin β) and the angle-difference identity gives |u| |v| (sin β cos α − cos β sin α), which is ux·vy − uy·vx. The sign of sin θ is positive when v is counter-clockwise from u and negative when it is clockwise, which is the sign claim, and the area is half the absolute value, which is the magnitude claim.
□
So a determinant of 1 — the smallest nonzero value an integer determinant can have — is a triangle of area one half. The lab's (0, 0), (7, 3), (5, 2) example is exactly that: the determinant is −1, the three points are very nearly on a line, and they are definitively not. There is no room between “area one half” and “area zero” for an integer to be uncertain about.
The lab's opening points are (0, 0), (4, 0), (2, 3). The 2×2 route computes (4 − 0)(3 − 0) − (0 − 0)(2 − 0) = 12. The 3×3 route expands the determinant of the matrix whose rows are (0, 0, 1), (4, 0, 1), (2, 3, 1) by cofactors along the last column, giving 0·(0 − 3) − 0·(4 − 2) + (4·3 − 2·0) = 12. The double route runs the first expression in ordinary floating point and also reports 12. Three routes, one number, and the lab prints all three side by side.
Why bother with the second route at all, when it is algebraically the same determinant? Because it is not the same ARITHMETIC. The 2×2 form multiplies differences of coordinates; the 3×3 form multiplies the coordinates themselves. A transposed subscript in either one produces a number that looks entirely reasonable, and the only thing that catches it is another route that would have to be wrong in precisely the same way. The lab flags a disagreement in red and declines to say which side is right.
Is c to the left of the directed line a → b? That is orient(a, b, c) > 0. Do the segments p₁p₂ and q₁q₂ cross properly? That is four such tests with opposite signs in pairs. Is the polygon v₁ … vₙ wound counter-clockwise? That is the sum of n such determinants being positive. Did the last point pushed onto a hull stack make a non-left turn, so the one below it is not a corner after all? Same test again.
Every page on this course is one of those four, which is why it is worth spending a lesson on a single arithmetic expression. Get the sign wrong once and the hull loses a vertex, the segment test answers about the wrong pair, and the polygon reports the wrong orientation — each of them silently, each of them returning a well-formed answer to a question it was asked correctly.
The lab prints the determinant, not just its sign, and the polygon page prints twice the area rather than the area. Doubling is what keeps it an integer: a lattice polygon's area can be a half, and a half is not representable as an integer, but twice it always is. Halving is left to the very end, and the result is printed as an exact fraction rather than as a decimal close to it.
That habit — postpone the division, keep the integer — is the whole of exactness in this course. Distances are kept squared for the same reason, since √2 is not a number this library can write down exactly and 2 is. Comparing squared distances orders pairs exactly as comparing distances does, so nothing is lost by never taking the root.
Interactive
One determinant, computed exactly twice and approximately once
Method
Subtract first, multiply second, and compare against zero third. Never divide.
Write u = b − a and v = c − a as two pairs of integers. This is where a hand computation goes wrong most often, and it is also where the arithmetic is guaranteed exact: a difference of two integers under 2⁵³ is an integer.
ux·vy and uy·vx, then the first minus the second. Keep both products whole; there is no intermediate quantity here that wants a decimal point.
Positive is a left turn, negative is a right turn, zero is collinear. If the question you are answering is a side question, you are finished — do not compute a slope, an angle or a distance to confirm it, because each of those introduces a division the determinant did not need.
Twice the area of the triangle, and nothing else. In particular the magnitude is not a distance from the line: that would be the determinant divided by |b − a|, and the moment you divide you are back in approximate arithmetic.
Take a = (0, 0), b = (4, 0), c = (2, 3), which is what the lab opens on, and then the near-degenerate triple (0, 0), (7, 3), (5, 2).
The second triple is the smallest nonzero determinant there is, and it is worth sitting with. Those three points are visibly almost on a line: (7, 3) and (5, 2) differ from the slope 3/7 by a hair. But 14 − 15 is −1 and not 0, and an integer has no way of being nearly zero. The turn is a right turn, definitely, and the area is one half, definitely.
Notice also that the 3×3 expansion does not compute a single one of the same products the 2×2 form does. It multiplies 7 by 2 and 5 by 3, where the other multiplies the same numbers because a happens to be the origin. Move a to (1, 1) and the two routes share nothing at all: the 2×2 form works with (6, 2) and (4, 1) and the 3×3 form still works with the original six coordinates. Redo both and confirm the answer is still −1.
For a faded rehearsal, predict the determinant of (0, 0), (5, 2), (7, 3) — the same three points with the last two swapped — before computing it. The supplied first move is the swap rule: exchanging two arguments negates the determinant, so the answer is +1 and the turn is a left turn. Then say what orient(b, c, a) is, and why a CYCLIC rotation of the three arguments leaves the sign alone while a swap does not.
You should be able to write the determinant from the definition, predict how it changes when two arguments are swapped or all three are translated, state the area theorem and why doubling keeps it an integer, and explain why a second route to the same number is worth computing.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.