Polygon in rectangle algorithm?

Question

I have an algorithm which can find if a point is in a given polygon:

 int CGlEngineFunctions::PointInPoly(int npts, float *xp, float *yp, float x, float y)
 {
     int i, j, c = 0;
     for (i = 0, j = npts-1; i < npts; 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;
 }

given this, how could I make it check if its within a rectangle defind by Ptopleft and Pbottomright instead of a single point?

Thanks

Basically you know how in Adobe Illustrator you can drag to select all objects that fall within the selection rectangle? well I mean that. –

Answer 1

Can't you just find the minimum and maximum x and y values among the points of the polygon and check to see if any of the values are outside the rectangle's dimensions?

Answer 2

int isPointInRect( Point point, Point ptopleft, Point pbottomright) {

   float xp[2] ;
   xp[0] = ptopleft.x, 
   xp[1] = pbottomright.x;

   float yp[2] ;
   yp[0] = ptopleft.y ;
   yp[1] = pbottomright.y ;

   return CGlEngineFunctions::PointInPoly(2, xp, yp, point.x, point.y);
}

Answer 3

EDIT: duh, I misinterpreted the question. If you want to ensure that the polygon is encosed by a rectangle, do a check for each polygon point. You can do that more cheaply with the minimum/maximum x and y coordinates and checking if that rectangle is within the query rectangle.

EDIT2: Oops, meant horizontal, not vertical edges.

EDIT3: Oops #2, it does handle horizontal edges by avoiding checking edges that are horizontal. If you cross multiply however, you can avoid the special casing as well.

Answer 4

As mentioned before, for that specific problem, this function is an overkill. However, if you are required to use it, note that:
1. It works only for convex polygons,
2. The arrays holding the polygon's vertices must be sorted such that consecutive points in the array relate to adjacent vertices of your polygon.
3. To work properly, the vertices must be ordered in the "right hand rule" order. That means that when you start "walking" along the edges, you only make left turns.

That said, I think there is an error in the implementation. Instead of:

// c initialized to 0 (false), then...
c = !c;  

you should have something like:

// c initialized to 1 (true), then...
// negate your condition:
if ( ! (....))
    c = 0;