GRASS GIS 8 Programmer's Manual  8.5.0dev(2024)-0b29c8ef57
htmldriver/polygon.c
Go to the documentation of this file.
1 #include <string.h>
2 #include <stdlib.h>
3 #include <math.h>
4 
5 #include <grass/gis.h>
6 #include "driverlib.h"
7 #include "htmlmap.h"
8 
9 #define RAD_DEG M_R2D
10 
11 static void delete_point(int *x, int *y, int count)
12 {
13  int i;
14 
15  for (i = 0; i < count; i++) {
16  x[i] = x[i + 1];
17  y[i] = y[i + 1];
18  }
19 }
20 
21 static double find_azimuth(double x1, double y1, double x2, double y2)
22 {
23  double xx, yy;
24 
25  xx = x1 - x2;
26  yy = y1 - y2;
27 
28  if (x1 == x2) {
29  return (y2 > y1) ? 90.0 : 270.0;
30  }
31  else {
32  if (y2 < y1) {
33  if (x2 > x1) {
34  return 360.0 + (RAD_DEG * atan(yy / xx));
35  }
36  else {
37  return 180.0 + (RAD_DEG * atan(yy / xx));
38  }
39  }
40  else {
41  if (x2 > x1) {
42  return (RAD_DEG * atan(yy / xx));
43  }
44  else {
45  return 180.0 + (RAD_DEG * atan(yy / xx));
46  }
47  }
48  }
49 }
50 
51 void html_polygon(const struct path *p)
52 {
53  int n = p->count;
54  struct MapPoly *new;
55  int i;
56  int delta_x, delta_y;
57  int min_x, max_x, min_y, max_y;
58 
59  double min_azimuth = 1.0;
60  double azimuth1, azimuth2, diff1, diff2;
61  int *x = G_malloc(n * sizeof(int));
62  int *y = G_malloc(n * sizeof(int));
63 
64  for (i = 0; i < n; i++) {
65  x[i] = (int)floor(p->vertices[i].x + 0.5);
66  y[i] = (int)floor(p->vertices[i].y + 0.5);
67  }
68 
69  /*
70  * remove points that have adjacent duplicates or have differences of
71  * less the the minimum allowed. remove end points that are same as
72  * the begin point (ending point = starting point is added
73  * during Graph_Clse)
74  */
75 
76  i = 0;
77  while (i < (n - 1)) {
78  delta_x = x[i] - x[i + 1];
79  if (delta_x < 0)
80  delta_x = -delta_x;
81  delta_y = y[i] - y[i + 1];
82  if (delta_y < 0)
83  delta_y = -delta_y;
84 
85  if ((x[i] == x[i + 1] && y[i] == y[i + 1]) ||
86  (delta_x <= html.MINIMUM_DIST && delta_y <= html.MINIMUM_DIST)) {
87  delete_point(&x[i + 1], &y[i + 1], n - i - 1);
88  --n;
89  }
90  else {
91  ++i;
92  }
93  }
94 
95  /* perform same checks for last point & first point */
96  while (1) {
97  delta_x = x[0] - x[n - 1];
98  if (delta_x < 0)
99  delta_x = -delta_x;
100  delta_y = y[0] - y[n - 1];
101  if (delta_y < 0)
102  delta_y = -delta_y;
103 
104  if ((x[0] == x[n - 1] && y[0] == y[n - 1]) ||
105  (delta_x <= html.MINIMUM_DIST && delta_y <= html.MINIMUM_DIST)) {
106  --n;
107  }
108  else {
109  break;
110  }
111  }
112 
113  /*
114  * if a polygon has either x or y extents less than the bounding box
115  * minimum, ignore it
116  *
117  */
118 
119  min_x = max_x = x[0];
120  min_y = max_y = y[0];
121  for (i = 0; i < n; i++) {
122  if (x[i] < min_x)
123  min_x = x[i];
124  if (x[i] > max_x)
125  max_x = x[i];
126  if (y[i] < min_y)
127  min_y = y[i];
128  if (y[i] > max_y)
129  max_y = y[i];
130  }
131  delta_x = max_x - min_x;
132  delta_y = max_y - min_y;
133  if (delta_x < html.BBOX_MINIMUM || delta_y < html.BBOX_MINIMUM) {
134  n = 0;
135  }
136 
137  /*
138  * remove points in excess of MAX_POINTS vertices
139  */
140 
141  while (n > html.MAX_POINTS) {
142 
143  for (i = 0; i < (n - 2); i++) {
144 
145  /*
146  * see if middle point can be removed, by checking if the
147  * relative bearing to the middle is less than our current tolerance
148  */
149 
150  azimuth1 = find_azimuth((double)x[i], (double)y[i],
151  (double)x[i + 1], (double)y[i + 1]);
152  azimuth2 = find_azimuth((double)x[i], (double)y[i],
153  (double)x[i + 2], (double)y[i + 2]);
154 
155  diff1 = fmod(fabs((azimuth2 + 360.0) - azimuth1), 360.0);
156  diff2 = fmod(fabs((azimuth1 + 360.0) - azimuth2), 360.0);
157 
158  if (diff1 <= min_azimuth || diff2 <= min_azimuth) {
159 
160  delete_point(&x[i + 1], &y[i + 1], n - i - 1);
161  --n;
162  ++i;
163  /* either stop deleting points because we're less than 100,
164  or keep deleting points with the same difference as this
165  one (which might make a smaller polygon yet).
166  if (n <= 100) {
167  break;
168  }
169  */
170  }
171  }
172 
173  /* increase minimum azimuth difference for next round */
174  min_azimuth += 1.0;
175  }
176 
177  /*
178  * copy remaining points into a new MapPoly
179  */
180 
181  if (n >= 3) {
182 
183  new = (struct MapPoly *)G_malloc(sizeof(struct MapPoly));
184 
185  /* grab the last text string written as url */
186  new->url = G_store(html.last_text);
187 
188  /* hook up new MapPoly into list */
189  new->next_poly = NULL;
190  *html.tail = new;
191  html.tail = &(new->next_poly);
192 
193  new->num_pts = n;
194  new->x_pts = x;
195  new->y_pts = y;
196  }
197  else {
198  G_free(x);
199  G_free(y);
200  }
201 }
#define NULL
Definition: ccmath.h:32
void G_free(void *)
Free allocated memory.
Definition: gis/alloc.c:150
#define G_malloc(n)
Definition: defs/gis.h:94
char * G_store(const char *)
Copy string to allocated memory.
Definition: strings.c:87
struct html_state html
void html_polygon(const struct path *p)
#define RAD_DEG
int count
int num_pts
Definition: htmlmap.h:19
int MAX_POINTS
Definition: htmlmap.h:32
char * last_text
Definition: htmlmap.h:26
struct MapPoly ** tail
Definition: htmlmap.h:31
int MINIMUM_DIST
Definition: htmlmap.h:34
int BBOX_MINIMUM
Definition: htmlmap.h:33
Definition: path.h:15
int count
Definition: path.h:17
struct vertex * vertices
Definition: path.h:16
double x
Definition: path.h:11
double y
Definition: path.h:11
#define x