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 */
Vect_point_in_box(double x,double y,double z,const struct bound_box * Box)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 */
Vect_point_in_box_2d(double x,double y,const struct bound_box * Box)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 */
Vect_box_overlap(const struct bound_box * A,const struct bound_box * B)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 */
Vect_box_copy(struct bound_box * A,const struct bound_box * B)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 */
Vect_box_extend(struct bound_box * A,const struct bound_box * B)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 */
Vect_box_clip(double * x,double * y,double * c_x,double * c_y,const struct bound_box * Box)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 */
Vect_get_line_box(const struct Map_info * Map,int line,struct bound_box * Box)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 */
Vect_get_area_box(const struct Map_info * Map,int area,struct bound_box * Box)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 */
Vect_get_isle_box(const struct Map_info * Map,int isle,struct bound_box * Box)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 */
Vect_get_map_box(const struct Map_info * Map,struct bound_box * Box)394 int Vect_get_map_box(const struct Map_info *Map, struct bound_box *Box)
395 {
396 const struct Plus_head *Plus;
397
398 Plus = &(Map->plus);
399 Vect_box_copy(Box, &(Plus->box));
400
401 if (Vect_level(Map) < 2)
402 return 0;
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 */
Vect_get_map_box1(struct Map_info * Map,struct bound_box * Box)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 */
Vect_region_box(const struct Cell_head * Window,struct bound_box * Box)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 }
479