Implement line sweep algorithms
- Dominant language
- Hy
- Stars
- 2
- Forks
- 0
- PR merge metrics
- No merged PRs in 30d
Description
Create implementations for line sweep (sweep line) algorithm techniques:
## Basic line sweep problems:
- Find all intersections of line segments
- Closest pair of points
- Rectangle area union
- Rectangle intersection
- Point in polygon
- Maximal points
## Applications:
- Geometric problems
- Event scheduling
- Range queries
- Computational geometry
- Voronoi diagrams
## Data structures for sweep line:
- Event queue
- Status structure
- Balanced binary search tree
## Requirements:
- Provide detailed complexity analysis
- Include visualization helpers
- Create comprehensive test cases
- Document practical applications
This collection will demonstrate the powerful line sweep technique for efficiently solving geometric and interval-based problems by transforming complex 2D problems into 1D problems that can be solved incrementally.
Contributor guide
Assessment
This issue has not been assessed yet.