# SweepLine

SweepLine algorithm for finding all intersections

sweepLineIntersection(Points[0..2n-1]):
1. Sort Points[] from left to right (according to x coordinate) (priority_queue)

2. Create an empty Self-Balancing BST T. It will contain all active line
Segments ordered by y coordinate. (map)

// Process all 2n points
3. for i = 0 to 2n-1
pq.pop()
// If this point is left end of its line
if (Points[i].isLeft)
T.insert(Points[i].line())  // Insert into the tree

// Check if this points intersects with its predecessor and successor
if ( doIntersect(Points[i].line(), T.pred(Points[i].line()) )
return true
if ( doIntersect(Points[i].line(), T.succ(Points[i].line()) )
return true

else  // If it's a right end of its line
// Check if its predecessor and successor intersect with each other
if ( doIntersect(T.pred(Points[i].line(), T.succ(Points[i].line()))
return true
T.delete(Points[i].line())  // Delete from tree

4. return False