Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #1003

Re: inside parallelogram?

Show all headers | View raw

lloyd <lloyd.houghton@gmail.com> wrote in news:18a4d91e-99c0-428e-823a-
3b62ed401ae9@l12g2000vby.googlegroups.com:

> On Nov 6, 4:18 pm, Sjouke Burry <bu...@planet.nl> wrote:
> 
>>this (works perfectly for me)
> 
> Hey Sjouke thank you! Thanks James too, but Sjouke's solution was more
> ready for me to use. Sjouke I have one question. I have a simpler case
> than your more general case, as I am constrained to have an uncrossed
> parallelogram in the upper half-plane whose lowest corner is at the
> origin, and all corners have integer coordinates. When I use your
> code, it misses the corners of the parallelogram. For example when I
> set the first corner to (-2,5) and the third corner to (11,3) (with
> the 0th corner the origin and the 2nd corner calculated as the vector
> sum of the two others), I get this (view fixed-width; 0 is the
> origin):
> 
> . . . . . . . . . . . . . .
> . . . . . . . . X X X X . .
> . . . . X X X X X X X X . .
> X X X X X X X X X X X X X .
> . X X X X X X X X X X X X .
> . X X X X X X X X X X X X .
> . . X X X X X X X X . . . .
> . . X X X X . . . . . . . .
> . . 0 . . . . . . . . . . .
> 
> But I should get this (missing corners indicated with Q):
> 
> . . . . . . . . . . . Q . .
> . . . . . . . . X X X X . .
> . . . . X X X X X X X X . .
> X X X X X X X X X X X X X .
> . X X X X X X X X X X X X .
> . X X X X X X X X X X X XQ.
> . . X X X X X X X X . . . .
> . . X X X X . . . . . . . .
> . . 0 . . . . . . . . . . .
> 
> (My C program is below for reference). When you run your program, do
> the corners get included? I'm sure I just need to change an equals
> sign to an inequality somewhere, but I can't figure out where. Thanks
> so much -- Lloyd.
> 
> #include <stdio.h>
> 
> main()
> {
>         int xp[4]={0,-2,0,11};
>         int yp[4]={0,5,0,3};
>         int x,y,p1,p2,i,j,c;
>         int max_x,min_x,max_y;
> 
>         xp[2]=xp[1]+xp[3];
>         yp[2]=yp[1]+yp[3];
> 
>         min_x=0;max_x=0;
>         for(i=0;i<4;i++)
>                 {
>                 if (xp[i]<min_x) min_x=xp[i];
>                 if (xp[i]>max_x) max_x=xp[i];
>                 }
>         max_y=yp[2];
> 
>         for(y=max_y;y>=0;y--)
>                 {
>                 for(x=min_x;x<=max_x;x++)
>                         {
>                         c=0;
>                         for (i=0,j=3;i<4;j=i++)
>                                 {
>                                 p1=(((yp[i]<=y) && (y<yp[j]))  ||
>                                     ((yp[j]<=y) && (y<yp[i])));
>                                 if(yp[j]==yp[i])
>                                         {
>                                         if( ((xp[j]-xp[i]) >=0 && (y-
> yp[i])>=0)  ||
>                                             ((xp[j]-xp[i]) < 0 && (y-
> yp[i]) <0)  )
>                                                 p2=1;
>                                         else
>                                                 p2=0;
>                                         }
>                                 else
>                                         p2=(x < (xp[j]-xp[i])*(y-
> yp[i])/(float)(yp[j]-yp[i])+xp[i]);
> 
>                                 if(p1 && p2) c=!c;
>                                 }
> 
>                         if (!x && !y)
>                                 printf("0 ");
>                         else if (c)
>                                 printf("X ");
>                         else
>                                 printf(". ");
>                         }
>                 printf("\n");
>                 }
> }
> 
I suspect rounding error. Using double, and the mouse
to browse around the polygon, I get no detectable errors,
using line color to show inside/outside state.
If you want to know, whether the dot is on a line,
calculate the 4 distances, and if one is less than 1,
you could assume it is on that line.
you need to check though whether the point is between or on
the 2 corners,when the inside/outside flag shows outside.

Back to comp.programming | Previous | Next — Previous in thread | Find similar

Thread

inside parallelogram? lloyd <lloyd.houghton@gmail.com> - 2011-11-05 14:40 -0700
  Re: inside parallelogram? James Waldby <not@valid.invalid> - 2011-11-06 20:49 +0000
    Re: inside parallelogram? James Waldby <not@valid.invalid> - 2011-11-06 21:02 +0000
  Re: inside parallelogram? Sjouke Burry <burry@planet.nl> - 2011-11-06 21:18 +0000
    Re: inside parallelogram? lloyd <lloyd.houghton@gmail.com> - 2011-11-06 21:37 -0800
      Re: inside parallelogram? Sjouke Burry <burry@planet.nl> - 2011-11-07 06:47 +0000

csiph-web