Segment Intersection Test

Take two straight line segments drawn on a page. Do they cross? Your eyes answer instantly, but teaching a computer to answer takes some care — and doing it fast, exactly, and without corner cases blowing up is a small classic of computational geometry.

The tempting approach is algebra: write each segment as a line $y = mx + b$, solve for the intersection point, then check whether that point actually falls inside both segments. It works, but it is clumsy — vertical segments break the slope, and floating-point coordinates for the crossing point invite rounding errors right when you need an exact yes-or-no.

There is a cleaner way that never solves for a point at all. It only asks, for each segment, which side of it the other segment's endpoints fall on. That single idea — the sign of a turn — is enough to decide crossings exactly, and it shows up everywhere from video-game collision to chip design.

Drag the endpoints of the two segments below. For each segment, the demo checks which side its two turns fall on relative to the other segment — four little signs, updated live.

<p class="hint">{{hint_para}}</p>
<svg id="stage" viewBox="0 0 360 260" class="stage"></svg>
<div class="signs" id="signs"></div>
<div class="status" id="status">{{drag_hint}}</div>
<div class="btns">
  <button id="cross" type="button">{{btn_cross}}</button>
  <button id="collinear" type="button">{{btn_collinear}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.stage { width: 100%; max-width: 420px; height: 240px; background: #eef2f6; border: 1px solid #cdd9e3;
         border-radius: 10px; touch-action: none; }
.seg-ab { stroke: #1d3557; stroke-width: 3; }
.seg-cd { stroke: #e63946; stroke-width: 3; }
.handle { cursor: grab; }
.handle:active { cursor: grabbing; }
.handle-ab { fill: #1d3557; stroke: #fff; stroke-width: 1.5; }
.handle-cd { fill: #e63946; stroke: #fff; stroke-width: 1.5; }
.label { font: 700 12px ui-monospace, monospace; fill: #445; pointer-events: none; }
.signs { display: flex; gap: .6rem; flex-wrap: wrap; margin: .55rem 0; font: 600 13px ui-monospace, monospace; }
.sign { padding: .2rem .5rem; border-radius: 6px; background: #e8eef3; border: 1px solid #cdd9e3; }
.sign.pos { background: #e6f6ea; border-color: #9fd8ae; color: #0a7d33; }
.sign.neg { background: #fdeaec; border-color: #f3aab1; color: #c92f3c; }
.sign.zero { background: #fff6df; border-color: #f0d78a; color: #9a7a08; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.warn { color: #9a7a08; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Watch what happens right at a crossing: the two signs computed against segment AB point opposite ways, and the two signs computed against segment CD also point opposite ways. That double disagreement is the whole test. Nudge a segment until it merely touches without truly crossing, and you will see one of the signs pass through exactly zero — the collinear case the test has to handle separately.

The core tool is the orientation of an ordered triple of points $A$, $B$, $C$: turning from $A \to B \to C$, do you turn left, turn right, or stay straight? It is computed with a single cross product,

$$\text{orient}(A,B,C) = (B_x - A_x)(C_y - A_y) - (B_y - A_y)(C_x - A_x),$$

whose sign — positive, negative, or exactly zero — is all that matters. Positive means counter-clockwise, negative means clockwise, and zero means $A$, $B$, $C$ are collinear.

• The general test. Segments $AB$ and $CD$ cross (as open segments, ignoring touching endpoints for now) exactly when $C$ and $D$ lie on opposite sides of line $AB$, and $A$ and $B$ lie on opposite sides of line $CD$. In signs: $\text{orient}(A,B,C)$ and $\text{orient}(A,B,D)$ must differ, and $\text{orient}(C,D,A)$ and $\text{orient}(C,D,B)$ must differ.
• Why it's exact. Every quantity involved is a sum of products of the input coordinates — no division, no square root, no trigonometry. With integer or fixed-precision input the sign is computed exactly, which is exactly why this test, not the "solve for the intersection point" approach, is the standard building block in real geometry engines.
• The collinear special case. If any orientation comes out to zero, the two points are exactly on the line, and the general rule above cannot be trusted alone. The segments might overlap along a line, touch at a single endpoint, or miss each other entirely while collinear — this needs an explicit on-segment bounding-box check ($C$ must lie between $A$ and $B$) layered on top.
• Cost. Four orientation computations, four comparisons, and — only when a zero appears — a handful of coordinate comparisons. That is $O(1)$ time and $O(1)$ space per pair of segments, independent of how large the coordinates are.

This primitive is also exactly what powers the sweep line in Segment Intersection: scaling the same yes/no test to many segments at once is what turns an $O(n^2)$ pairwise scan into an output-sensitive algorithm.

The orientation test is a primitive — a small building block that bigger geometric algorithms lean on constantly:

• Video games and physics: a bullet's path, a laser, a raycast — all reduce to "does this segment cross that wall?", checked thousands of times per frame.
• GIS and map overlays: does a proposed road cross a protected river or a property boundary? Overlaying two maps means testing many segment pairs for crossings.
• Polygon algorithms: testing whether a polygon is simple (its edges never cross itself), clipping one polygon against another, and computing point-in-polygon all reduce to orientation tests.
• Robot motion planning and CAD: deciding whether a straight-line move collides with an obstacle edge, or whether two wires on a chip layout would short, is the same crossing question at industrial scale.

Learn this one test and you have the atomic operation behind Convex Hull and the many-segment sweep of Segment Intersection — nearly every shape algorithm eventually asks "which side is this point on?"

Deciding whether two segments cross does not need a solved system of equations or a single floating-point division. It needs only the sign of a cross product, evaluated four times, compared for disagreement on both sides — plus one careful branch for when three points fall dead on the same line.

That is the quiet elegance behind computational geometry: hard-looking questions about shapes usually collapse into "what is the sign of this expression?" Master the orientation test and you are holding the same tool that scales up to sweep lines, convex hulls, and every polygon algorithm built on top of it.