point-in-polygon_20hit_20testing

*by Richard Russell, September 2010*

A common requirement in graphics programming is to determine whether a point is inside or outside a polygon (which can be regular or irregular, concave or convex). Since any closed curve can be approximated by a polygon, given a sufficient number of vertices, this can be extended to testing whether a point is inside or outside an arbitrary boundary.

One approach is to use the **Windows API**. The polygon can be converted to a *region* using the **CreatePolygonRgn** API and the hit test then carried out using the **PtInRegion** API; however this is a relatively slow operation. This article presents an alternative method using an assembly language routine to perform the test directly.

To use this method the code must first be assembled, during the initialisation phase of your program, by calling **PROCassemblepip** as follows:

` PROCassemblepip`

Once that has been done the test can be carried out simply by making the following **SYS** call:

SYS `PtInPoly`, pt{(0)}, nvert%, x%, y% TO res%

This is directly equivalent to (but much faster than) this code using the Windows API:

SYS "CreatePolygonRgn", pt{(0)}, nvert%, 1 TO hrgn% SYS "PtInRegion", hrgn%, x%, y% TO res% SYS "DeleteObject", hrgn%

In both cases **pt{()}** is an array of POINT structures containing the vertices of the polygon, **nvert%** is the total number of vertices in the polygon and **x%,y%** defines the point to be tested. The returned value **res%** is set non-zero if the point is inside the polygon and zero if it is outside.

The array of POINT structures can typically be created as follows (in this case for a hexagon):

nvert% = 6 DIM pt{(nvert%-1) x%,y%} Once created the vertices should be initialised with the appropriate coordinates, for example:\\ FOR V% = 0 TO nvert%-1 READ pt{(V%)}.x%, pt{(V%)}.y% NEXT

Here the coordinates are assumed to be contained within DATA statements.

Finally, here is the code of **PROCassemblepip**:

DEF PROCassemblepip LOCAL L%, P%, code%, pass% DIM code% 120, L% -1 FOR pass% = 8 TO 10 STEP 2 P% = code% [OPT pass% .`PtInPoly` mov edi,[esp+4] ; lpPoints mov ecx,[esp+8] ; nCount mov ebx,[esp+12] ; X mov ebp,[esp+16] ; Y mov esi,edi xor eax,eax dec ecx .piploop pushad mov ecx,[edi] mov edx,[edi+4] mov esi,[edi+8] mov edi,[edi+12] call intersect xor [esp+28],eax popad add edi,8 loop piploop pushad mov ecx,[edi] mov edx,[edi+4] mov edi,[esi+4] mov esi,[esi] call intersect xor [esp+28],eax popad ret 16 .intersect cmp edx,ebp ; y1 > y0 ? setg al cmp edi,ebp ; y2 > y0 ? setg ah xor al,ah ; eor jz bailout cmp edx,edi ; y1 > y2 ? setg al sub esi,ecx ; dx0 = x2 - x1 sub edi,edx ; dy0 = y2 - y1 sub ebx,ecx ; dx2 = x0 - x1 sub ebp,edx ; dy2 = y0 - y1 imul esi,ebp ; dx0 * dy2 imul edi,ebx ; dy0 * dx2 cmp esi,edi ; > ? setg ah xor al,ah ; eor .bailout movzx eax,al ret ] NEXT pass% ENDPROC

This website uses cookies for visitor traffic analysis. By using the website, you agree with storing the cookies on your computer.More information

point-in-polygon_20hit_20testing.txt · Last modified: 2018/04/13 15:53 by richardrussell

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International