How to get the length of a segment crossing a square?

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 (i开发者_如何学Pythone 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:

1. Compute the intersection of the line with the vertical lines x = a and x = a + 1, and the horizontal lines y = b and y = b + 1
2. Check if 2 of these 4 points are on the square boundaries (ie a <= 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.

---

Your proposed method may meet with problems in step (1) when m is 0 (when trying to compute the intersection with y = k).

if m is 0, then it's easy (the line segment length is either 1 or 0, depending on whether b <= h <= b+1).

Otherwise, you can find the intersections with x = a and a+1, say, y_a, y_{a+1} via a substitution. Then, clip y_a and y_{a+1} to between b and b+1 (say, y1 and y2, i.e. y1 = min(b+1, max(b, y_a)) and similarly for y2), and use the proportion abs((y1-y2)/m) * sqrt(m^2+1).

This makes use of the fact that the line segment between x=k and x=k+1 is sqrt(m^2+1), and the difference in y is m, and similarity.

---

You can do like this: first find center of square and then find length of diagonal. If the distance from center of square to line is less than length of diagonal then the line will intersect the square. and once you know that line will intersect then you can easily find the intersected line segment. I think you are trying to make weight matrix for Algebraic reconstruction technique. I hope this is correct answer. This was my first answer in stack flow. :)