Results 1 to 3 of 3
Like Tree2Thanks
  • 1 Post By SlipEternal
  • 1 Post By SGS

Thread: Determine if Line passes through Squares

  1. #1
    Newbie
    Joined
    Jul 2017
    From
    Barcelona
    Posts
    1

    Determine if Line passes through Squares

    Dear all, I'd like to know if there is a common approach to this problem:


    I have a line segment defined by points a and b over a 2D plane. That plane is divided in Squares of the same size. I need to find a list of all the squares which the "ab" segment passes through.




    I know:

    • Points a and b coordinates
    • The size and position of the Squares
    • The Line Equation for ab (the Slope and the Y-Intercept)


    I know I can pick any X value and calculate its Y intercept on the ab segment, and there for say if that point is inside a square or not, but this aproach may involve iterating and unwanted CPU computing (given I want to implement this concept into a computer graphics experiment).


    Thanks in advance for any tip!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,014
    Thanks
    1152

    Re: Determine if Line passes through Squares

    Does any square in the plane have (0,0) as a vertex? Are points a and b both vertices of some squares in the plane? If the latter question is true then the former question is moot.
    Thanks from Particlerama
    Follow Math Help Forum on Facebook and Google+

  3. #3
    SGS
    SGS is offline
    Junior Member
    Joined
    Mar 2015
    From
    Clarion, PA
    Posts
    31
    Thanks
    6

    Re: Determine if Line passes through Squares

    Quote Originally Posted by Particlerama View Post
    Dear all, I'd like to know if there is a common approach to this problem:


    I have a line segment defined by points a and b over a 2D plane. That plane is divided in Squares of the same size. I need to find a list of all the squares which the "ab" segment passes through.




    I know:

    • Points a and b coordinates
    • The size and position of the Squares
    • The Line Equation for ab (the Slope and the Y-Intercept)


    I know I can pick any X value and calculate its Y intercept on the ab segment, and there for say if that point is inside a square or not, but this aproach may involve iterating and unwanted CPU computing (given I want to implement this concept into a computer graphics experiment).


    Thanks in advance for any tip!!
    From observation of your sketch ....

    1. The line starts at the top left of the plane and ends at the bottom right of the plane
    2. The first and last rows of the plane contain two adjacent squares where the line passes through. For the rows in-between, the line passes through three squares.
    3. In your sketch, in the second row the adjacent boxes are 1 column to the right of the left edge of the plane. The third row is 3 columns over, the fourth is 5 columns over, the fifth is 7 and the sixth is 9. (Do you see the pattern?)
    4. Given H and W of the plane, the slope of the line is H/W.
    5. Given the size of the squares, the number of vertical squares is H/(Size) and the number of horizontal squares is W/(Size).

    The above observations are all dependent on H and W. You need to create a set of simultaneous equations for the above observations where the solution to the equations identify the names of the squares that the line passes through.

    Steve
    Thanks from Particlerama
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Equation of a line that passes through a point.
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: May 22nd 2011, 12:48 PM
  2. Show that line passes through a point
    Posted in the Geometry Forum
    Replies: 12
    Last Post: May 2nd 2010, 05:55 PM
  3. Replies: 1
    Last Post: May 22nd 2009, 01:10 PM
  4. Replies: 9
    Last Post: Aug 11th 2008, 08:03 AM
  5. graph of a point that passes through a line
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: Feb 18th 2008, 03:07 AM

/mathhelpforum @mathhelpforum