>>You could always try using the old grade 10 math:
>>1.  Find the equation of the line in the form y#=m(x-x1)+y1, where m is the
>>slope of the line and (x1,y1) is a known point on the line.
>>2.  Find the coordinates of the four corners of the rectangle.
>>3.  Sub each corner into the equation, one at a time, and check if the LS
>>is >,<, or = to the right side.  Keep track of the results.
>>4.  The line intersects the rectangle if you get an = result or if you get
>>both a < and > result for different points.
>>This would take a little bit of work to code, but it may be faster than
>>working with regions.  Be sure to express the m value in step 1 as an
>>integer in the form a/b so that you are using integer math most of the time
>>and don't slow down the calculations.  You will have to express the y-value
>>as a float, preferably using SANE for speed.
<snip>
>Wave:
>
<snip>

>The
>solution you describe would require a calculation for every x and y along a
>line AND then a check to see if each point is within the box. Talk about
>slow! Believe me, toolbox functions are designed for these types of
>calculations.
>
>I'll make you a bet that the solution you propose would be an order of
>magnitude slower than a toolbox solution. So, write your solution and then
>I'll write mine.
>
>:-)
>
>tedd


Tedd,
Seems to me you would only be sticking in the four corners of the rectangle
into the line equation using the above approach. That would only be 4 or
more calculations, not one for every point on the line.


Don't know if this will help, but here it is.

Robert Covington

From the <comp.graphics.algorithms> FAQ maintained by Joseph O'Rourke:


--------------------------
Subject 2.03: How do I find if a point lies within a polygon?

    The definitive reference is "Point in Polyon Strategies" by
    Eric Haines [Gems IV]  pp. 24-46.
    The code in the Sedgewick book Algorithms (2nd Edition, p.354) is
    incorrect.

    The essence of the ray-crossing method is as follows.
    Think of standing inside a field with a fence representing the polygon.
    Then walk north. If you have to jump the fence you know you are now
    outside the poly. If you have to cross again you know you are now
    inside again; i.e., if you were inside the field to start with, the total
    number of fence jumps you would make will be odd, whereas if you were
    ouside the jumps will be even.

    The code below is from Wm. Randolph Franklin <wrf@...>
    with some minor modifications for speed.  It returns 1 for strictly
    interior points, 0 for strictly exterior, and 0 or 1 for points on
    the boundary.  The boundary behavior is complex but determined;
    in particular, for a partition of a region into polygons, each point
    is "in" exactly one polygon.  See the references below for more detail.

    int pnpoly(int npol, float *xp, float *yp, float x, float y)
    {
      int i, j, c = 0;
      for (i = 0, j = npol-1; i < npol; j = i++) {
        if ((((yp[i]<=y) && (y<yp[j])) ||
             ((yp[j]<=y) && (y<yp[i]))) &&
            (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))

          c = !c;
      }
      return c;
    }

    The code may be further accelerated, at some loss in clarity, by
    avoiding the central computation when the inequality can be deduced,
    and by replacing the division by a multiplication for those processors
    with slow divides.

    References:
    [Gems IV]  pp. 24-46
    [O'Rourke (C)] pp. 233-238
    [Glassner:RayTracing]