# Hidden Surface Removal

*June 2018*

**Download link: Click here**

There's a common problem in computer science known as hidden surface removal, essentially 2d occlusion culling. The solution is a divide and conquer algorithm
which runs in O(n logn). The problem goes 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.*

This problem comes with a few different flavors, so here are a list of a few:

My solution is a modified merge sort which gives a Line two extra variables, the range of x over which the line is visible. When a line intersects, then the left or right bound is decreased. If a line's interval completely overlaps another line, then the other line cannot be visible. Lines that aren't visible are "decreased" in the merge sort.