判断一个点在一个面内的算法

    技术2022-05-11  64

      #include <sys/types.h>#include <stdarg.h>#include <stdio.h>  #include <sys/stat.h>  #define   X   0    #define   Y   1    //typedef   enum   {   FALSE,   TRUE   }   bool;       #define   DIM           2                               /*   Dimension   of   points   */    typedef   int           tPointi[DIM];       /*   type   integer   point   */    typedef   double     tPointd[DIM];       /*   type   double   point   */    #define   PMAX         10000                       /*   Max   #   of   pts   in   polygon   */             typedef   tPointi   tPolygoni[PMAX];/*   type   integer   polygon   */       char   InPoly(   tPointi   q,   tPolygoni   P,   int   n   );    void   PrintPoly(   int   n,   tPolygoni   P   );    void   PrintPoint(   tPointi   p   );    void         Copy   (   tPolygoni   a,   tPolygoni   b   ,   int   n   );    int   ReadPoly(   tPolygoni   P   )  ;     main()    {        int     n;        tPolygoni   P,   Porig;        tPointi   q;               n   =   ReadPoly(   P   );        Copy(   P,   Porig,   n   );           while(   scanf(   "%d   %d",   &q[X],   &q[Y])   !=   EOF   )   {            printf(   "InPoly   =   %c/n",   InPoly(   q,   P,   n   )   );            /*   Refill   the   destroyed   polygon   with   original.   */            Copy(   Porig,   P,   n   );                      }    }       /*    InPoly   returns   a   char   in   {i,o,v,e}.     See   above   for   definitions.    */    char   InPoly(   tPointi   q,   tPolygoni   P,   int   n   )    {        int     i,   i1;             /*   point   index;   i1   =   i-1   mod   n   */        int     d;                     /*   dimension   index   */        double   x;                     /*   x   intersection   of   e   with   ray   */        int     Rcross   =   0;   /*   number   of   right   edge/ray   crossings   */        int         Lcross   =   0;   /*   number   of   left   edge/ray   crossings   */           printf("/n==>InPoly:   q   =   ");   PrintPoint(q);   putchar('/n');               /*   Shift   so   that   q   is   the   origin.   Note   this   destroys   the   polygon.              This   is   done   for   pedogical   clarity.   */        for(   i   =   0;   i   <   n;   i++   )   {            for(   d   =   0;   d   <   DIM;   d++   )                P[i][d]   =   P[i][d]   -   q[d];        }             /*   For   each   edge   e=(i-1,i),   see   if   crosses   ray.   */        for(   i   =   0;   i   <   n;   i++   )   {            /*   First   see   if   q=(0,0)   is   a   vertex.   */            if   (   P[i][X]==0   &&   P[i][Y]==0   )   return   'v';            i1   =   (   i   +   n   -   1   )   %   n;            /*   printf("e=(%d,%d)/t",   i1,   i);   */                       /*   if   e   "straddles"   the   x-axis...   */            /*   The   commented-out   statement   is   logically   equivalent   to   the   one                    following.   */            /*   if(   (   (   P[i][Y]   >   0   )   &&   (   P[i1][Y]   <=   0   )   )   ||                  (   (   P[i1][Y]   >   0   )   &&   (   P[i]   [Y]   <=   0   )   )   )   {   */                       if(   (   P[i][Y]   >   0   )   !=   (   P[i1][Y]   >   0   )   )   {                               /*   e   straddles   ray,   so   compute   intersection   with   ray.   */                x   =   (P[i][X]   *   (double)P[i1][Y]   -   P[i1][X]   *   (double)P[i][Y])/(double)(P[i1][Y]   -   P[i][Y]);                /*   printf("straddles:   x   =   %g/t",   x);   */                               /*   crosses   ray   if   strictly   positive   intersection.   */                if   (x   >   0)   Rcross++;            }            /*   printf("Right   cross=%d/t",   Rcross);   */                       /*   if   e   straddles   the   x-axis   when   reversed...   */            /*   if(   (   (   P[i]   [Y]   <   0   )   &&   (   P[i1][Y]   >=   0   )   )   ||                  (   (   P[i1][Y]   <   0   )   &&   (   P[i]   [Y]   >=   0   )   )   )     {   */                       if   (   (   P[i][Y]   <   0   )   !=   (   P[i1][Y]   <   0   )   )   {                                 /*   e   straddles   ray,   so   compute   intersection   with   ray.   */                x   =   (P[i][X]   *   P[i1][Y]   -   P[i1][X]   *   P[i][Y])                        /   (double)(P[i1][Y]   -   P[i][Y]);                /*   printf("straddles:   x   =   %g/t",   x);   */                   /*   crosses   ray   if   strictly   positive   intersection.   */                if   (x   <   0)   Lcross++;            }            /*   printf("Left   cross=%d/n",   Lcross);   */        }                 /*   q   on   the   edge   if   left   and   right   cross   are   not   the   same   parity.   */        if(   (   Rcross   %   2   )   !=   (Lcross   %   2   )   )            return   'e';               /*   q   inside   iff   an   odd   number   of   crossings.   */        if(   (Rcross   %   2)   ==   1   )            return   'i';        else   return   'o';    }       void   PrintPoint(   tPointi   p   )    {        int   i;               putchar('(');        for   (   i   =   0;   i   <   DIM;   i++   )   {            printf("%d",   p[i]);            if   (   i   !=   DIM-1   )   putchar(',');        }        putchar(')');    }       /*          Reads   in   the   coordinates   of   the   vertices   of   a   polygon   from   stdin,          puts   them   into   P,   and   returns   n,   the   number   of   vertices.          Formatting   conventions:   etc.          */    int   ReadPoly(   tPolygoni   P   )    {        int   i,   n;               do   {            printf(   "Input   the   number   of   vertices:/n");            scanf(   "%d",   &n   );            if   (   n   <=   PMAX   )                break;            printf("Error   in   read_poly:     too   many   points;   max   is   %d/n",   PMAX);        }        while   (   1   );           printf(   "Polygon:/n"   );        printf(   "       i       x       y/n");        for   (   i   =   0;   i   <   n;   i++   )   {            scanf(   "%d   %d",   &P[i][0],   &P[i][1]   );            printf("=MM/n",   i,   P[i][0],   P[i][1]);        }        printf("n   =   =   vertices   read/n",n);        putchar('/n');           return   n;    }       void   PrintPoly(   int   n,   tPolygoni   P   )    {        int   i;               printf("Polygon:/n");        printf("     i       x       y/n");        for(   i   =   0;   i   <   n;   i++   )            printf("=MM/n",   i,   P[i][0],   P[i][1]);    }       /*   Copy   polygon   a   to   b   (overwriting   b).   */    void   Copy(   tPolygoni   a,   tPolygoni   b,   int   n   )    {        int   i,   j;               for   (   i=0;   i   <   n;   i++)            for   (   j   =   0;   j   <   DIM;   j++   )                b[i][j]   =   a[i][j];    }     /*  bool   EqPoint(   tPointi   a,   tPointi   b   )    {        int           i;        for   (   i   =   0;   i   <   DIM;   i++   )            if   (   a[i]   !=   b[i])                return     FALSE;        return     TRUE;    }  */  /*gcc -lstdc++  testpoint.cpp

    645 2035 1010 1530 2520 3540 3025 1525 2525 20

      */ 


    最新回复(0)