0

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!

skaffman
  • 398,947
  • 96
  • 818
  • 769
Hessa
  • 3
  • 1
  • 2

1 Answers1

0

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.

John R Doner
  • 2,242
  • 8
  • 30
  • 36
  • Finally tried to implement this and having a few problems: When you say " lower left of the squares has coordinates (x1, y1) while the upper left corner has coordinates (x2, y2)" surely that would be x1==x2? If so then (y' = a*x1 + b) == (y'' = a*x2 + b) which doesn't make sense with the method. – Hessa Jan 21 '11 at 02:50
  • Perhaps John R Doner meant two opposite corners? – Zev Eisenberg Jan 28 '14 at 18:51