[futurebasic] [FB] Re: small C to FB problem

Message: < previous - next > : Reply : Subscribe : Cleanse
Home   : June 2000 : Group Archive : Group : All Groups

From: Chris Stasny <staz@...>
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@...