00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016 #include "pt_poly.h"
00017
00018
00019
00020 #define quadrant(vertex, x, y) \
00021 ( (vertex->x > x) ? ((vertex->y > y) ? 0 : 3) : ( (vertex->y > y) ? 1 : 2) )
00022
00023
00024
00025 #define x_intercept(pt1, pt2, yy) \
00026 (pt2->x - ( (pt2->y - yy) * ((pt1->x - pt2->x) / (pt1->y - pt2->y)) ) )
00027
00028
00029 #define adjust_delta(delta, vertex, next_vertex, xx, yy) \
00030 switch (delta) { \
00031 \
00032 case 3: delta = -1; break; \
00033 case -3: delta = 1; break; \
00034 \
00035 case 2: case -2: if (x_intercept(vertex, next_vertex, yy) > xx) \
00036 delta = - (delta); \
00037 break; \
00038 }
00039
00040
00041
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
00048 vertex = NULL;
00049 vertex = first_vertex = polygon_get_vertex(poly,vertex);
00050 quad = quadrant(vertex, x, y);
00051 angle = 0;
00052
00053 do {
00054 next_vertex = polygon_get_vertex(poly,vertex);
00055
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
00061 angle = angle + delta;
00062
00063 quad = next_quad;
00064 vertex = next_vertex;
00065 } while (vertex != first_vertex);
00066
00067
00068
00069 if ((angle == +4) || (angle == -4)) return DENTRO; else return FUERA;
00070
00071
00072
00073
00074
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
00089
00090
00091
00092
00093
00094 return (x >= vertex1->x && x <= vertex2->x);
00095 else return 0;
00096 }
00097