Introduction

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+by = 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.

Watch the Signs Flip

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">Drag the endpoints A, B, C, D. The demo computes the sign of a cross product (orientation) four times and checks whether the signs disagree on both sides — that disagreement is the whole crossing test.</p>
<svg id="stage" viewBox="0 0 360 260" class="stage"></svg>
<div class="signs" id="signs"></div>
<div class="status" id="status">Drag any point to move a segment.</div>
<div class="btns">
  <button id="cross" type="button">Crossing example</button>
  <button id="collinear" type="button">Collinear example</button>
  <button id="reset" type="button" class="ghost">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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Orientation test for segment crossing. A segment AB crosses CD iff
// C and D fall on opposite sides of AB, and A and B fall on opposite sides of CD.
const EPS = 1e-6;

// Draggable endpoints of the two segments, in SVG viewBox coordinates.
let A = { x: 60, y: 60 };
let B = { x: 300, y: 200 };
let C = { x: 60, y: 200 };
let D = { x: 300, y: 60 };

const svgNS = 'http://www.w3.org/2000/svg';
const stage = document.getElementById('stage');

// Sign of the cross product (B-A) x (C-A): + = counter-clockwise, - = clockwise, 0 = collinear.
function orient(ax, ay, bx, by, cx, cy) {
  const v = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
  if (Math.abs(v) < EPS) return 0;
  return v > 0 ? 1 : -1;
}
// Bounding-box check used only when three points are already known to be collinear.
function onSegment(ax, ay, bx, by, cx, cy) {
  return Math.min(ax, bx) - EPS <= cx && cx <= Math.max(ax, bx) + EPS &&
         Math.min(ay, by) - EPS <= cy && cy <= Math.max(ay, by) + EPS;
}
// The full test, general case plus the collinear special case.
function segmentsIntersect(p1, p2, p3, p4) {
  const o1 = orient(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y);
  const o2 = orient(p1.x, p1.y, p2.x, p2.y, p4.x, p4.y);
  const o3 = orient(p3.x, p3.y, p4.x, p4.y, p1.x, p1.y);
  const o4 = orient(p3.x, p3.y, p4.x, p4.y, p2.x, p2.y);
  let collinearTouch = false;
  if (o1 === 0 && onSegment(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y)) collinearTouch = true;
  if (o2 === 0 && onSegment(p1.x, p1.y, p2.x, p2.y, p4.x, p4.y)) collinearTouch = true;
  if (o3 === 0 && onSegment(p3.x, p3.y, p4.x, p4.y, p1.x, p1.y)) collinearTouch = true;
  if (o4 === 0 && onSegment(p3.x, p3.y, p4.x, p4.y, p2.x, p2.y)) collinearTouch = true;
  const crosses = (o1 !== o2 && o3 !== o4) || collinearTouch;
  return { o1, o2, o3, o4, crosses, anyZero: (o1 === 0 || o2 === 0 || o3 === 0 || o4 === 0) };
}

function signEl(labelText, value) {
  const cls = value > 0 ? 'pos' : value < 0 ? 'neg' : 'zero';
  const glyph = value > 0 ? '+' : value < 0 ? '−' : '0';
  const span = document.createElement('span');
  span.className = 'sign ' + cls;
  span.textContent = i18nFmt('%name% = %glyph%', { name: labelText, glyph: glyph });
  return span;
}

let dragging = null; // Which endpoint (if any) is currently being dragged.

function makeHandle(point, cls, key) {
  const c = document.createElementNS(svgNS, 'circle');
  c.setAttribute('r', 8);
  c.setAttribute('class', 'handle ' + cls);
  c.setAttribute('cx', point.x);
  c.setAttribute('cy', point.y);
  c.addEventListener('pointerdown', (e) => { dragging = key; e.target.setPointerCapture(e.pointerId); });
  return c;
}

function labelEl(point, text, dx, dy) {
  const t = document.createElementNS(svgNS, 'text');
  t.setAttribute('x', point.x + dx);
  t.setAttribute('y', point.y + dy);
  t.setAttribute('class', 'label');
  t.textContent = text;
  return t;
}

function render() {
  stage.innerHTML = '';
  const lineAB = document.createElementNS(svgNS, 'line');
  lineAB.setAttribute('x1', A.x); lineAB.setAttribute('y1', A.y);
  lineAB.setAttribute('x2', B.x); lineAB.setAttribute('y2', B.y);
  lineAB.setAttribute('class', 'seg-ab');
  stage.appendChild(lineAB);

  const lineCD = document.createElementNS(svgNS, 'line');
  lineCD.setAttribute('x1', C.x); lineCD.setAttribute('y1', C.y);
  lineCD.setAttribute('x2', D.x); lineCD.setAttribute('y2', D.y);
  lineCD.setAttribute('class', 'seg-cd');
  stage.appendChild(lineCD);

  stage.appendChild(labelEl(A, 'A', -14, -10));
  stage.appendChild(labelEl(B, 'B', 10, -10));
  stage.appendChild(labelEl(C, 'C', -14, 18));
  stage.appendChild(labelEl(D, 'D', 10, 18));

  stage.appendChild(makeHandle(A, 'handle-ab', 'A'));
  stage.appendChild(makeHandle(B, 'handle-ab', 'B'));
  stage.appendChild(makeHandle(C, 'handle-cd', 'C'));
  stage.appendChild(makeHandle(D, 'handle-cd', 'D'));

  const r = segmentsIntersect(A, B, C, D);
  const signs = document.getElementById('signs');
  signs.innerHTML = '';
  signs.appendChild(signEl('orient(A,B,C)', r.o1));
  signs.appendChild(signEl('orient(A,B,D)', r.o2));
  signs.appendChild(signEl('orient(C,D,A)', r.o3));
  signs.appendChild(signEl('orient(C,D,B)', r.o4));

  const status = document.getElementById('status');
  if (r.crosses && r.anyZero) {
    status.textContent = '⚠ Collinear case: a point lies exactly on the other line — checked with the on-segment rule.';
    status.className = 'status warn';
  } else if (r.crosses) {
    status.textContent = '✓ The segments cross (signs split both ways).';
    status.className = 'status ok';
  } else {
    status.textContent = '✗ The segments do not cross (signs agree on at least one side).';
    status.className = 'status bad';
  }
}

function pointFromEvent(e) {
  const rect = stage.getBoundingClientRect();
  const vb = stage.viewBox.baseVal;
  const x = (e.clientX - rect.left) * (vb.width / rect.width);
  const y = (e.clientY - rect.top) * (vb.height / rect.height);
  return {
    x: Math.max(10, Math.min(vb.width - 10, x)),
    y: Math.max(10, Math.min(vb.height - 10, y)),
  };
}

stage.addEventListener('pointermove', (e) => {
  if (!dragging) return;
  const p = pointFromEvent(e);
  if (dragging === 'A') A = p; else if (dragging === 'B') B = p;
  else if (dragging === 'C') C = p; else if (dragging === 'D') D = p;
  render();
});
stage.addEventListener('pointerup', () => { dragging = null; });
stage.addEventListener('pointerleave', () => { dragging = null; });

function setCrossing() {
  A = { x: 60, y: 60 }; B = { x: 300, y: 200 };
  C = { x: 60, y: 200 }; D = { x: 300, y: 60 };
  render();
}
function setCollinear() {
  // Four collinear points with an overlapping stretch, to show the special case.
  A = { x: 40, y: 130 }; B = { x: 200, y: 130 };
  C = { x: 140, y: 130 }; D = { x: 320, y: 130 };
  render();
}
document.getElementById('cross').addEventListener('click', setCrossing);
document.getElementById('collinear').addEventListener('click', setCollinear);
document.getElementById('reset').addEventListener('click', setCrossing);

render();
Result
Console

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 Real Complexity

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

orient(A,B,C)=(Bx−Ax)(Cy−Ay)−(By−Ay)(Cx−Ax),\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 AA, BB, CC are collinear.

  • The general test. Segments ABAB and CDCD cross (as open segments, ignoring touching endpoints for now) exactly when CC and DD lie on opposite sides of line ABAB, and AA and BB lie on opposite sides of line CDCD. In signs: orient(A,B,C)\text{orient}(A,B,C) and orient(A,B,D)\text{orient}(A,B,D) must differ, and orient(C,D,A)\text{orient}(C,D,A) and orient(C,D,B)\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 (CC must lie between AA and BB) layered on top.
  • Cost. Four orientation computations, four comparisons, and — only when a zero appears — a handful of coordinate comparisons. That is O(1)O(1) time and O(1)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(n2)O(n^2) pairwise scan into an output-sensitive algorithm.

Where It Matters

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?"

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/line-segment-intersection/Content licensed under CC BY-NC 4.0.