Suppose we have an rectangular area with corner points P1 to P8. The four corner points around each square (Q1-Q3) are forming a plain. The corner points have different heights (see first image).
Lets say we want to draw a straight line from P8 to all other corner points. How can we check whether or not the line will go through to the corner points (like the orange lines in the second image) or not (like the red lines in the second image).
My idea: The lines between P8 and P7, P3 and P4 are trivial. For the line between P8 and P2 we can calculate the height of the trapezoid between points P7 and P3. P7 has height 0, P3 has height 3, the trapezoid will have height 1.5 right in the middle. The line from P8 to P2 will go over the trapezoid right in the middle, so that works.
My problem is with lines like P8 and P1. The trapezoid between P6 and P2 has a height of 2.5 (in the middle). However, the line from P8 to P1 won't go over the middle, it will be closer to P2. How can we determine whether the line will go through or over the trapezoid?
The test is really the same for all of the edge crossings, though it might not look that way because part of the calculation is particularly simple when you’re sighting along one of the outer edges.
Basically, you’re testing whether or not the line segment between one pair of vertices, call it $L$, is above or below the line segment between another pair, call it $M$, at the point at which $L$ crosses the vertical plane in which $M$ lies. The altitudes of the line segments vary in proportion to the distance along the segment, so you just need to find the correct proportions.
You’ve already used this idea when you computed the $L=P_8P_2$ and $M=P_7P_3$ crossing. The latter segment is horizontally halfway between the endpoints of $L$, so the crossing occurs at the midpoints of $L$ and $M$: the heights of the two line segments are then also midway between the heights at the endpoints.
Applying the same reasoning to $L=P_8P_2$ and $M=P_7P_3$, assuming that the points are evenly spaced along the edge, the crossing occurs a third of the way horizontally between $P_8$ and $P_2$. All of the other distances will be in the same proportion. In particular, the crossing is also a third of the way from $P_7$ to $P_3$, so if we let the height at point $P$ be denoted by $z(P)$, the two heights at the crossing are $$z(P_8)+\frac13\left[z(P_2)-z(P_8)\right] = \frac23 z(P_8)+\frac13 z(P_2) = 1$$ and $$z(P_7)+\frac13\left[z(P_3)-z(P_7)\right] = \frac23 z(P_7)+ \frac13 z(P_3) = 1$$ so $L$ just grazes the top of the wall along $M$. The other crossing can be computed in a similar way, as can the crossings of the other diagonal. Be careful to get the endpoints of the two line segments being tested in the same order. (Underlying all of these calculations are a bunch of similar triangles.)
More generally, you can represent the line segment between points $A$ and $B$ as $(1-\lambda)A+\lambda B$, $0\le\lambda\le1$. The parameter $\lambda$ is the fraction of the distance from $A$ to $B$. Given two such line segments, you can plug in their $x$- and $y$-coordinates to get a system of two linear equations in the parameters, which you can solve using a number of well-known methods. (Cramer’s rule is handy here.) The heights at their crossings can then be computed using the resulting two fractions.