Checking a point inside a polygon

[Farabi]

lol - that man is Farabi   :eek
give me some time to look at the code......

that is some monster code - lol
for the polygram, you have a set of lines - a list ? with end-points ?

Yes a set of lines with end points

[Farabi]

oh my fo!
this man looks like a terrorist!

*ahem*

[dedndave]

i think i understand what is going on

they merely count X's below Xmouse and X's above Xmouse to determine odd nodes
that makes sense
i will look at your code again tomorrow Farabi

[dedndave]

the list is a set of points - not lines

here is what you may have:


line1     dd      x1a,y1a,x1b,y1b
line2     dd      x2a,y2a,x2b,y2b
line3     dd      x3a,y3a,x3b,y3b
.
.


the point x1b,y1b must be the same as x2a,y2a
(the end of one line is the start of the next)

the routine wants a point list, rather than a line list, as the end-points may be removed


point1   dd      x1a,y1a ; (x1b,y1b) = (x2a,y2a)
point2   dd      x2a,y2a ; (x2b,y2b) = (x3a,y3a)
point3   dd      x3a,y3a ; (x3b,y3b) = (x4a,y4a)
.
.
.


so, the list is a set of corner points for the polygon, rather than lines
also, PolySides is the number of corner points (or sides) of the polygon

[dedndave]

        mov     esi,lpPoints

should be

        mov     esi,offset lpPoints


i translated the code to assembler (lol)
if you want your code to look like C, write in C
here, we speak assembler
it doesn't go sideways - it goes down
train your brain to think like a CPU


IsInsidePolygon proc uses esi edi x:dword,y:dword,lpPoints:dword,nPointCounts:dword

        LOCAL   i,j:dword
        LOCAL   oddNodes,logic:dword

        push    nPointCounts
        pop     j
        dec     j
        mov     esi,offset lpPoints
        xor     eax,eax
        mov     i,eax
        mov     oddNodes,eax

loop_i: mov     eax,i
        shl     eax,3
        mov     ecx,[esi+eax].POINT.y
        cmp     ecx,y
        jnl     pol_i

        mov     eax,j
        shl     eax,3
        mov     ecx,[esi+eax].POINT.y
        cmp     ecx,y
        jb      pol_i

        mov     eax,j
        shl     eax,3
        mov     ecx,[esi+eax].POINT.y
        cmp     ecx,y
        jnl     pol_i

        mov     eax,i
        shl     eax,3
        mov     ecx,[esi+eax].POINT.y
        cmp     ecx,y
        jb      pol_i

        mov     eax,j
        shl     eax,3
        mov     ecx,[esi+eax].POINT.x
        mov     eax,i
        shl     eax,3
        sub     ecx,[esi+eax].POINT.x
        push    ecx
        mov     eax,j
        shl     eax,3
        mov     ecx,[esi+eax].POINT.y
        mov     eax,i
        shl     eax,3
        sub     ecx,[esi+eax].POINT.y
        xchg    eax,ecx
        mul dword ptr [esp]
        pop     ecx
        push    eax
        push    y
        mov     eax,i
        shl     eax,3
        mov     ecx,[esi+eax].POINT.y
        sub     [esp],ecx
        mov     eax,i
        shl     eax,3
        mov     ecx,[esi+eax].POINT.x
        add     [esp],ecx
        pop     eax
        xor     edx,edx
        div dword ptr [esp]
        pop     ecx
        mov     ecx,x
        cmp     eax,ecx
        jnl     pol_i

        not     oddNodes

pol_i:  push    i
        pop     j
        inc     i
        mov     eax,nPointCounts
        cmp     i,eax
        jl      loop_i
   
        mov     eax,oddNodes
        ret

IsInsidePolygon endp

[Farabi]

Ded:
I re-read the code and not tested your code yet

I think the 1st problem is on this code (polyY<y && polyY[j]>=y ||  polyY[j]<y && polyY>=y) .  This part can be TRUE or FALSE polyY<y && polyY[j]>=y so do this part polyY[j]<y && polyY>=y, and on my code both should be true if you dont want to jump to the end code thats why its not working. I will try it again tommorow, its late in here now, time to read some article in here before go to sleep, not the time to think.

[dedndave]

        mov     esi,lpPoints

should be

        mov     esi,offset lpPoints

[Farabi]

        mov     esi,lpPoints

should be

        mov     esi,offset lpPoints

No it think it should not. offset lpPoints will return the ESP address if Im not mistaken, it should be just mov esi,lpPoints.

[dedndave]

if lpPoints looks like this, it is ok...

PointList  dd ?,?
             dd ?,?
.
.
.

lpPoints dd PointList


but - could just be mov esi,offset PointList

[Farabi]

Almost work but div instruction causing memory leak.

Code Select Expand


IsInsidePolygon proc uses esi edi x:dword,y:dword,lpPoints:dword,nPointCounts:dword
LOCAL i,j:dword
LOCAL oddNodes,logic,logic2,logic3,logic4:dword
; bool pointInPolygon() {
;
; int      i, j=polySides-1 ;
  ;boolean  oddNodes=NO      ;
;
;  for (i=0; i<polySides; i++) {
;    if (polyY[i]<y && polyY[j]>=y
;    ||  polyY[j]<y && polyY[i]>=y) {
;      if (polyX[i]+(y-polyY[i])/(polyY[j]-polyY[i])*(polyX[j]-polyX[i])<x) {
;        oddNodes=!oddNodes; }}
;    j=i; }
;  return oddNodes; }

push nPointCounts
pop j
dec j

mov esi,lpPoints

xor eax,eax
mov i,eax
mov oddNodes,eax
loop_i:
xor eax,eax
mov logic,eax
mov logic2,eax
mov logic3,eax
mov logic4,eax

mov eax,i
shl eax,3
mov ecx,[esi+eax].POINT.y ; polyY[i]<y
cmp ecx,y
jnl logic1_not_set
mov logic,1
logic1_not_set:
mov eax,j
shl eax,3
mov ecx,[esi+eax].POINT.y ; polyY[j]>=y
cmp ecx,y
jnae logic2_not_set
mov logic2,1
logic2_not_set:
mov eax,j
shl eax,3
mov ecx,[esi+eax].POINT.y ;polyY[j]<y
cmp ecx,y
jnl logic3_not_set
mov logic3,1
logic3_not_set:
mov eax,i
shl eax,3
mov ecx,[esi+eax].POINT.y ; POINT.y
cmp ecx,y
jnae logic4_not_set
mov logic4,1
logic4_not_set:
;polyY[i]<y && polyY[j]>=y
mov eax,logic
and eax,logic2
;polyY[j]<y && polyY[i]>=y
mov ecx,logic3
and ecx,logic4
;polyY[i]<y && polyY[j]>=y || polyY[j]<y && polyY[i]>=y
or eax,ecx
jz pol_i
;      if (polyX[i]+(y-polyY[i])/(polyY[j]-polyY[i])*(polyX[j]-polyX[i])<x)
mov eax,j
shl eax,3
mov ecx,[esi+eax].POINT.x
mov eax,i
shl eax,3
sub ecx,[esi+eax].POINT.x
push ecx ; esp=(polyX[j]-polyX[i])
mov eax,j
shl eax,3
mov ecx,[esi+eax].POINT.y
mov eax,i
shl eax,3
sub ecx,[esi+eax].POINT.y
xchg eax,ecx
mul dword ptr[esp]
pop ecx
; Something is wrong in here
push eax ; esp=(polyY[j]-polyY[i])*(polyX[j]-polyX[i])
push y
mov eax,i
shl eax,3
mov ecx,[esi+eax].POINT.y
sub dword ptr [esp],ecx ; [esp]=(y-polyY[i])
mov eax,i
shl eax,3
mov ecx,[esi+eax].POINT.x
add dword ptr [esp],ecx
pop eax
.if eax<0
pushad
invoke MessageBox,0,CADD("Error"),0,0
popad
.endif
xor edx,edx
;div dword ptr[esp]
pop ecx
mov ecx,x
cmp eax,ecx
jnl pol_i
not oddNodes
; mov oddNodes,1
; ;invoke PostQuitMessage,0
pol_i:
push i
pop j
inc i
mov eax,nPointCounts
cmp i,eax
jl loop_i

mov eax,oddNodes

ret
IsInsidePolygon endp


f lpPoints looks like this, it is ok...

PointList  dd ?,?
             dd ?,?
.
.
.

lpPoints dd PointList


but - could just be mov esi,offset PointList

We use it like this, IsInsidePolygon, x,y,addr PointList so there are no need of mov esi,offset PointList because the lpPoint is already the address of the lists.

[MichaelW]

After several hours of trying with a translation of the source here, I was not able to duplicate the results of PtInRegion. I suspect that part of the problem is the substitution of integers for floats. So I switched to the source from here, which is designed to work with integers:

Code Select Expand


int                                /*   1=inside, 0=outside                */
inpoly(                            /* is target point inside a 2D polygon? */
unsigned int poly[][2],            /*   polygon points, [0]=x, [1]=y       */
int npoints,                       /*   number of points in polygon        */
unsigned int xt,                   /*   x (horizontal) of target point     */
unsigned int yt)                   /*   y (vertical) of target point       */
{
     unsigned int xnew,ynew;
     unsigned int xold,yold;
     unsigned int x1,y1;
     unsigned int x2,y2;
     int i;
     int inside=0;

     if (npoints < 3) {
          return(0);
     }
     xold=poly[npoints-1][0];
     yold=poly[npoints-1][1];
     for (i=0 ; i < npoints ; i++) {
          xnew=poly[i][0];
          ynew=poly[i][1];
          if (xnew > xold) {
               x1=xold;
               x2=xnew;
               y1=yold;
               y2=ynew;
          }
          else {
               x1=xnew;
               x2=xold;
               y1=ynew;
               y2=yold;
          }
          if ((xnew < xt) == (xt <= xold)          /* edge "open" at one end */
           && ((long)yt-(long)y1)*(long)(x2-x1)
            < ((long)y2-(long)y1)*(long)(xt-x1)) {
               inside=!inside;
          }
          xold=xnew;
          yold=ynew;
     }
     return(inside);
}


I did not have time to translate the code to assembly so I compiled the C code to an object module and linked it into my test app. The compiled procedure appears to duplicate the results of PtInRegion in almost all cases, although I did test one polygon with an area in the vicinity of one vertex where there was a small difference, of apparently one pixel pitch. The attachment contains all the relevant components.


[attachment deleted by admin]

[dedndave]

very cool Michael
not only integer math, but much simpler to look at

[UtillMasm]

Microsoft Visual C++ Toolkit 2003
:eek
i want it.

[dedndave]

nah - write the code Utill
you learn to write more stuff
you can make better code than the C lib
and
you don't have to say "(C) Microsoft"
you can say "(C) UtillMasm"

if you don't tell us your name, i will start calling you "Yun-Fat"

[UtillMasm]

Code Select Expand

The Microsoft Visual C++ Toolkit 2003 consists of a subset of Visual Studio .NET 2003 Professional.

Yun-Fat.

:clap:

btw: thanks TmX for send me the download linker.