SweepLine

Jin Shang bio photo By Jin Shang

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