INFO: Alternative to PtInRegion() for Hit-Testing

MORE INFORMATION

Sample Code

   #include "windows.h"
   #include "limits.h"

   BOOL G_PtInPolygon(POINT *rgpts, WORD wnumpts, POINT ptTest,

                   RECT *prbound) ;

   BOOL G_PtInPolyRect(POINT *rgpts, WORD wnumpts, POINT ptTest,

                    RECT *prbound) ;
 
   BOOL Intersect(POINT p1, POINT p2, POINT p3, POINT p4) ;

   int  CCW(POINT p0, POINT p1, POINT p2) ;

 /*************************************************************************

   * FUNCTION:   G_PtInPolygon
   *
   * PURPOSE
   * This routine determines if the point passed is in the polygon. It uses

   * the classical polygon hit-testing algorithm: a horizontal ray starting

   * at the point is extended infinitely rightwards and the number of
  * polygon edges that intersect the ray are counted. If the number is odd,

   * the point is inside the polygon.
   *
   * RETURN VALUE
   * (BOOL) TRUE if the point is inside the polygon, FALSE if not.
 *************************************************************************/ 

  BOOL G_PtInPolygon(POINT *rgpts, WORD wnumpts, POINT ptTest,

                   RECT *prbound)

  {

   RECT   r ;
   POINT  *ppt ;
   WORD   i ;
   POINT  pt1, pt2 ;
   WORD   wnumintsct = 0 ;

   if (!G_PtInPolyRect(rgpts,wnumpts,ptTest,prbound))

   return FALSE ;

   pt1 = pt2 = ptTest ;
   pt2.x = r.right + 50 ;

   // Now go through each of the lines in the polygon and see if it
   // intersects
   for (i = 0, ppt = rgpts ; i < wnumpts-1 ; i++, ppt++)
   {
      if (Intersect(ptTest, pt2, *ppt, *(ppt+1)))
         wnumintsct++ ;
   }

   // And the last line
   if (Intersect(ptTest, pt2, *ppt, *rgpts))
      wnumintsct++ ;

   return (wnumintsct&1) ;

   }

/*************************************************************************

   * FUNCTION:   G_PtInPolyRect
   *
   * PURPOSE
   * This routine determines if a point is within the smallest rectangle
   * that encloses a polygon.
   *
   * RETURN VALUE
   * (BOOL) TRUE or FALSE depending on whether the point is in the rect or

   * not.
 *************************************************************************/ 

  BOOL  G_PtInPolyRect(POINT *rgpts, WORD wnumpts, POINT ptTest,

                     RECT *prbound)

   {

   RECT r ;
   // If a bounding rect has not been passed in, calculate it
   if (prbound)

   r = *prbound ;

   else
   {

      int   xmin, xmax, ymin, ymax ;
      POINT *ppt ;
      WORD  i ;

      xmin = ymin = INT_MAX ;
      xmax = ymax = -INT_MAX ;

      for (i=0, ppt = rgpts ; i < wnumpts ; i++, ppt++)
      {
         if (ppt->x < xmin)
            xmin = ppt->x ;
         if (ppt->x > xmax)
            xmax = ppt->x ;
         if (ppt->y < ymin)
            ymin = ppt->y ;
         if (ppt->y > ymax)
            ymax = ppt->y ;
      }
      SetRect(&r, xmin, ymin, xmax, ymax) ;

   }
   return (PtInRect(&r,ptTest)) ;

   }

/*************************************************************************
   * FUNCTION:   Intersect
   *
   * PURPOSE
   * Given two line segments, determine if they intersect.
   *
   * RETURN VALUE
   * TRUE if they intersect, FALSE if not.
 *************************************************************************/ 

  BOOL Intersect(POINT p1, POINT p2, POINT p3, POINT p4)
  {

   return ((( CCW(p1, p2, p3) * CCW(p1, p2, p4)) <= 0)

        && (( CCW(p3, p4, p1) * CCW(p3, p4, p2)  <= 0) )) ;

   }

/*************************************************************************

   * FUNCTION:   CCW (CounterClockWise)
   *
   * PURPOSE
   * Determines, given three points, if when travelling from the first to
   * the second to the third, we travel in a counterclockwise direction.
   *
   * RETURN VALUE
   * (int) 1 if the movement is in a counterclockwise direction, -1 if
   * not.
 *************************************************************************/ 

  int CCW(POINT p0, POINT p1, POINT p2)

   {

   LONG dx1, dx2 ;
   LONG dy1, dy2 ;

   dx1 = p1.x - p0.x ; dx2 = p2.x - p0.x ;
   dy1 = p1.y - p0.y ; dy2 = p2.y - p0.y ;

   /* This is basically a slope comparison: we don't do divisions because

    * of divide by zero possibilities with pure horizontal and pure
    * vertical lines.
    */ 

   return ((dx1 * dy2 > dy1 * dx2) ? 1 : -1) ;

   }

   /*************************************************

   * The above code might be tested as follows:
   *************************************************/ 

   void PASCAL TestProc( HWND hWnd )

   {

    POINT rgpts[] = {0,0, 10,0, 10,10, 5,15, 0,10};
    WORD wnumpts = 5;
    POINT ptTest = {3,10};
    RECT prbound = {0, 0, 20, 20};
    BOOL bInside;

    bInside = G_PtInPolygon(rgpts, wnumpts, ptTest, &prbound);

    if (bInside)
       MessageBox(hWnd, "Point is inside!", "Test", MB_OK );
    else
       MessageBox(hWnd, "Point is outside!", "Test", MB_OK );

   }

   /* code ends */