Alternative to PtInRegion() for Hit-Testing

• Microsoft Windows Software Development Kit (SDK) for Windows versions 3.1 and 3.0
• Microsoft Win32 Application Programming Interface (API) included with:

      - Microsoft Windows NT versions 3.1, 3.5, and 3.51
      - Microsoft Windows 95 version 4.0
  

SUMMARY

It may be useful to perform hit-testing on an object that is defined by a polygon. To accomplish this, you could call CreatePolygonRgn() to create a region from the polygon, and then call PtInRegion() to determine if the point falls within the region. However, this method can be expensive both in terms of GDI resources, and in terms of speed. If a polygon is complex, CreatePolygonRgn() will often fail due to lack of memory in Windows because regions are in GDI's heap.

The code below provides a better method. Use it to determine if a point lies within a polygon. It is fast and does not use regions. The trick lies in determining the number of times an imaginary line drawn from the point you want to test crosses edges of your polygon. If the line crosses edges an even number of times, the point is outside the polygon. If it crosses an odd number of times it is inside. The line is drawn horizontally from the point to the right.

MORE INFORMATION

WARNING: ANY USE BY YOU OF THE CODE PROVIDED IN THIS ARTICLE IS AT YOUR OWN RISK. Microsoft provides this code "as is" without warranty of any kind, either express or implied, including but not limited to the implied warranties of merchantability and/or fitness for a particular purpose. The references below do not constitute a recommendation. You are encouraged to examine any resource to determine whether or not it meets your needs. These books are not recommended over any others.

The following code is based on an algorithm presented in "Algorithms" by Robert Sedgewick, Addison-Wesley, 1988, 2nd ed. ISBN 0201066734. The algorithm is on p.354, in the section "Inclusion in a Polygon" in the chapter "Elementary Geometric Methods." It is also discussed in "Computer Graphics" by Foley, van Dam, Feiner and Hughes, Addison-Wesley, 1990, 2nd ed. ISBN 0201121107, chapter 2, section 1, p.34.

Sample Code

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

                   RECT *prbound) ;

                    RECT *prbound) ;

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.
 *************************************************************************/

                   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.
 *************************************************************************/

                     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.
 *************************************************************************/

   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 */