jwalsh / jwalsh/hy-algorithms

Implement line sweep algorithms

Open
#29 0 comments 0 reactions 0 assignees View on GitHub
difficulty:hard math
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.