BBC BASIC Programmers' Reference

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