GRASS GIS 7 Programmer's Manual  7.9.dev(2021)-e5379bbd7
vector/Vlib/box.c
Go to the documentation of this file.
1 /*!
2  \file lib/vector/Vlib/box.c
3
4  \brief Vector library - bounding box
5
6  Higher level functions for reading/writing/manipulating vectors.
7
8  (C) 2001-2015 by the GRASS Development Team
9
10  This program is free software under the
11  GNU General Public License (>=v2).
12  Read the file COPYING that comes with GRASS
13  for details.
14
16  */
17
18 #include <stdlib.h>
19 #include <grass/vector.h>
20 #include <grass/glocale.h>
21
22 /*!
23  \brief Tests if point is in 3D box
24
25  This function considers 3D point and 3D bounding box.
26
27  \par Example
28
29  \verbatim
30  struct bound_box bbox;
31  bbox.N = 135;
32  bbox.S = 125;
33  bbox.E = 220;
34  bbox.W = 215;
35  bbox.T = 340;
36  bbox.B = 330;
37  Vect_point_in_box(217, 130, 335, &bbox);
38  \endverbatim
39
40  \param x coordinate (W-E direction)
41  \param y coordinate (S-N direction)
42  \param z coordinate (B-T direction)
43  \param Box boundary box
44
45  \returns 1 if point is in box
46  \returns 0 if point is not in box
47  */
48 int Vect_point_in_box(double x, double y, double z, const struct bound_box *Box)
49 {
50
51  return (x >= Box->W && x <= Box->E &&
52  y >= Box->S && y <= Box->N &&
53  z >= Box->B && z <= Box->T);
54 }
55
56 /*!
57  \brief Tests if point is in 2D box
58
59  Only x and y are tested. Top and bottom of the bounding box are ignored.
60
61  \param x coordinate (W-E direction)
62  \param y coordinate (S-N direction)
63  \param Box boundary box (only W, E, S, N are used)
64
65  \returns 1 if point is in box
66  \returns 0 if point is not in box
67  */
68 int Vect_point_in_box_2d(double x, double y, const struct bound_box *Box)
69 {
70
71  return (x >= Box->W && x <= Box->E &&
72  y >= Box->S && y <= Box->N);
73 }
74
75 /*!
76  \brief Tests for overlap of two boxes
77
78  \param A boundary box A
79  \param B boundary box B
80
81  \return 1 boxes overlap
82  \return 0 boxes do not overlap
83  */
84 int Vect_box_overlap(const struct bound_box *A, const struct bound_box *B)
85 {
86
87  if (A->E < B->W || A->W > B->E ||
88  A->N < B->S || A->S > B->N || A->T < B->B || A->B > B->T) {
89  return 0;
90  }
91
92  return 1;
93 }
94
95 /*!
96  \brief Copy box B to box A
97
98  \param A boundary A
99  \param B boundary B
100
101  \return 1
102  */
103 int Vect_box_copy(struct bound_box *A, const struct bound_box *B)
104 {
105
106  A->N = B->N;
107  A->S = B->S;
108  A->E = B->E;
109  A->W = B->W;
110  A->T = B->T;
111  A->B = B->B;
112
113  return 1;
114 }
115
116 /*!
117  \brief Extend box A by box B
118
119  \param A boundary A
120  \param B boundary B
121
122  \return 1
123  */
124 int Vect_box_extend(struct bound_box *A, const struct bound_box *B)
125 {
126
127  if (B->N > A->N)
128  A->N = B->N;
129  if (B->S < A->S)
130  A->S = B->S;
131  if (B->E > A->E)
132  A->E = B->E;
133  if (B->W < A->W)
134  A->W = B->W;
135  if (B->T > A->T)
136  A->T = B->T;
137  if (B->B < A->B)
138  A->B = B->B;
139
140  return 1;
141 }
142
143
144 /*!
145  * \brief Clip coordinates to box, if necessary, lines extending outside of a box.
146  *
147  * A line represented by the coordinates <em>x, y</em> and <em>c_x, c_y</em> is clipped to
148  * the window defined by <em>s</em> (south), <em>n</em> (north), <em>w</em>
149  * (west), and <em>e</em> (east). Note that the following constraints must be
150  * true:
151  * w <e
152  * s <n
153  * The <em>x</em> and <em>c_x</em> are values to be compared to <em>w</em> and
154  * <em>e.</em> The <em>y</em> and <em>c_y</em> are values to be compared to
155  * <em>s</em> and <em>n.</em>
156  * The <em>x</em> and <em>c_x</em> values returned lie between <em>w</em> and
157  * <em>e.</em> The <em>y</em> and <em>c_y</em> values returned lie between
158  * <em>s</em> and <em>n.</em>
159  *
160  * \param x, y coordinates (w, e)
161  * \param c_x,c_y coordinates (s, n)
162  * \param Box boundary box
163  *
164  * \return 1 if any clipping occurred
165  * \return 0 otherwise
166  */
167 int Vect_box_clip(double *x, double *y, double *c_x, double *c_y, const struct bound_box *Box)
168 {
169  int mod;
170
171  mod = 0;
172
173  if (*x < Box->W) {
174  if (*c_x != *x)
175  *y = *y + (Box->W - *x) / (*c_x - *x) * (*c_y - *y);
176  *x = Box->W;
177  mod = 1;
178  }
179  if (*x > Box->E) {
180  if (*c_x != *x)
181  *y = *y + (Box->E - *x) / (*c_x - *x) * (*c_y - *y);
182  *x = Box->E;
183  mod = 1;
184  }
185  if (*c_x < Box->W) {
186  if (*c_x != *x)
187  *c_y = *c_y + (Box->W - *c_x) / (*x - *c_x) * (*y - *c_y);
188  *c_x = Box->W;
189  mod = 1;
190  }
191  if (*c_x > Box->E) {
192  if (*c_x != *x)
193  *c_y = *c_y + (Box->E - *c_x) / (*x - *c_x) * (*y - *c_y);
194  *c_x = Box->E;
195  mod = 1;
196  }
197  if (*y < Box->S) {
198  if (*c_y != *y)
199  *x = *x + (Box->S - *y) / (*c_y - *y) * (*c_x - *x);
200  *y = Box->S;
201  mod = 1;
202  }
203  if (*y > Box->N) {
204  if (*c_y != *y)
205  *x = *x + (Box->N - *y) / (*c_y - *y) * (*c_x - *x);
206  *y = Box->N;
207  mod = 1;
208  }
209  if (*c_y < Box->S) {
210  if (*c_y != *y)
211  *c_x = *c_x + (Box->S - *c_y) / (*y - *c_y) * (*x - *c_x);
212  *c_y = Box->S;
213  mod = 1;
214  }
215  if (*c_y > Box->N) {
216  if (*c_y != *y)
217  *c_x = *c_x + (Box->N - *c_y) / (*y - *c_y) * (*x - *c_x);
218  *c_y = Box->N;
219  mod = 1;
220  }
221
222  return (mod);
223 }
224
225
226 /*!
227  \brief Get bounding box of given feature
228
229  Vector map must be open at topological level and built with level
230  >= GV_BUILD_BASE.
231
232  \param Map vector map
233  \param line feature id
234  \param[out] Box bounding box
235
236  \return 1 on success
237  \return 0 line is dead
238  \return -1 on error
239  */
240 int Vect_get_line_box(const struct Map_info *Map, int line, struct bound_box *Box)
241 {
243  struct P_line *Line;
244  int type;
245  static struct line_pnts *Points = NULL;
246
247  Plus = (struct Plus_head *) &(Map->plus);
248  if (line < 1 || line > Plus->n_lines) {
249  G_warning(_("Attempt to access feature with invalid id (%d)"), line);
250  return -1;
251  }
252
253  Line = Plus->Line[line];
254  if (Line == NULL) { /* dead */
255  Box->N = Box->S = Box->E = Box->W = Box->T = Box->B = 0. / 0.;
256  return 0;
257  }
258
259  type = Line->type;
260
261  /* GV_LINES: retrieve box from spatial index */
262  if (type & GV_LINES) {
263  if (dig_find_line_box(Plus, line, Box) == 0) {
264  G_warning(_("Unable to determine bbox for feature %d"), line);
265  return -1;
266  }
267
268  if (!Vect_is_3d(Map)) {
269  Box->T = PORT_DOUBLE_MAX;
270  Box->B = -PORT_DOUBLE_MAX;
271  }
272
273  return 1;
274  }
275
276  /* all other: read line */
277  if (Points == NULL)
278  Points = Vect_new_line_struct();
279
281  dig_line_box(Points, Box);
282
283  if (!Vect_is_3d(Map)) {
284  Box->T = PORT_DOUBLE_MAX;
285  Box->B = -PORT_DOUBLE_MAX;
286  }
287
288  return 1;
289 }
290
291
292 /*!
293  \brief Get bounding box of area
294
295  Vector map must be open at topological level and built with level
296  >= GV_BUILD_AREAS.
297
298  \param Map vector map
299  \param area area id
300  \param[out] Box bounding box
301
302  \return 1 on success
303  \return 0 area is dead
304  \return -1 on error
305  */
306 int Vect_get_area_box(const struct Map_info *Map, int area, struct bound_box *Box)
307 {
309  struct P_area *Area;
310
311  Plus = (struct Plus_head *) &(Map->plus);
312  if (area < 1 || area > Plus->n_areas) {
313  G_warning(_("Attempt to access area with invalid id (%d)"), area);
314  return -1;
315  }
316
317  Area = Plus->Area[area];
318
319  if (Area == NULL) { /* dead */
320  Box->N = Box->S = Box->E = Box->W = Box->T = Box->B = 0. / 0.;
321  return 0;
322  }
323
324  if (dig_find_area_box(Plus, area, Box) == 0) {
325  G_warning(_("Unable to determine bbox for area %d"), area);
326  return -1;
327  }
328
329  if (!Vect_is_3d(Map)) {
330  Box->T = PORT_DOUBLE_MAX;
331  Box->B = -PORT_DOUBLE_MAX;
332  }
333
334  return 1;
335 }
336
337 /*!
338  \brief Get bounding box of isle
339
340  Vector map must be open at topological level and built with level
341  >= GV_BUILD_AREAS.
342
343  \param Map vector map
344  \param isle isle id
345  \param[out] Box bounding box
346
347  \return 1 on success
349  \return -1 on error
350  */
351 int Vect_get_isle_box(const struct Map_info *Map, int isle, struct bound_box *Box)
352 {
354  struct P_isle *Isle;
355
356  Plus = (struct Plus_head *) &(Map->plus);
357
358  if (isle < 1 || isle > Plus->n_isles) {
359  G_warning(_("Attempt to access area with invalid id (%d)"), isle);
360  return -1;
361  }
362
363  Isle = Plus->Isle[isle];
364
365  if (Isle == NULL) { /* dead */
366  Box->N = Box->S = Box->E = Box->W = Box->T = Box->B = 0. / 0.;
367  return 0;
368  }
369
370  if (dig_find_isle_box(Plus, isle, Box) == 0) {
371  G_warning(_("Unable to determine bbox for isle %d"), isle);
372  return -1;
373  }
374
375  if (!Vect_is_3d(Map)) {
376  Box->T = PORT_DOUBLE_MAX;
377  Box->B = -PORT_DOUBLE_MAX;
378  }
379
380  return 1;
381 }
382
383 /*!
384  \brief Get bounding box of map (all features in the map)
385
386  Requires level 2. On level 1 error code is returned.
387
388  \param Map vector map
389  \param[out] Box bounding box
390
391  \return 1 on success
392  \return 0 on error
393  */
394 int Vect_get_map_box(const struct Map_info *Map, struct bound_box *Box)
395 {
397
398  if (Vect_level(Map) < 2)
399  return 0;
400
401  Plus = &(Map->plus);
402  Vect_box_copy(Box, &(Plus->box));
403
404  return 1;
405 }
406
407 /*!
408  \brief Get bounding box of map on level 1 (all features in the map)
409
410  This subroutine determines bounding box by reading all features
411  sequentially.
412
413  \param Map vector map
414  \param[out] Box bounding box
415
416  \return 1 on success
417  \return 0 on error
418  */
419 int Vect_get_map_box1(struct Map_info *Map, struct bound_box *Box)
420 {
421  int type;
422  int first = TRUE;
423
424  struct line_pnts *Points;
425  struct bound_box line_box;
426
427  Points = Vect_new_line_struct();
428  Vect_rewind(Map);
429  G_verbose_message(_("Topology not available for vector map <%s>. "
430  "Registering primitives..."), Vect_get_full_name(Map));
431  while (TRUE) {
432  /* register line */
433  type = Vect_read_next_line(Map, Points, NULL);
434
435  if (type == -1) {
436  G_warning(_("Unable to read vector map"));
437  return 0;
438  }
439  else if (type == -2) {
440  break;
441  }
442
443  /* update box */
444  dig_line_box(Points, &line_box);
445  if (first == TRUE) {
446  Vect_box_copy(Box, &line_box);
447  first = FALSE;
448  }
449  else
450  Vect_box_extend(Box, &line_box);
451  }
452  Vect_destroy_line_struct(Points);
453
454  return 1;
455 }
456
457
458 /*!
459  \brief Copy region window to bounding box
460
461  \param Window region structure (raster-based)
462  \param[out] Box boundary box (vector-based)
463
464  \return 1 on success
465  \return 0 on error
466  */
467 int Vect_region_box(const struct Cell_head *Window, struct bound_box *Box)
468 {
469
470  Box->N = Window->north;
471  Box->S = Window->south;
472  Box->E = Window->east;
473  Box->W = Window->west;
474  Box->T = PORT_DOUBLE_MAX;
475  Box->B = -PORT_DOUBLE_MAX;
476
477  return 1;
478 }
#define TRUE
Definition: gis.h:59
plus_t n_areas
Current number of areas.
Definition: dig_structs.h:951
int Vect_get_isle_box(const struct Map_info *Map, int isle, struct bound_box *Box)
Get bounding box of isle.
Bounding box.
Definition: dig_structs.h:65
double W
West.
Definition: dig_structs.h:82
Vector geometry.
Definition: dig_structs.h:1574
struct P_line ** Line
Array of vector geometries.
Definition: dig_structs.h:887
2D/3D raster map header (used also for region)
Definition: gis.h:412
float Box[8][3]
Vertices for box.
Definition: gsd_objs.c:1421
Isle (topology) info.
Definition: dig_structs.h:1646
int Vect_get_area_box(const struct Map_info *Map, int area, struct bound_box *Box)
Get bounding box of area.
double west
Extent coordinates (west)
Definition: gis.h:464
struct P_area ** Area
Array of areas.
Definition: dig_structs.h:891
int dig_line_box(const struct line_pnts *, struct bound_box *)
int Vect_region_box(const struct Cell_head *Window, struct bound_box *Box)
Copy region window to bounding box.
double E
East.
Definition: dig_structs.h:78
struct P_isle ** Isle
Array of isles.
Definition: dig_structs.h:895
#define N
Definition: e_intersect.c:923
plus_t n_isles
Current number of isles.
Definition: dig_structs.h:955
int Vect_get_map_box(const struct Map_info *Map, struct bound_box *Box)
Get bounding box of map (all features in the map)
#define NULL
Definition: ccmath.h:32
#define x
plus_t n_lines
Current number of lines.
Definition: dig_structs.h:947
#define W
Definition: ogsf.h:140
double N
North.
Definition: dig_structs.h:70
char type
Line type.
Definition: dig_structs.h:1586
Feature geometry info - coordinates.
Definition: dig_structs.h:1675
double north
Extent coordinates (north)
Definition: gis.h:458
int Vect_get_line_box(const struct Map_info *Map, int line, struct bound_box *Box)
Get bounding box of given feature.
Basic topology-related info.
Definition: dig_structs.h:784
int dig_find_area_box(struct Plus_head *, int, struct bound_box *)
Find bounding box for given area.
Definition: spindex.c:903
#define FALSE
Definition: gis.h:63
struct line_pnts * Vect_new_line_struct(void)
Creates and initializes a line_pnts structure.
Definition: line.c:45
double south
Extent coordinates (south)
Definition: gis.h:460
double B
Bottom.
Definition: dig_structs.h:90
int dig_find_isle_box(struct Plus_head *, int, struct bound_box *)
Find box for isle.
Definition: spindex.c:997
Plus info (topology, version, ...)
Definition: dig_structs.h:1286
double T
Top.
Definition: dig_structs.h:86
struct bound_box box
Bounding box of features.
Definition: dig_structs.h:877
int Vect_rewind(struct Map_info *)
Rewind vector map to cause reads to start at beginning.
Vector map info.
Definition: dig_structs.h:1259
#define PORT_DOUBLE_MAX
Limits for portable types.
Definition: dig_defines.h:66
Area (topology) info.
Definition: dig_structs.h:1605
int Vect_box_copy(struct bound_box *A, const struct bound_box *B)
Copy box B to box A.
int Vect_is_3d(const struct Map_info *)
Check if vector map is 3D.
int Vect_point_in_box_2d(double x, double y, const struct bound_box *Box)
Tests if point is in 2D box.
const char * Vect_get_full_name(const struct Map_info *)
Get fully qualified name of vector map.
int Vect_get_map_box1(struct Map_info *Map, struct bound_box *Box)
Get bounding box of map on level 1 (all features in the map)
int dig_find_line_box(struct Plus_head *, int, struct bound_box *)
Find box for line.
Definition: spindex.c:791
void G_warning(const char *,...) __attribute__((format(printf
double S
South.
Definition: dig_structs.h:74
int Vect_box_clip(double *x, double *y, double *c_x, double *c_y, const struct bound_box *Box)
Clip coordinates to box, if necessary, lines extending outside of a box.
double east
Extent coordinates (east)
Definition: gis.h:462
int Vect_box_overlap(const struct bound_box *A, const struct bound_box *B)
Tests for overlap of two boxes.
#define _(str)
Definition: glocale.h:10
int Vect_box_extend(struct bound_box *A, const struct bound_box *B)
Extend box A by box B.
#define GV_LINES
Definition: dig_defines.h:192
int Vect_read_next_line(const struct Map_info *, struct line_pnts *, struct line_cats *)