Anyone know how to determine if a point(x,y) is inside a set of points?
How about this (http://alienryderflex.com/polygon/)?
Thanks. I'll take a look.
If j=i what is the different of polY and polY[j]? Anyone can explain?
i and j are two points that are being tested
if you look at the first image on that page - then read the first paragraph
you can toss out his C code and write it in asm
@TmX - that looks like a cool site
i need a refresher in reading C - haven't had to look at it for years
now, trying to learn API functions - it seems all the examples are C
you guys can all take solice - if i were ceo of MS, all the examples would be in asm and we'd make the C guys figure it out - lol
oh - btw Farabi - make sure you include the possibility of polygons are larger than the display area
this looks like a good basis for a fill routine
EDIT:
i knew i saw this someplace
recursive fill
this one is written in basic :red
http://www.wearmouth.demon.co.uk/gw03/basfill.htm
Quote from: Farabi on May 21, 2009, 10:41:39 AM
If j=i what is the different of polY and polY[j]? Anyone can explain?
no difference
but look, j have a constant value: polySides-1
while for i, you have to iterate from 0 to polySides
example:
polySides = 10
j = 9
i = 0,1,2,3,4,5,6,7,8,9
Quote from: TmX on May 21, 2009, 12:38:36 PM
Quote from: Farabi on May 21, 2009, 10:41:39 AM
If j=i what is the different of polY and polY[j]? Anyone can explain?
no difference
but look, j have a constant value: polySides-1
while for i, you have to iterate from 0 to polySides
example:
polySides = 10
j = 9
i = 0,1,2,3,4,5,6,7,8,9
So j must remain 9 until the iteration is complete am I right?
ah sorry, just recently re-read the code again
first, j is initialized as polySide-1
and during the iteration, j is updated by "j =i"
so j's value it's not constant...
For the lazy programmer...
The PtInRegion function determines whether the specified point is inside the specified region.
BOOL PtInRegion(
HRGN hrgn, // handle of region
int X, // x-coordinate of point
int Y // y-coordinate of point
);
Quote from: jj2007 on May 21, 2009, 05:17:44 PM
For the lazy programmer...
The PtInRegion function determines whether the specified point is inside the specified region.
BOOL PtInRegion(
HRGN hrgn, // handle of region
int X, // x-coordinate of point
int Y // y-coordinate of point
);
I'll try to use non-MS first, If Im stuck I guess I will use MS one.
Here is my code so far
IsInsidePolygon proc uses esi edi x:dword,y:dword,lpPoints:dword,nPointCounts:dword
LOCAL i,j:dword
LOCAL oddNodes,logic: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:
mov eax,i
shl eax,3
mov ecx,[esi+eax].POINT.y ; POINT.y
cmp ecx,y
jnl pol_i
mov eax,j
shl eax,3
mov ecx,[esi+eax].POINT.y
cmp ecx,y
jnae 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 ; POINT.y
cmp ecx,y
jnae pol_i
pol_i:
inc i
mov eax,nPointCounts
cmp i,eax
jl loop_i
ret
And about if (polyX+(y-polyY)/(polyY[j]-polyY)*(polyX[j]-polyX)<x) What should I calculate first? Add everything first and then divide it I guess?
Farabi, are you trying to see if it is a target hit ?
Quote from: dedndave on May 22, 2009, 03:46:56 AM
Farabi, are you trying to see if it is a target hit ?
Yes.
Look this picture,
(http://omploader.org/vMXBrdg/fe.bmp)
I want the user able to pick a polygon from the mouse and my app will crop it.
Here is the complete code, but it have not working yet. Mind to help?
Quote
IsInsidePolygon proc uses esi edi x:dword,y:dword,lpPoints:dword,nPointCounts:dword
LOCAL i,j:dword
LOCAL oddNodes,logic:dword
; bool pointInPolygon() {
;
; int i, j=polySides-1 ;
;boolean oddNodes=NO ;
;
; for (i=0; i<polySides; i++) {
; if (polyY<y && polyY[j]>=y
; || polyY[j]<y && polyY>=y) {
; if (polyX+(y-polyY)/(polyY[j]-polyY)*(polyX[j]-polyX)<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:
mov eax,i
shl eax,3
mov ecx,[esi+eax].POINT.y ; POINT.y
cmp ecx,y
jnl pol_i
mov eax,j
shl eax,3
mov ecx,[esi+eax].POINT.y
cmp ecx,y
jnae 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 ; POINT.y
cmp ecx,y
jnae pol_i
; if (polyX+(y-polyY)/(polyY[j]-polyY)*(polyX[j]-polyX)<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)
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 ; esp=(polyY[j]-polyY)*(polyX[j]-polyX)
push y
mov eax,i
shl eax,3
mov ecx,[esi+eax].POINT.y
sub dword ptr [esp],ecx ; [esp]=(y-polyY)
mov eax,i
shl eax,3
mov ecx,[esi+eax].POINT.x
add dword ptr [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
oh my fo!
this man looks like a terrorist!
lol - that man is Farabi :eek
give me some time to look at the code......
that is some monster code - lol
for the polygon, you have a set of lines - a list ? with end-points ?
Quote from: dedndave on May 22, 2009, 04:18:57 AM
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
Quote from: UtillMasm on May 22, 2009, 04:13:39 AM
oh my fo!
this man looks like a terrorist!
*ahem*
(http://www.addemoticons.com/emoticon/animated/AddEmoticons04232.gif)
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
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
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
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.
mov esi,lpPoints
should be
mov esi,offset lpPoints
Quote from: dedndave on May 22, 2009, 03:14:10 PM
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.
if lpPoints looks like this, it is ok...
PointList dd ?,?
dd ?,?
.
.
.
lpPoints dd PointList
but - could just be mov esi,offset PointList
Almost work but div instruction causing memory leak.
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
Quote
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.
After several hours of trying with a translation of the source here (http://alienryderflex.com/polygon/), 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 (http://www.visibone.com/inpoly/), which is designed to work with integers:
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]
very cool Michael
not only integer math, but much simpler to look at
Microsoft Visual C++ Toolkit 2003
:eek
i want it.
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"
(http://www.iwatchstuff.com/2007/06/15/chow-yun-fat-cut.jpg)
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.
Michael:
:U
I think I will use that code, its tiny anyway.