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.
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.
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": [] }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": [] }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:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
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.
- Computational Geometry
Mark de Berg; Otfried Cheong; Marc van Kreveld; Mark Overmars (2008). Reference book.