***HELP*** with CYRUS-BECK algorithm 
Author Message
 ***HELP*** with CYRUS-BECK algorithm

Hi everyone!

   I've implemented a 2D cyrus-beck algorithm from the Rogers' book to know if a
polygon intersects another one (both convexes). The problem is that I've found
one case where the algorithm doesn't work. Since I cannot figure out what's wrong
with it, I ask somebody to please take a look in the code (C one given below) OR
please send a correct version of such algorithm.
  I send also a postscript  figure which shows that both polygones don't
intersect themselves.
  PLEASE ***MAIL*** the answer!!
  The function cyrus_beck returns 1 when there is intersection and 0 (zero) when
there is not. the polygones are given by poly and p2 arrays.

Thanks a lot.

Nilo.

/*********************C code:***********************/

main()
  {  static double poly[16]=
     { 0.0, 0.0, 0.0, 11.5942033161315301, 11.0267417074506913,
       15.1770101134445046,17.8416437317122387, 5.7971037060037176,
       11.0267436001553065 ,-3.58280423799886671};
     static double p2[6]=
     { 0.575126459104368992, -0.866231306382081678, 0.726550103311835338
      -0.817030764995151926, 0.658831404687457045, -0.981441257308409254};
     int i;
     i=cyrus_beck(&poly[0],&p2[0],5,3);
  }

#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
cyrus_beck(P,p,K,k)
double *P,*p;
int K,k;
  { double *n,*N,*v,*V,dx,dy,wx,wy,t,tl,tu,DxN,WxN;
    int i,j, invisible;
    N=(double *)malloc(sizeof(double)*K*2);
    n=N; V=P;
    for(i=1; i<=K; i++)
       { for (j=0; j<2; j++)
            { *(n+(j^1))=*V-((i==K)?*(P+j):*(V+2));
              V++; }
         if(*n!=0) *n=-*n;
         n+=2;
       }
    v=p;
    for (i=1; i<=k; (v+=2,i++))
      { n=N;
        V=P;
        dx=((i==k)?*p:*(v+2))-*v;
        dy=((i==k)?*(p+1):*(v+3))-*(v+1);
        tl=0; tu=1;
        invisible=0;
        for (j=1; j<=K; ((n+=2,V+=2),j++))
           { wx=*v-*V;
             wy=*(v+1)-*(V+1);
             DxN=dx* *n + dy* *(n+1);
             WxN=wx* *n + wy* *(n+1);
             if(DxN==0)
               { if(WxN<0) {invisible=1; break;}
                  else continue;
               }
             t= -WxN/DxN;
             if (DxN>0)
               { if (t<=1) tl=MAX(t,tl);}
             else
               { if (t>=0) tu=MIN(t,tu);}
            }
         if((invisible)||(tl>tu)) continue;
         free(N);
         return(1);
      }
    free(N);
    return(0);
  }

/********PostScript figure:************/
%!
/draw_poly
 { /np exch 1 sub def
   /arr exch def arr 0 get aload pop
   moveto
   1 1 np { arr exch get aload pop lineto } for
   arr 0 get aload pop lineto
  } bind def

50 250 translate
0.0 0.0 moveto
30 30 scale
[[0.0 0.0]
 [0.0 11.5942033161315301]
 [11.0267417074506913 15.1770101134445046]
 [17.8416437317122387 5.7971037060037176]
 [11.0267436001553065 -3.58280423799886671]
] 5 draw_poly stroke

[[0.575126459104368992 -0.866231306382081678]
 [0.726550103311835338 -0.817030764995151926]
 [0.658831404687457045 -0.981441257308409254]
] 3 draw_poly stroke
showpage



Thu, 17 Aug 1995 04:48:54 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. Rogers' CYRUS-BECK ***WRONG***???!!

2. ***HELP*** Algorithms/Code for Greyscale to Postscript...

3. Need Half-Toning Algorithm suited for HP-Laserjet

4. eexec decoding algorithm

5. Halftoning Algorithm

6. Encryption of XML using Russian Peasant Algorithm

7. Encryption algorithm implementation in JScript

8. Algorithm for automatic page change ?

9. Very fast spline algorithm ???

10. smooth type algorithm Apple LaserWriter

11. Best algorithm to build smallcaps from standard font (eg.: Times)

 

 
Powered by phpBB® Forum Software