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 
15  \author Radim Blazek
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 {
242  struct Plus_head *Plus;
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 
280  Vect_read_line(Map, Points, NULL, line);
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 {
308  struct Plus_head *Plus;
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
348  \return 0 isle is dead / bounding box not found
349  \return -1 on error
350  */
351 int Vect_get_isle_box(const struct Map_info *Map, int isle, struct bound_box *Box)
352 {
353  struct Plus_head *Plus;
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 {
396  const struct Plus_head *Plus;
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
struct Plus_head plus
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 *)
Read next vector feature.
void Vect_destroy_line_struct(struct line_pnts *)
Frees all memory associated with a line_pnts structure, including the structure itself.
Definition: line.c:77
void void G_verbose_message(const char *,...) __attribute__((format(printf
int Vect_read_line(const struct Map_info *, struct line_pnts *, struct line_cats *, int)
Read vector feature (topological level required)
int Vect_level(const struct Map_info *)
Returns level that Map is opened at.
Definition: level.c:29
int Vect_point_in_box(double x, double y, double z, const struct bound_box *Box)
Tests if point is in 3D box.