Overview
Line Segment Intersection tests segment orientation and endpoint cases to decide whether two finite segments intersect.
FoundationSource checked
Line Segment Intersection
Determines whether two line segments cross or touch.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Beginner
- Family
- Geometric Predicate
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 11
- Code example
- Not ready
- Visualization
- Ready
Core Concepts
geometric calculationgeometric predicatespatial relationshipcoordinate calculation
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(1)
Worst
O(1)
Space
O(1)
When to Use
- Use it to test whether two finite segments cross, touch, or overlap.
- Use it inside polygon, sweep-line, and collision algorithms.
- Use robust orientation predicates when coordinates are floating-point.
When Not to Use
- Avoid using infinite-line intersection when segment endpoints matter.
- Avoid ignoring collinear overlap and endpoint-touching cases.
- Avoid exact floating-point equality checks on near-degenerate geometry.
What It Does
- Compares segment orientations
- Handles crossing and touching cases
Use Cases
- Collision detection
- Map geometry validation
- Polygon operations
Inputs
- Two line segments
Outputs
- Intersection result
- Optional intersection point
Key Formulas (1)
Orientation test
orientation(a, b, c) = sign(cross(b − a, c − a))
orientation(a, b, c) = sign(cross(b - a, c - a))Checks relative turn direction for segment intersection tests.
Pseudocode
- 1.Compute orientations for each segment endpoint against the other segment
- 2.Check whether the orientations straddle
- 3.Handle collinear endpoint cases
- 4.Return whether the segments intersect
Canonical Example
- Input
- segment A = (0,0)-(2,2), segment B = (0,2)-(2,0)
- Output
- intersects = true
- Explanation
- The segments cross at the point (1,1).
Implementation Notes
- Use orientation tests for both endpoint pairs.
- Check bounding intervals for collinear cases.
- Define whether touching at an endpoint counts as intersection.
Common Pitfalls
- Handling only the crossing case and missing endpoint touches.
- Treating collinear overlapping segments as non-intersections.
- Using orientation signs without a tolerance or exact predicate when needed.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasShow segment endpoints and orientation signs for crossing tests.
Step 1 of 4: Compute orientations for each segment endpoint against the other segment
segment-crossingNotes
Most bugs in segment intersection come from degenerate cases, not from the general crossing case.
Sources (1)
What each reference supports for this entry.
Computational Geometry
BookComputational geometry textbook reference for the predicates or constructions used by Line Segment Intersection.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
UsesOrientation Test
Geometry · Foundation
Segment intersection uses orientation tests to compare endpoint orderings.
Compare with thisUsed byMarching Squares
Geometry · Core
It emits contour segments based on interpolated grid-edge crossings.
Compare with thisUsed bySutherland-Hodgman Polygon Clipping
Geometry · Core
Polygon clipping computes intersections between polygon edges and clip boundaries.
Compare with thisUsed byWeiler-Atherton Polygon Clipping
Geometry · Extended
It inserts intersection points between polygon and clipping boundaries.
Compare with thisRelationships
View full relationship pagePrerequisite ofBentley-Ottmann Algorithm
Bentley-Ottmann reports segment intersections efficiently.
Often paired withSweep Line Algorithm
Sweep-line algorithms frequently use segment intersection predicates.
Related Algorithms
Tags
GeometryComputational Geometry