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