Two segments cross properly when each one has the other's endpoints strictly on opposite sides, which is four orientation tests with opposite signs in pairs. That covers the case everybody draws and none of the cases that are hard. A zero anywhere among the four means collinear, and collinear is a one-dimensional question the determinant cannot answer. The lab checks the four-sign verdict against an exact solve for the two parameters, which has no orientation sign in it at all.
Core ideas
The proper case, the reason it is not the whole answer, and a second route that reaches the same verdict without computing a single orientation.
The segment p₁p₂ crosses the LINE through q₁ and q₂ when q₁q₂ has p₁ and p₂ strictly on opposite sides, which is orient(q₁, q₂, p₁) and orient(q₁, q₂, p₂) differing in sign. That alone is not enough: the segments might cross each other's lines in places neither segment reaches. Asking the same question the other way round as well gives the proper-crossing test, and the two together are exactly right when no determinant is zero.
If any of the four is zero then three of the four points are collinear, and the verdict now depends on WHERE along the line things sit — which is a question a determinant is structurally unable to answer, since it is zero for every point on the line. The test has to fall back on comparing coordinates along the segment. Four of the seven worked examples on this page are cases the proper test alone gets wrong, and the lab counts them.
Solve p₁ + t(p₂ − p₁) = q₁ + u(q₂ − q₁) for t and u. Both are ratios of determinants, and the conditions 0 ≤ t ≤ 1 and 0 ≤ u ≤ 1 can be checked by comparing numerators against the denominator after forcing it positive — so nothing is ever divided and the whole thing stays in integers. The lab runs it beside the four-sign test on every input and reports whether the two agree.
The material
The four determinants, the theorem that makes them sufficient in general position, and the parametric solve that finishes the rest.
Segments p₁p₂ and q₁q₂ cross properly when orient(q₁, q₂, p₁) and orient(q₁, q₂, p₂) are nonzero with opposite signs and orient(p₁, p₂, q₁) and orient(p₁, p₂, q₂) are too. They touch when an endpoint of one lies on the other segment. They meet when they share at least one point, which is exactly when they cross properly or touch.
If all four orientation determinants are nonzero, then the segments meet if and only if they cross properly.
Suppose they cross properly. Then p₁ and p₂ are strictly on opposite sides of the line through q₁q₂, so the segment p₁p₂ meets that line at a single interior point x. Symmetrically the segment q₁q₂ meets the line through p₁p₂ at a single interior point y. Both x and y lie on both lines, and two distinct lines meet in at most one point — they are distinct because all four determinants are nonzero — so x = y, and that point is interior to both segments.
Conversely, suppose they meet at some point z and that no determinant is zero. Then no endpoint of either lies on the other's line, so z is interior to both segments; hence each segment has points strictly on both sides of the other's line, and since its endpoints are not on that line they must be on opposite sides. That is a proper crossing.
□
The hypothesis is doing all the work, and it is the hypothesis that almost never holds on real data. Rectilinear layouts, lattice coordinates, anything snapped to a grid, anything sharing endpoints: all of them produce zeros. An implementation that ships the proper test alone is correct on general position and wrong on the inputs people actually have.
Take p₁p₂ from (0, 0) to (6, 6) and q₁q₂ from (0, 6) to (6, 0). The four determinants are −36, 36, 36, −36, so the signs are −1, 1, 1, −1: opposite in each pair, none of them zero. The proper test says yes, the parametric solve says yes, and the bounding boxes overlap. Everything agrees, which is what makes this the wrong example to test an implementation on.
The magnitude 36 is the same for all four here because the configuration is symmetric, and it is worth remembering from “The Orientation Test” what those numbers mean: |orient(q₁, q₂, p₁)| = 36 says the triangle q₁ q₂ p₁ has area 18. The test discards every bit of that and keeps four signs.
Two segments whose bounding boxes do not overlap cannot meet, and that test is four comparisons with no multiplication in it. It is worth doing first, and it is never an answer: boxes that overlap say nothing at all. The lab prints the box verdict as its own row so that the distinction between a filter and a decision is on the page. None of the seven worked examples happens to have overlapping boxes and segments that miss, so type 0, 0; 4, 4; 2, 0; 4, 1 to see one: the boxes overlap, the four signs are 1, 1, −1, −1, and the segments do not meet.
Write a point of the first segment as p₁ + t(p₂ − p₁) and of the second as q₁ + u(q₂ − q₁). Setting them equal gives two linear equations in t and u, whose determinant is the cross product of the two direction vectors. When that is nonzero, t and u are ratios of determinants and the segments meet exactly when both lie in [0, 1]. Force the denominator positive by negating both numerators if necessary, and the test becomes four integer comparisons with no division.
When the denominator IS zero the directions are parallel, and there are two sub-cases: not collinear, where they cannot meet at all; and collinear, where the question becomes whether two intervals on a line overlap. The oracle handles that by projecting onto the first segment's direction with a dot product, which is a different computation from anything the four-sign test does. That is what makes it a check rather than a restatement, and the page reports a disagreement in red and declines to say which route is right.
Interactive
Four orientations against an exact solve for the two parameters
Method
Box filter, four signs, and then the case the signs cannot settle.
Four comparisons, no multiplications, and it disposes of most pairs in a large input. Never conclude anything from boxes that DO overlap: that is the filter failing to reject, not evidence of a crossing.
Not two, and not two with an early exit. You need to know whether any of them is zero before you know which branch you are in, and an implementation that short-circuits on the first pair has already thrown away the information that would have told it to take the collinear branch.
Opposite signs in each pair means yes, anything else means no, and the theorem above says that is exact. This is the only case where the four signs are the complete story.
A zero means three points are collinear, so ask whether the relevant endpoint lies BETWEEN the other two — a coordinate comparison, not a determinant. The next lesson is built on a pair of inputs with identical signs and opposite answers, which is what makes this step unskippable.
First (0, 0)–(6, 6) against (0, 6)–(6, 0); then (0, 0)–(6, 0) against (3, 0)–(3, 5), where one segment ends on the other.
The second case is the whole lesson in one table. A test that computed proper and returned it would answer NO here, and the segments plainly meet: q₁ is the point (3, 0), which is on the first segment. The zero in the third row is the signal that the proper test has run out of information, and the touching column is what finishes the job.
Notice that the first pair of signs is still opposite in the T-junction. Three quarters of the proper test is satisfied, which is exactly why this case survives so long in implementations: it fails only on the last row, and only when the reader thinks to construct it.
For a faded rehearsal, work out all four signs for (0, 0)–(4, 0) against (4, 0)–(4, 5), which share the endpoint (4, 0) and nothing else. The supplied first move is that two of the four will be zero, because (4, 0) lies on both lines. Predict which two, predict both verdicts, and then say why proper is false on an input where the right answer is obviously yes.
You should be able to write down the four orientations in the right order, state and prove why they are sufficient in general position, name the three degenerate families a zero can indicate, and explain why the parametric route is worth running even though both routes are exact.
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.