From: Chris Stasny <staz@...>

Date: Thu, 8 Jun 2000 09:22:28 -0500

Date: Thu, 8 Jun 2000 09:22:28 -0500

Being math ignorant, I would have approached this problem from the toolbox. Conversationally... Open region Draw poly Close region Use PTINRGN Dispose region 5 lines of code to do the same thing. :) >Hi All, > >Given a point polygon p and a point (x,y) NOT ON p, we are deciding >whether (x,y) lies inside of p -- by suitably counting edge >intersections with the ray going right (east) from (x,y). In fact, >points (x,y) too near to p may give a wrong answer or even cause a >zero-divide error. > >I happen to have looked at this problem recently for loops that are >piecewise b'ezier (or worse) rather than piecewise linear. So I cannot >resist commenting on the C-code. (I'll explain the b'ezize curve case >privately if someone is really interested.) > >Randolph Franklin original C code looks clean and solid to me. >He does miss one optimization that Paul D. Bourke >uses. Namely bypass the guts of the for loop in case the max of xp[i] >and xp[j] is less than x. That is because the edge p[j] to p[i] >could then not possibly hit the ray. > >Franklin's C code revised is: > > int pnpoly(int npol, float *xp, float *yp, float x, float y) > {int i, j, c = 0; > for (i = 0, j = npol-1; i < npol; j = i++) > {if (xp[i]<=x && xp[j]<=x) \* the added condition is "if..."; LS *\ > {if ((((yp[i] <= y) && (y < yp[j])) || > ((yp[j] <= y) && (y < yp[i]))) && > (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) > c = !c; > } > } > return c; > } > > Paul C. Bourke's code (below) on the other hand seems to contain >a a redundancy and a glitch. > >The redundancy is Bourke's condition: > > if (p1.y != p2.y) > >At the point in question (p1.y != p2.y) is necessarily true. > >The possible glitch is Bourke's > > if (p1.x == p2.x || p.x <= xinters) > >I think that line should become: > > if (p.x <= xinters) > >My reason: Bourke seems to be counting all *vertical* edges* that hit >the horizontal line through (x,y) and protrude below it. That seems >wrong. > >I may be confused myself, but I believe Bourke's code would report >that (x,y)=(.5,.5) is not inside the unit square! > >Sorry to address the meaning rather than the FB translation. >But I believe translation in general must pass via meaning. > > Cheers > > Larry S > >PS. Here is Bourke's code: > > > Content: futurebasic_18774.ezm > > Date: Tue, 6 Jun 2000 22:55:14 -0400 > > From: Robert Covington <t88@...> > >... > > From Paul D. Bourke: > > > > The following C function returns INSIDE or OUTSIDE indicating >the status of > > a point P with respect to a polygon with N points. > > > > #define MIN(x,y) (x < y ? x : y) > > #define MAX(x,y) (x > y ? x : y) > > #define INSIDE 0 > > #define OUTSIDE 1 > > > > typedef struct { > > double x,y; > > } Point; > > > > int InsidePolygon(Point *polygon,int N,Point p) > > { > > DIM counter as int > > counter =0 > > int i as int > > DIM xinters as double > > DIM p1 as point ,p2 as point > > > > p1 = polygon[0]; > > for (i=1;i<=N;i++) { > > p2 = polygon[i % N]; > > if (p.y > MIN(p1.y,p2.y)) { > > if (p.y <= MAX(p1.y,p2.y)) { > > if (p.x <= MAX(p1.x,p2.x)) { > > if (p1.y != p2.y) { > > xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x; > > if (p1.x == p2.x || p.x <= xinters) > > counter++; > > } > > } > > } > > } > > p1 = p2 > > } > > > > if (counter % 2 == 0) > > return(OUTSIDE); > > else > > return(INSIDE); > > >-- >To unsubscribe, send ANY message to <futurebasic-unsubscribe@...> Best, -STAZ ~)~ 800.348.2623 Orders http://www.stazsoftware.com 228.255.7086 FAX mailto:staz@...