Hidden Surface Removal Algorithm

Source code: lines.cpp

Various universities present computer science students with a hidden surface removal problem; perhaps better described as 2d occlusion culling. A variation of the problem may read something like this:

We say a line is uppermost at a given x-coordinate if it's y-coordinate at x is greater than all the other lines. Inuitively, a line is visible if at least some portion of it can be seen if you look down from y = ∞. You can assume that there are no points where three or more lines intersect, there are no vertical lines, and no two lines are parallel.

The optimal solution is an O(n log n) divide and conquer algorithm. My specific implementation uses a Line structure that tracks the range over x which its visible. If a line's interval completely overlaps another line, then the other line cannot be visible.