Distance Formula

 BBS: Inland Empire Archive
Date: 06-21-92 (15:35)             Number: 1263
From: RICK PEDLEY                  Refer#: NONE
  To: ROBERT CHURCH                 Recvd: NO  
Subj: Distance Formula               Conf: (2) Quik_Bas

 On 06-20-92 Robert Church wrote to All...

 RC> I need some help with a little math.  For a game I'm writing, I need
 RC> to
 RC> not only find the distance between two points on a grid, but to find
 RC> the POINTS on the grid.
 RC>
 RC>    In short, How can I find all of the points between two points on
 RC>    a grid?

If it's a rectangular grid, then the distance between two points
is the hypotenuse of a right-angled triangle:


    (x ,y ) .
      1  1   \
              \
               \
                \
                 \
                  . (x ,y )
                      2  2

distance = square root ((y -y )^2 + (x -x )^2), or in BASIC:
                          2  1        2  1

Distance! = SQR((Y2 - Y1)^2 + (X2 - X1)^2))

Distance! will often be a decimal fraction, even if your end points
are whole numbers -- (1,4) and (4,1) for example are SQR(18) apart.

Your second question is a little trickier. There is an infinite
number of points on a continuous line segment. Are you looking only
for points that have integer coordinates? In many cases there won't
be =any= points that meet this requirement except possibly the end-
points -- a few minutes with a piece of graph paper will show you that.
But assuming you want integer-valued points between any two points
(which we'll assume are also integers), and that the line is horizontal,
perpendicular or at 45 degrees, here's what to do:


Find the slope of the line:

m! = (Y2 - Y1) / (X2 - X1)  'Trap for X2 = X1 -- if they are equal
                             then the equation of the line is just
                             x = X1 or x = X2.

If m! = 0 then the points on the line are simply (X1,Y1),(X1+1,Y1),...,
(X2,Y1)

If X1 = X2 then the points are (X1,Y1),(X1,Y1-1),...(X1,Y2)

If m! = 1 or -1, the line is at 45 degrees (/ or \), and you can
determine the points by running through nested FOR..NEXT loops.
For example, if (X1,Y1) = (0,0) and (X2,Y2) = (5,5), you know
the coordinates will be (0,0), (1,1), (2,2), etc.

If the slope isn't 1, -1, 0, or undetermined (vertical), then you'll
have to determine the equation of the line, and run through the last
step above, testing each pair of integer coordinates to see whether
they fit the equation, and as I mentioned, there may be =no=
points that fit. If possible therefore, stick to those 8 directions
of movement: up, down, left, right, and the four diagonal directions.


... OFFLINE 1.37

--- Maximus 2.01wb
 * Origin: The BULLpen BBS * Intel 14.4EX (613)549-5168 (1:249/140)