Math wizardry

[Jim Hurley]

>
>Message: 7
>Date: Fri, 4 Mar 2005 16:45:58 -0500
>From: James Steiner <gregortroll at gmail.com>
>Subject: Re: Math wizardry
>To: How to use Revolution <use-revolution at lists.runrev.com>
>Message-ID: <5ec67432050304134535aa35a9 at mail.gmail.com>
>Content-Type: text/plain; charset=US-ASCII
>
>>  To find out whether the
>>  intersection point lies between the end points of each line you will
>>  need to test whether the distance between the intersection point and
>>  ALL the end points is less than the length  of each line
>>  respectively. (I can't imagine that sentence is clear.)
>
>That's not required, which is good, because the distance function is costly.
>
>First, lets assume the purpose of the function is not only to return
>the intersection of the two *lines* but rather to return the
>intersection of the two *line segments*, and returns a special value
>if the *line segments* do not intersect.

Yes, but to write this new function you still need to be sure the 
point of intersection lies between the end points.

You might consider *two* useful functions (1) a point of intersection 
function and (2) a function to tell if the intersection lies between 
the end points.

For example, an intersection function which allows for any one of 
three different ways of describing the two lines might be:

function intersection p1,p2,p1', p2'
   get the paramcount
   if it is not 4 then
     if it is 2 then
       --Each geographic line is two Run Rev lines of 2 items each
       if the number of lines in p1 is 2 then
         put line 2 of p2 into p2'
         put line 1 of p2 into p1'
         put line 2 of p1 into p2
         put line 1 of p1 into p1
       else
         --Each geographic line is 4 items, i.e. p1 and p2 combined
         if the number of items in p1 is 4 then
           put item 3 to 4 of p2 into p2'
           put item 1 to 2 of p2 into p1'
           put item 3 to 4 of p1 into p2
           put item 1 to 2 of p1 into p1
         end if
       end if
     end if
   end if
   put item 1 of p1 into x1
   put item 2 of p1 into y1
   put item 1 of p2 into x2
   put item 2 of p2 into y2
   put item 1 of p1' into x1'
   put item 2 of p1' into y1'
   put item 1 of p2' into x2'
   put item 2 of p2' into y2'

   if x1=x2 and x1'=x2' then add .0001 to x1--Two vertical lines
   --The above will return something like: 200,121999738

   if x2'<> x1' then
     put (y2'-y1')/(x2'-x1') into m'
     put y1' -m'*x1' into b'
   end if

   if x1 <> x2 then
     put (y2-y1)/(x2-x1) into m
     put y1 -m*x1 into b
   end if

   if x1 = x2 then return x1,m'*x1 + b'
   if x1'= x2' then return x2',m*x2' + b
   if m = m' then add .0001 to m--Or whatever
   return  (b'-b)/(m-m'),(m*b'-m'*b)/(m-m')

end intersection

(You may wish to treat the special case of parallel lines 
differently. In most game applications and simulations, you don't 
want to stop execution when the lines are parallel. Best to let the 
intersection point be at some great distance. )

And:

function betweenEndPointsOfLine  pt, tLine
   put line 1 of tLine into p1
   put  line 2 of tLine into p2
   put dist(pt,p1) into s1
   put dist(pt,p2) into s2
   put dist(p1,p2) into s
   if s1<s and s2< s then
     return true
     else return false
end betweenEndPointsOfLine


>
>First, lets assume the purpose of the function is not only to return
>the intersection of the two *lines* but rather to return the
>intersection of the two *line segments*, and returns a special value
>if the *line segments* do not intersect.
>
>Then, given the three points on a line (and we know that the
>calculated intersection point is on the lines, if Ax is between Bx and
>Cx and Ay is between By and Cy, then point A must be between points B
>and C.


Yes, this is quite true.

>
>Also, as a side note, sometimes, like when comparing distances, it's
>OK to use a partial calculation, rather than the complete distance
>calculation. For example, if distance A is equal to distance B, then
>it is true that A^2 is equal to B^2. So, rather that performing the
>full distance calculation: sqrt ( ( x1 - x2) + (y1 - y2) ) , you can
>leave off the sqrt, and compare the partial result, which is really
>the sqaure of the distance, saving some calculation time (sqrt is a
>much more expensive function than multiplication). In applications
>(like games or physics-based simulations) where many of these
>calculations are occuring every second, the saved time can be used for
>other things.

Good point. [ I'm sure you meant  sqrt((x1-x2)^2 + (y1-y2)^2)]

Jim



-