geometry - Intersection of line and square in JAVA

Question

JAVA:

I'm working on a grid where the centre point of each square is an integer co-ordinate and I'm drawing a line between two integers and need to check whether it goes through a specific grid square based around integer coordinates.

I've seen similar posts/google results but mine's a lot more basic so I'm wondering whether there's a simple solution I can't grasp. (Most probable)

Appreciate any help you can give!

Answer 1

I think you are asking if one specific line intersects one specific square (if that problem is solved, it applies to any number of squares).

Try this. Say the line has equation y = a*x + b, and the lower left of the squares has coordinates (x1, y1) while the upper left corner has coordinates (x2, y2).

Find the points y' = a*x1 + b, y'' = a*x2 + b ("*" for multiply);

then depending on whether y' > y'' or vice versa, you have an intervals [y', y''] or [y'', y'], say for argument that the interval is [y', y''].

(In math notation, [m, n] stands for all numbers >= m, and <= n.)

If [y', y''] intersects [y1, y2], the line enters the square.