I have a line, defined by the parameters m, h, where
y = m*x + h
This line goes across a grid (i.e. pixels). For each square (a, b) of the grid (ie the square [a, a+1] x [b, b+1]), I want to determine if the given line crosses this square or not, and if so, what is the length of the segment in the square.
Eventually, I would like to be able to do this with multiple lines at once (ie m and h are vectors, matlab-style), but we can focus on the "simple" case for now.
I figured how to determine if the line crosses the square:
x = a and x = a + 1, and the horizontal lines y = b and y = b + 1a <= x < a + 1 and b <= y < b + 1)If two on these points are on the square, the line crosses it. Then, to compute the length, you simply subtract the two points, and use Pythagorean theorem.
My problem is more on the implementation side: how can I implement that nicely (especially when selecting which 2 points to subtract) ?
Let square be defined by corner points (a,b), (a+1,b), (a,b+1), (a+1,b+1).
Step 1: Check if the line intersects the square...
(a)Substitute each of the coordinates of the 4 corner points, in turn into y - mx - h. If the sign of this evaluation includes both positive and negative terms, go to step b. Otherwise, the line does not intersect the square.
(b)Now there are two sub-cases:
(b1)Case 1: In step (a) you had three points for which y - mx - h evaluated to one sign and the fourth point evaluated to the other sign. Let this 4th point be some (x*,y*). Then the points of intersection are (x*,mx*+h) and ((y*-h)/m,y*).
(b2)Case 2: In step (a) you had two points for which y - mx - h evaluate to one sign and the other two points evaluated to the other sign. Pick any two points that evaluated to the same sign, say (x*,y*) and (x*+1, y*). Then the intersection points are (x*, mx* + h) and (x*+1,m(x*+1) + h).
You would have to consider some degenerate cases where the line touches exactly one of the four corner points and the case where the line lies exactly on one side of the square.