GRASS Programmer's Manual  6.4.2(2012)
driver/Polygon.c
Go to the documentation of this file.
00001 #include <stdlib.h>
00002 #include <math.h>
00003 #include <grass/gis.h>
00004 #include "driver.h"
00005 #include "driverlib.h"
00006 
00007 struct point
00008 {
00009     int x, y;
00010 };
00011 
00012 static int cmp_int(const void *aa, const void *bb)
00013 {
00014     const int *a = aa;
00015     const int *b = bb;
00016 
00017     return *a - *b;
00018 }
00019 
00020 static void fill(int x0, int x1, int y)
00021 {
00022     COM_Box_abs(x0, y, x1, y + 1);
00023 }
00024 
00025 static void line(const struct point *p, int n, int y)
00026 {
00027     static int *xs;
00028     static int max_x;
00029     int num_x = 0;
00030     int i;
00031 
00032     for (i = 0; i < n; i++) {
00033         const struct point *p0 = &p[i];
00034         const struct point *p1 = &p[i + 1];
00035         const struct point *tmp;
00036         double fx, fy;
00037         long x;
00038 
00039         if (p0->y == p1->y)
00040             continue;
00041 
00042         if (p0->y > p1->y)
00043             tmp = p0, p0 = p1, p1 = tmp;
00044 
00045         if (p0->y > y)
00046             continue;
00047 
00048         if (p1->y <= y)
00049             continue;
00050 
00051         fy = y + 0.5;
00052         fx = (double)p1->x * (fy - p0->y) + (double)p0->x * (p1->y - fy);
00053         fx /= p1->y - p0->y;
00054         x = fx < -0x7fffffff ? -0x7fffffff :
00055             fx > 0x7fffffff ? 0x7fffffff : (long)floor(fx + 0.5);
00056 
00057         if (num_x >= max_x) {
00058             max_x += 20;
00059             xs = G_realloc(xs, max_x * sizeof(int));
00060         }
00061 
00062         xs[num_x++] = x;
00063     }
00064 
00065     qsort(xs, num_x, sizeof(int), cmp_int);
00066 
00067     for (i = 0; i + 1 < num_x; i += 2)
00068         fill(xs[i], xs[i + 1], y);
00069 }
00070 
00071 static void poly(const struct point *p, int n)
00072 {
00073     int y0, y1;
00074     int i, y;
00075 
00076     if (n < 3)
00077         return;
00078 
00079     y0 = y1 = p[0].y;
00080 
00081     for (i = 1; i < n; i++) {
00082         if (y0 > p[i].y)
00083             y0 = p[i].y;
00084 
00085         if (y1 < p[i].y)
00086             y1 = p[i].y;
00087     }
00088 
00089     if (y0 > screen_bottom || y1 < screen_top)
00090         return;
00091 
00092     if (y0 < screen_top)
00093         y0 = screen_top;
00094 
00095     if (y1 > screen_bottom)
00096         y1 = screen_bottom;
00097 
00098     for (y = y0; y < y1; y++)
00099         line(p, n, y);
00100 }
00101 
00102 static void fill_polygon(const int *xarray, const int *yarray, int count)
00103 {
00104     static struct point *points;
00105     static int max_points;
00106     int i;
00107 
00108     if (max_points < count + 1) {
00109         max_points = count + 1;
00110         points = G_realloc(points, sizeof(struct point) * max_points);
00111     }
00112 
00113     for (i = 0; i < count; i++) {
00114         points[i].x = xarray[i];
00115         points[i].y = yarray[i];
00116     }
00117 
00118     points[count].x = xarray[0];
00119     points[count].y = yarray[0];
00120 
00121     poly(points, count);
00122 }
00123 
00124 void COM_Polygon_abs(const int *xarray, const int *yarray, int number)
00125 {
00126     if (driver->Polygon_abs) {
00127         (*driver->Polygon_abs) (xarray, yarray, number);
00128         return;
00129     }
00130 
00131     fill_polygon(xarray, yarray, number);
00132 }
00133 
00134 void COM_Polygon_rel(const int *xarray, const int *yarray, int number)
00135 {
00136     static int *xa, *ya;
00137     static int nalloc;
00138     int i;
00139 
00140     if (driver->Polygon_rel) {
00141         (*driver->Polygon_rel) (xarray, yarray, number);
00142         return;
00143     }
00144 
00145     if (number > nalloc) {
00146         nalloc = number;
00147         xa = G_realloc(xa, (size_t) nalloc * sizeof(int));
00148         ya = G_realloc(ya, (size_t) nalloc * sizeof(int));
00149     }
00150 
00151     xa[0] = xarray[0] + cur_x;
00152     ya[0] = yarray[0] + cur_y;
00153 
00154     for (i = 1; i < number; i++) {
00155         xa[i] = xa[i - 1] + xarray[i];
00156         ya[i] = ya[i - 1] + yarray[i];
00157     }
00158 
00159     COM_Polygon_abs(xa, ya, number);
00160 }
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines