Line-segment intersection: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Classify disjoint, touching, crossing and overlapping closed segments.

Evaluate four orientations. Opposite strict signs identify a proper crossing; otherwise test shared endpoints against both closed segments and distinguish a single common point from positive-length overlap.

Open the 3D visualization

Line-segment intersection example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Line-segment intersection

Classifying collisions between two closed planar segments.

Choosing an alternative

This constant-size predicate handles one segment pair; it is not a multi-segment sweep-line intersection enumerator.

Worked example: input and state changes

Example input

0,0;4,4;0,4;4,0

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Exact integer predicates; equal scale on both coordinate axes.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        2,
        3
      ],
      "active": [],
      "kind": "graph",
      "points": [
        [
          0,
          0
        ],
        [
          4,
          4
        ],
        [
          0,
          4
        ],
        [
          4,
          0
        ]
      ],
      "nodeLabels": [
        "0 (0, 0)",
        "1 (4, 4)",
        "2 (0, 4)",
        "3 (4, 0)"
      ],
      "directed": false,
      "chosen": [],
      "visited": [],
      "result": 0,
      "output": []
    }
  2. Step 1: Orientation signs: 16, -16, -16, 16.

    State at this checkpoint
    {
      "values": [
        0,
        1,
        2,
        3
      ],
      "active": [
        0,
        1,
        2,
        3
      ],
      "kind": "graph",
      "points": [
        [
          0,
          0
        ],
        [
          4,
          4
        ],
        [
          0,
          4
        ],
        [
          4,
          0
        ]
      ],
      "nodeLabels": [
        "0 (0, 0)",
        "1 (4, 4)",
        "2 (0, 4)",
        "3 (4, 0)"
      ],
      "directed": false,
      "chosen": [],
      "visited": [],
      "result": 0,
      "output": []
    }
  3. Step 2: Proper interior crossing

    State at this checkpoint
    {
      "values": [
        0,
        1,
        2,
        3
      ],
      "active": [
        0,
        1,
        2,
        3
      ],
      "kind": "graph",
      "points": [
        [
          0,
          0
        ],
        [
          4,
          4
        ],
        [
          0,
          4
        ],
        [
          4,
          0
        ]
      ],
      "nodeLabels": [
        "0 (0, 0)",
        "1 (4, 4)",
        "2 (0, 4)",
        "3 (4, 0)"
      ],
      "directed": false,
      "chosen": [
        0,
        1
      ],
      "visited": [],
      "result": 2,
      "output": []
    }

Expected final state

Proper interior crossing

Complexity and input bounds

Family: Geometry. Time complexity: O(1).

Implementation detail: Exactly four endpoint coordinates in -20..20. Return 0 disjoint, 1 touching, 2 proper crossing or 3 overlapping. This predicate does not compute the intersection coordinates. Both views preserve the coordinate aspect ratio. Independent fixtures cover degeneracies and deterministic outcomes in all nine languages.

Space complexity: O(n) index storage for closest-pair sweep; O(1) predicate state otherwise, excluding inputs and saved frames.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

Exactly four x,y points: segment endpoints A;B;C;D. Integers -20..20. 0 disjoint, 1 touch, 2 proper crossing, 3 positive-length overlap.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

Zero orientation alone does not prove containment. Check both coordinate intervals and support zero-length segments. Collinear overlap differs from one shared endpoint.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
1
2
3
4
5
6
7
8
// Exactly four endpoints x/y, integers -20..20, closed segments [0,1] and [2,3]. Return 0 disjoint, 1 single boundary point, 2 proper crossing, 3 positive-length overlap. Degenerate zero-length segments supported. Exact orientation and interval tests, O(1); no intersection coordinate or floating division. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(x, y) {
    let first = ((x[1]-x[0])*(y[2]-y[0])-(y[1]-y[0])*(x[2]-x[0])); let second = ((x[1]-x[0])*(y[3]-y[0])-(y[1]-y[0])*(x[3]-x[0])); let third = ((x[3]-x[2])*(y[0]-y[2])-(y[3]-y[2])*(x[0]-x[2])); let fourth = ((x[3]-x[2])*(y[1]-y[2])-(y[3]-y[2])*(x[1]-x[2]));
    if (first*second < 0 && third*fourth < 0) { return 2; }
    let seen = 0; let px = 0; let py = 0; let onFirst = 0; let onSecond = 0;
    for (let i = 0; i < 4; i++) { onFirst = 0; onSecond = 0; if (((x[1]-x[0])*(y[i]-y[0])-(y[1]-y[0])*(x[i]-x[0])) == 0 && (x[i]-x[0])*(x[i]-x[1]) <= 0 && (y[i]-y[0])*(y[i]-y[1]) <= 0) { onFirst = 1; } if (((x[3]-x[2])*(y[i]-y[2])-(y[3]-y[2])*(x[i]-x[2])) == 0 && (x[i]-x[2])*(x[i]-x[3]) <= 0 && (y[i]-y[2])*(y[i]-y[3]) <= 0) { onSecond = 1; } if (onFirst != 0 && onSecond != 0) { if (seen != 0 && (x[i] != px || y[i] != py)) { return 3; } seen = 1; px = x[i]; py = y[i]; } }
    return seen;
}

Source

Authoritative computational-geometry textbook covering segment intersection; not an asserted original research attribution for the elementary orientation predicate.