Collinear segments produce four zero determinants whatever they do. Two of the lab's worked examples have exactly the same four signs — 0, 0, 0, 0 — and opposite answers: one pair overlaps and one pair has a gap. Since the inputs agree on every quantity the sign test computes, no amount of care with the signs can distinguish them, and the collinear case has to be finished as a one-dimensional interval question.
Core ideas
A pair of inputs, the argument they make, and the machinery that actually finishes the case.
That is not a defect of the orientation test, it is what the test means: orient(a, b, c) = 0 says c is on the line through a and b, with no information about where. Once all four points are collinear, all four determinants are zero and every one of them will stay zero however you perturb the points along the line. There is simply no more signal to extract.
(0, 0)–(6, 0) against (4, 0)–(10, 0) overlaps on the interval from 4 to 6. (0, 0)–(4, 0) against (6, 0)–(10, 0) has a gap from 4 to 6. Both produce 0, 0, 0, 0. Any function of the four signs must give them the same answer, and the right answers are different, so no such function is the intersection test. That is a proof and not a warning, and it takes two lines of the lab to demonstrate.
Project both segments onto the direction of the first: t₀ = (q₁ − p₁)·r and t₁ = t₀ + (q₂ − q₁)·r, where r = p₂ − p₁. The first segment occupies [0, r·r] in that coordinate, the second occupies the interval between t₀ and t₁, and the two meet exactly when those intervals overlap. Every quantity there is an integer dot product, so the whole test is exact, and it uses no determinant.
The material
The impossibility argument, the interval test that finishes the case, and the degenerate inputs that reach it.
Two segments are collinear when all four endpoints lie on one line, which makes all four orientation determinants zero. For collinear segments with r = p₂ − p₁ nonzero, define the projection coordinate of a point x as (x − p₁)·r. In this coordinate p₁ is at 0 and p₂ is at r·r, and both are integers whenever the endpoints are.
There exist two pairs of segments whose four orientation signs are equal, one of which meets and one of which does not. Consequently any intersection test computed from the four signs alone is wrong on at least one of them.
Take p₁p₂ = (0, 0)–(6, 0) with q₁q₂ = (4, 0)–(10, 0), and p₁p₂ = (0, 0)–(4, 0) with q₁q₂ = (6, 0)–(10, 0). In both, all four points lie on the line y = 0, so all four determinants are zero and the sign vectors are both (0, 0, 0, 0).
The first pair shares every point with 4 ≤ x ≤ 6, so it meets. The second pair has the first segment ending at x = 4 and the second starting at x = 6, so no point is on both and it does not meet. A function of the sign vector returns one value on that vector, and it cannot be both true and false.
□
That argument is short and it is worth stating as a theorem rather than as a remark, because the usual reaction to the collinear case is to look for a cleverer combination of the signs. There is none, and the reason is structural: the signs are a function of which side of each line each point is on, and when everything is on the line, every input with that property has the same signature.
Select the overlapping collinear worked example and read the KPI row: proper crossing no, touching yes, bounding boxes overlap yes, verdict they meet. Select the one with the gap: proper crossing no, touching no, bounding boxes overlap NO, verdict they miss. The four-sign table above is byte-for-byte identical between the two runs, and every other row on the page changes.
One label to distrust while you are there. The worked example with the gap is offered as “collinear, boxes touching, no overlap”, and the boxes are not touching: they are the intervals from 0 to 4 and from 6 to 10, with two units between them, and the widget's own bounding-box row reports NO on that input. Read the row, not the label. While you are checking: none of the seven worked examples has overlapping boxes AND segments that miss, so the one case that shows the filter failing to decide has to be typed. 0, 0; 4, 4; 2, 0; 4, 1 does it — boxes overlapping, no crossing, and the status line then says the boxes are a filter and never an answer.
The bounding boxes DO separate these two, and it is worth working out why, because the answer is more interesting than a coincidence. Along a line, both coordinates are monotone in the parameter: if the direction has rx ≠ 0 then x increases or decreases steadily, and if rx = 0 the segment is vertical and y does. So for COLLINEAR segments, overlapping boxes and overlapping intervals along the line are the same condition, and the box test is not a filter at all here — it is exact. Running 197,506 random collinear pairs past both tests produces not one disagreement.
That does not make the box test the answer, for two reasons. It stops being exact the moment the segments are not collinear, which is the whole of the rest of the problem and where 0, 0; 4, 4; 2, 0; 4, 1 lives. And it says nothing about the degenerate case below, where one segment is a point. The projection coordinate is the form worth learning because it is the same computation in both, and because it states the question in the coordinate the answer actually lives in rather than in two coordinates that happen to agree with it.
A segment whose two endpoints coincide is a point. The lab has one: the point (3, 2) against the segment from (0, 0) to (6, 4), which passes through it. All four determinants are zero again, proper is false, and the right answer is yes. The parametric route handles this by noticing that r·r = 0 and falling back to asking whether the point lies on the other segment; a route that divided by r·r would have failed here instead.
That is the third distinct family that produces four zeros: collinear and overlapping, collinear and disjoint, and degenerate. A fourth is nearly there — a shared endpoint gives two zeros rather than four. The lab's preset list walks all of them deliberately, and four of its seven entries are inputs the proper test alone gets wrong.
The projection coordinates t₀ and t₁ are dot products of integer vectors, so they are integers, and the first segment occupies [0, r·r] which is also an integer interval. The test is then max(t₀, t₁) ≥ 0 and min(t₀, t₁) ≤ r·r, two integer comparisons. No normalisation, no direction vector of unit length, no division.
It is worth appreciating how little this costs. The entire collinear branch is a handful of multiplications and two comparisons, and it converts a test that is right on general position into one that is right on everything. The usual reason it is missing from an implementation is not cost; it is that the author never constructed an input that reaches it.
Interactive
Four orientations against an exact solve for the two parameters
Method
Once the determinant is zero, stop thinking about sides and start thinking about intervals.
Four zeros means all four points are on one line. Two zeros usually means a shared or touching endpoint. One zero means one endpoint is on the other's line. Each leads somewhere different, so read all four before branching.
Take r = p₂ − p₁ and compute (x − p₁)·r for the other segment's endpoints. If r·r is zero the first segment is a point, and the question is just whether that point lies on the other segment.
The first segment is [0, r·r]; the second is the interval between the two projected values, in whichever order they came out. They meet when the intervals overlap, which is two comparisons. Everything here is an integer and nothing is normalised.
Any implementation of this branch should be run on the overlapping pair and the pair with a gap. They are the minimal pair of inputs that distinguishes a correct collinear branch from a missing one, and a test suite without something like them will pass on an implementation that has no collinear branch at all.
Both are horizontal and both give four zero determinants. Only one of them meets.
The top half of that table is the same twice, and the bottom half is where the answer lives. That is the argument in its most compact form: everything the sign test computes is identical, so the sign test cannot be the answer.
The projection rows are worth reading carefully, because they show the general machinery producing the right answer on both. In the overlapping case the second segment's interval starts at 24 and the first ends at 36, so they share [24, 36]. In the other case the first ends at 16 and the second starts at 24, so they do not. Note that 24 appears in both columns and means different things, because r is different — the coordinate is relative to the first segment's own direction and length.
For a faded rehearsal, construct a diagonal version: (0, 0)–(6, 6) against (4, 4)–(10, 10), and then against (8, 8)–(10, 10). The supplied first move is that r = (6, 6) so r·r = 72 in both. Compute the two projection intervals for each and predict the verdicts; then check that the bounding boxes agree with them, as the monotonicity argument above says they must, and say what would have to change about the input for them to stop agreeing.
You should be able to construct the identical-signature pair from memory, state why no function of the signs can separate them, project a collinear pair onto the first segment's direction and decide the overlap in integers, and say which degenerate families produce four zeros and which produce two.
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.