README
¶
benott
A blazingly fast, production-ready Go implementation of the Bentley-Ottmann algorithm for counting line segment intersections.
Overview
This library provides an efficient and robust solution for a classic computational geometry problem: finding the number of intersections in a set of 2D line segments. It uses a sweep-line algorithm powered by a Red-Black Tree for its status structure, ensuring optimal performance.
The implementation is carefully designed to handle complex edge cases, including vertical segments and multiple segments intersecting at a single point, making it suitable for demanding, production-level applications.
Features
- High Performance: Achieves the optimal
O((n+k) log n)time complexity, wherenis the number of segments andkis the number of intersections. - Robust and Accurate: Correctly handles edge cases like vertical lines, collinear points, and multiple segments intersecting at the same point.
- Extensively Tested: Near-perfect test coverage ensures reliability and correctness.
- Simple API: A single, clear entry point (
CountIntersections) makes the library easy to integrate. - Memory Efficient: Predictable, linear memory scaling with the number of input segments.
Installation
go get github.com/GregoryKogan/benott
Usage
Here is a simple example of how to use the library to count intersections.
package main
import (
"fmt"
"github.com/GregoryKogan/benott"
)
func main() {
// Define a set of line segments.
segments := []benott.Segment{
{P1: benott.Point{X: 0, Y: 0}, P2: benott.Point{X: 10, Y: 10}},
{P1: benott.Point{X: 0, Y: 10}, P2: benott.Point{X: 10, Y: 0}},
{P1: benott.Point{X: 5, Y: 0}, P2: benott.Point{X: 5, Y: 10}},
}
// Count the number of intersections.
// For this "star" pattern, the 3 segments intersect at one point,
// creating 3 unique intersection pairs: (s1,s2), (s1,s3), (s2,s3).
intersections := benott.CountIntersections(segments)
fmt.Printf("Found %d intersections.\n", intersections)
// Output: Found 3 intersections.
}
Performance
Benchmarks confirm the library's optimal O((n+k) log n) time complexity. The charts below show how the algorithm's runtime scales with the number of segments (n) and the number of intersections (k). The log-log scale helps visualize the near-linearithmic relationship.
Benchmarks were run on an Apple M1 Pro.
Scaling with Number of Segments (n)
This test uses randomly generated segments, where k is sparse. The runtime scales predictably, demonstrating the O(n log n) characteristic.
Scaling with Number of Intersections (k)
This test uses a grid of segments to generate a high number of intersections. The runtime scales nearly linearly with k, demonstrating the O(k log n) characteristic under high-contention scenarios.
| Benchmark | Operations | Time/Op | Memory/Op | Allocs/Op |
|---|---|---|---|---|
BenchmarkRandomSegments/N=10 |
403344 | 2947 ns/op | 1977 B/op | 26 allocs/op |
BenchmarkRandomSegments/N=100 |
15524 | 76822 ns/op | 24716 B/op | 335 allocs/op |
BenchmarkRandomSegments/N=1000 |
825 | 1433473 ns/op | 259955 B/op | 3625 allocs/op |
BenchmarkRandomSegments/N=10000 |
50 | 22666170 ns/op | 3337015 B/op | 39149 allocs/op |
BenchmarkGridSegments/Grid=10x10_Segments=20_Intersections=100 |
27460 | 43430 ns/op | 21351 B/op | 426 allocs/op |
BenchmarkGridSegments/Grid=50x50_Segments=100_Intersections=2500 |
972 | 1202848 ns/op | 475963 B/op | 10108 allocs/op |
BenchmarkGridSegments/Grid=100x100_Segments=200_Intersections=10000 |
222 | 5393481 ns/op | 1879555 B/op | 40217 allocs/op |
BenchmarkGridSegments/Grid=200x200_Segments=400_Intersections=40000 |
50 | 24858878 ns/op | 7453333 B/op | 160756 allocs/op |
The results show excellent, predictable scaling in line with the algorithm's optimal complexity.
Contributing
Contributions are welcome! Please feel free to submit a pull request or open an issue for bugs, feature requests, or suggestions.
License
This project is licensed under the MIT License. See the LICENSE file for details.
This project also includes third-party dependencies. Their licenses are collected in the LICENSES-3RD-PARTY.md file.
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func CountIntersections ¶
CountIntersections implements the Bentley-Ottmann algorithm to find the total number of intersection points in a given set of line segments.
The algorithm uses a sweep-line approach, processing events (segment endpoints and intersections) from left to right. It maintains a status structure (a Red-Black Tree) of segments that cross the sweep line, ordered vertically. This allows it to efficiently find new intersections only between adjacent segments.
The time complexity is O((n+k) log n), where n is the number of segments and k is the number of intersections. The space complexity is O(n+k).
It correctly handles complex cases, including vertical segments and multiple segments intersecting at a single point.
Types ¶
type Event ¶
type Event struct {
// Point is the coordinate in the 2D plane where the event occurs.
Point Point
// Type is the nature of the event (e.g., SegmentStart, Intersection).
Type EventType
// Seg1 is the primary segment associated with this event.
Seg1 *Segment
// Seg2 is the second segment, used only for Intersection events.
Seg2 *Segment
}
Event represents a significant point in the 2D plane to be processed by the Bentley-Ottmann algorithm. Each event has a location (Point), a Type, and one or more associated Segments.
type EventQueue ¶
type EventQueue []*Event
EventQueue is a min-priority queue of events, implemented using Go's container/heap. Events are ordered primarily by their X-coordinate, then by their Y-coordinate as a tie-breaker. This ensures the sweep-line processes points from left-to-right, bottom-to-top.
func (EventQueue) Len ¶
func (eq EventQueue) Len() int
Len returns the number of events in the queue.
func (EventQueue) Less ¶
func (eq EventQueue) Less(i, j int) bool
Less reports whether the event at index i should be sorted before the event at index j.
func (*EventQueue) Pop ¶
func (eq *EventQueue) Pop() any
Pop removes and returns the event with the lowest value (highest priority) from the queue.
func (*EventQueue) Push ¶
func (eq *EventQueue) Push(x any)
Push adds an event to the priority queue.
func (EventQueue) Swap ¶
func (eq EventQueue) Swap(i, j int)
Swap swaps the events at indices i and j.
type EventType ¶
type EventType int
EventType defines the nature of an event in the sweep-line algorithm.
const ( // SegmentStart signifies that the sweep line has reached the left endpoint of a segment. SegmentStart EventType = iota // SegmentEnd signifies that the sweep line has reached the right endpoint of a segment. SegmentEnd // Intersection signifies that the sweep line has reached a point where two or more segments cross. Intersection )
type Point ¶
type Point struct {
X, Y float64
}
Point represents a point in a 2D Cartesian coordinate system.
type Segment ¶
type Segment struct {
P1, P2 Point
// contains filtered or unexported fields
}
Segment represents a line segment in 2D space, defined by two endpoints, P1 and P2.
type Status ¶
type Status struct {
// contains filtered or unexported fields
}
Status represents the sweep-line status structure. It maintains the set of segments that are currently intersecting the sweep line, ordered vertically.
It is implemented using a Red-Black Tree to achieve efficient O(log n) for add, remove, and neighbor-finding operations.
func (*Status) FindNeighbors ¶
FindNeighbors finds the segments immediately above and below a given segment in the status tree. It returns `nil` for a neighbor if one does not exist.
Source Files