Overview
Bentley-Ottmann sweeps across segment endpoints and discovered intersections, maintaining the vertical order of active segments.
SpecializedSource checked
Bentley-Ottmann Algorithm
Finds all line segment intersections with a sweep line and event queue.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Advanced
- Family
- Sweep Line
- Tier
- Specialized
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
event queueactive setsweep lineneighbor intersection
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O((n + k) log n)
Average
O((n + k) log n)
Worst
O((n + k) log n)
Space
O(n + k)
When to Use
- Use when all intersections are needed and there may be far fewer intersections than segment pairs.
- Use when detecting map line crossings is a central requirement.
When Not to Use
- Avoid when the segment set is tiny enough for a simpler pairwise check.
- Avoid when floating-point precision or degenerate geometry cannot be handled robustly.
What It Does
- Processes geometric events in x order
- Maintains active segment order
- Reports neighboring segment intersections
Use Cases
- Detecting map line crossings
- CAD geometry validation
- Planar arrangement construction
Inputs
- Set of line segments
Outputs
- Intersection points
Key Formulas (1)
Sweep event order
process events by increasing x, then by event type and y
process events by increasing x, then by event type and yKeeps the sweep state deterministic around endpoints and intersections.
Pseudocode
- 1.Add segment endpoints to an event queue
- 2.Sweep events from left to right
- 3.Insert or remove segments from the active order
- 4.Check neighboring active segments for intersections
- 5.Add discovered intersection events
Canonical Example
- Input
- segments = two crossing lines and one separate line
- Output
- intersections = one crossing point
- Explanation
- The sweep only checks active neighbors instead of every pair.
Implementation Notes
- Use exact predicates or carefully designed tolerances for intersection ordering.
- Use robust predicates or tolerances when near-degenerate inputs are expected.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Failing to handle equal x coordinates and shared endpoints creates missed or duplicate events.
- Collinear, overlapping, and duplicate points need explicit tie-breaking rules.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasShow a vertical sweep line moving across segments while active neighbors swap at intersections.
Step 1 of 5: Add segment endpoints to an event queue
geometry-diagramNotes
Robust event ordering is difficult when segments overlap or share endpoints.
Sources (2)
What each reference supports for this entry.
Computational Geometry: Algorithms and Applications
BookComputational geometry textbook support for Bentley-Ottmann Algorithm's geometric model, data structures, and robustness concerns.
Open sourceBentley-Ottmann Sweep Line
PaperOriginal reference for reporting and counting geometric intersections using sweep-line status.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageIt detects and orders segment intersection events.
SpecializesSweep Line Algorithm
Bentley-Ottmann is a sweep-line algorithm for segment intersections.
Related Algorithms
Tags
GeometrySweep LineComputational GeometryCollision Detection