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