Página principal   Lista alfabética   Lista de componentes   Lista de archivos   Miembros de las clases   Archivos de los miembros  

pt_poly.cpp

Ir a la documentación de este archivo.
00001 /************************************************/
00002 /*  Rutinas para el test "punto en poligono     */
00003 /*  Se utiliza el metodo del calculo de angulos */
00004 /*  acumulados.                                 */
00005 /*  Rutina tomada de Graphics GEMS              */
00006 /*  y modificada convenientemente               */
00007 /************************************************/
00008 
00009 /*
00010  * C code from the article
00011  * "An Incremental Angle Point in Polygon Test"
00012  * by Kevin Weiler, kjw@autodesk.com
00013  * in "Graphics Gems IV", Academic Press, 1994
00014  */
00015 
00016 #include "pt_poly.h"
00017 
00018         /* determine the quadrant of a polygon point
00019            relative to the test point */
00020 #define quadrant(vertex, x, y) \
00021   ( (vertex->x > x) ? ((vertex->y > y) ? 0 : 3) : ( (vertex->y > y) ? 1 : 2) )
00022 
00023         /* determine x intercept of a polygon edge
00024            with a horizontal line at the y value of the test point */
00025 #define x_intercept(pt1, pt2,  yy) \
00026   (pt2->x - ( (pt2->y - yy) * ((pt1->x - pt2->x) / (pt1->y - pt2->y)) ) )
00027 
00028         /* adjust delta */
00029 #define adjust_delta(delta, vertex, next_vertex, xx, yy)                \
00030   switch (delta) {                                                      \
00031             /* make quadrant deltas wrap around */                      \
00032     case  3:    delta = -1; break;                                      \
00033     case -3:    delta =  1; break;                                      \
00034             /* check if went around point cw or ccw */                  \
00035     case  2: case -2: if (x_intercept(vertex, next_vertex, yy) > xx)    \
00036                     delta =  - (delta);                                 \
00037                 break;                                                  \
00038     }
00039 
00040         /* determine if a test point is inside of or outside of a polygon */
00041         /* polygon is "poly", test point is at "x","y" */
00042 pt_poly_relation point_in_poly(polygon_ptr poly, double x, double y)
00043 {
00044   vtx_ptr  vertex, first_vertex, next_vertex;
00045   quadrant_type quad, next_quad, delta, angle;
00046 
00047             /* initialize */
00048   vertex = NULL;    /* because polygon_get_vertex is a macro */
00049   vertex = first_vertex = polygon_get_vertex(poly,vertex);
00050   quad = quadrant(vertex, x, y);
00051   angle = 0;
00052             /* loop on all vertices of polygon */
00053   do {
00054     next_vertex = polygon_get_vertex(poly,vertex);
00055                 /* calculate quadrant and delta from last quadrant */
00056     if (point_on_edge(vertex,next_vertex,x,y)) return FUERA;
00057     next_quad = quadrant(next_vertex, x, y);
00058     delta = next_quad - quad;
00059     adjust_delta(delta,vertex,next_vertex,x,y);
00060                 /* add delta to total angle sum */
00061     angle = angle + delta;
00062                 /* increment for next step */
00063     quad = next_quad;
00064     vertex = next_vertex;
00065     } while (vertex != first_vertex);
00066 
00067             /* complete 360 degrees (angle of + 4 or -4 ) means inside */
00068 
00069   if ((angle == +4) || (angle == -4)) return DENTRO; else return FUERA;
00070 
00071             /* odd number of windings rule */
00072   /* if (angle & 4) return INSIDE; else return OUTSIDE; */
00073             /* non-zero winding rule */
00074   /* if (angle != 0) return INSIDE; else return OUTSIDE; */
00075 }
00076 
00077 int point_on_edge(vtx_ptr vertex1, vtx_ptr vertex2, double x, double y) {
00078   if ((vertex1->x == vertex2->x) && (vertex1->x == x))
00079     if (vertex1->y > vertex2->y)
00080       return (y >= vertex2->y && y <= vertex1->y);
00081     else
00082       return (y >= vertex1->y && y <= vertex2->y);
00083   else if ((vertex1->y == vertex2->y) && (vertex1->y == y))
00084     if (vertex1->x > vertex2->x)
00085       return (x >= vertex2->x && x <= vertex1->x);
00086     else
00087 
00088 //      return (x >= vertex1->y && x <= vertex2->x);
00089 
00090 //              ESTA LINEA ANULADA ES LA DEL CODIGO ORIGINAL
00091 //              QUE POR CIERTO ¡¡¡¡¡¡¡¡¡ESTABA MAL!!!!!!!!!!
00092 //              la linea equivalente, pero correcta es la de abajo                                                                                                              
00093 
00094       return (x >= vertex1->x && x <= vertex2->x);
00095   else return 0;
00096 }
00097 

Generado el Tue Apr 24 06:55:48 2001 para Dllcontrol por doxygen1.2.6 escrito por Dimitri van Heesch, © 1997-2001