PtInRegion() API 대체 방법

<참고> http://support.microsoft.com/kb/121960/ko
           http://support.microsoft.com/kb/121960/en-us

다각형 안에 포인트가 있는지 확인하기 위해서 일반적으로 사용하는 GDI API입니다.

예를 들어 CreatePolygonRgn() 호출하고 PtInRegion() 함수로 포인트가 지역 내에 있는지 여부를 확인 합니다.

다각형이 복잡한 경우에 CreatePolygonRgn() 함수는 GDI의 힙 영역에서 사용하기 때문에 종종 메모리 부족 에러를 발생시킵니다. 또한 위의 API들은 속도가 떨어집니다. 따라서 성능에 크게 영향을 미칩니다. 기존에 개발해서 사용한 함수도 다각형이 작을 때는 크게 상관이 없지만 점의 개수가 많아 커질 경우에 몇초 이상의 속도저하가 발생하는 것을 확인 할 수 있었습니다.

아래 방법은 점이 다각형 내에 있는지 확인하기 위해서 사용됩니다. 영역을 사용하지 않기 때문에 성능저하가 기존 방식보다 적게 발생합니다. 

It may be useful to perform hit-testing on an object that is defined by a polygon. To accomplish this, you could callCreatePolygonRgn() 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.

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.

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