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.