GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-8cbe8fef7c
spindex.c
Go to the documentation of this file.
1 /*!
2  \file diglib/spindex.c
3 
4  \brief Vector library - spatial index (lower level functions)
5 
6  Lower level functions for reading/writing/manipulating vectors.
7 
8  (C) 2001-2009 by the GRASS Development Team
9 
10  This program is free software under the GNU General Public License
11  (>=v2). Read the file COPYING that comes with GRASS for details.
12 
13  \author Original author CERL, probably Dave Gerdes
14  \author Update to GRASS 5.7 Radim Blazek
15  \author Update to GRASS 7 Markus Metz
16  */
17 
18 #include <stdlib.h>
19 #include <sys/types.h>
20 #include <sys/stat.h>
21 #include <fcntl.h>
22 #include <unistd.h>
23 #include <string.h>
24 #include <grass/vector.h>
25 #include <grass/glocale.h>
26 
27 /*!
28  \brief Initit spatial index (nodes, lines, areas, isles)
29 
30  \param Plus pointer to Plus_head structure
31 
32  \return 1 OK
33  \return 0 on error
34  */
35 int dig_spidx_init(struct Plus_head *Plus)
36 {
37  int ndims;
38 
39  ndims = (Plus->with_z != 0) ? 3 : 2;
40  Plus->spidx_with_z = (Plus->with_z != 0);
41 
42  G_debug(1, "dig_spidx_init(), %d dims", ndims);
43 
44  if (Plus->Spidx_file) {
45  int fd;
46  char *filename;
47 
48  filename = G_tempfile();
49  fd = open(filename, O_RDWR | O_CREAT | O_EXCL, 0600);
50  Plus->Node_spidx = RTreeCreateTree(fd, 0, ndims);
51  remove(filename);
52 
53  filename = G_tempfile();
54  fd = open(filename, O_RDWR | O_CREAT | O_EXCL, 0600);
55  Plus->Line_spidx = RTreeCreateTree(fd, 0, ndims);
56  remove(filename);
57 
58  filename = G_tempfile();
59  fd = open(filename, O_RDWR | O_CREAT | O_EXCL, 0600);
60  Plus->Area_spidx = RTreeCreateTree(fd, 0, ndims);
61  remove(filename);
62 
63  filename = G_tempfile();
64  fd = open(filename, O_RDWR | O_CREAT | O_EXCL, 0600);
65  Plus->Isle_spidx = RTreeCreateTree(fd, 0, ndims);
66  remove(filename);
67 
68  Plus->Face_spidx = NULL;
69  Plus->Volume_spidx = NULL;
70  Plus->Hole_spidx = NULL;
71 
72  if (!Plus->Spidx_new) {
73  close(Plus->Node_spidx->fd);
74  close(Plus->Line_spidx->fd);
75  close(Plus->Area_spidx->fd);
76  close(Plus->Isle_spidx->fd);
77  }
78  }
79  else {
80  Plus->Node_spidx = RTreeCreateTree(-1, 0, ndims);
81  Plus->Line_spidx = RTreeCreateTree(-1, 0, ndims);
82  Plus->Area_spidx = RTreeCreateTree(-1, 0, ndims);
83  Plus->Isle_spidx = RTreeCreateTree(-1, 0, ndims);
84  Plus->Face_spidx = NULL;
85  Plus->Volume_spidx = NULL;
86  Plus->Hole_spidx = NULL;
87  }
88 
89  Plus->Node_spidx_offset = 0L;
90  Plus->Line_spidx_offset = 0L;
91  Plus->Area_spidx_offset = 0L;
92  Plus->Isle_spidx_offset = 0L;
93  Plus->Face_spidx_offset = 0L;
94  Plus->Volume_spidx_offset = 0L;
95  Plus->Hole_spidx_offset = 0L;
96 
97  Plus->Spidx_built = FALSE;
98 
99  return 1;
100 }
101 
102 /*!
103  \brief Free spatial index for nodes
104 
105  \param Plus pointer to Plus_head structure
106  */
107 void dig_spidx_free_nodes(struct Plus_head *Plus)
108 {
109  int ndims;
110 
111  ndims = Plus->with_z ? 3 : 2;
112 
113  /* Node spidx */
114  if (Plus->Node_spidx->fd > -1) {
115  int fd;
116  char *filename;
117 
118  if (Plus->Spidx_new)
119  close(Plus->Node_spidx->fd);
120  RTreeDestroyTree(Plus->Node_spidx);
121  filename = G_tempfile();
122  fd = open(filename, O_RDWR | O_CREAT | O_EXCL, 0600);
123  Plus->Node_spidx = RTreeCreateTree(fd, 0, ndims);
124  remove(filename);
125  if (!Plus->Spidx_new)
126  close(Plus->Node_spidx->fd);
127  }
128  else {
129  RTreeDestroyTree(Plus->Node_spidx);
130  Plus->Node_spidx = RTreeCreateTree(-1, 0, ndims);
131  }
132 }
133 
134 /*!
135  \brief Free spatial index for lines
136 
137  \param Plus pointer to Plus_head structure
138  */
139 void dig_spidx_free_lines(struct Plus_head *Plus)
140 {
141  int ndims;
142 
143  ndims = Plus->with_z ? 3 : 2;
144 
145  /* Line spidx */
146  if (Plus->Line_spidx->fd > -1) {
147  int fd;
148  char *filename;
149 
150  if (Plus->Spidx_new)
151  close(Plus->Line_spidx->fd);
152  RTreeDestroyTree(Plus->Line_spidx);
153  filename = G_tempfile();
154  fd = open(filename, O_RDWR | O_CREAT | O_EXCL, 0600);
155  Plus->Line_spidx = RTreeCreateTree(fd, 0, ndims);
156  remove(filename);
157  if (!Plus->Spidx_new)
158  close(Plus->Line_spidx->fd);
159  }
160  else {
161  RTreeDestroyTree(Plus->Line_spidx);
162  Plus->Line_spidx = RTreeCreateTree(-1, 0, ndims);
163  }
164 }
165 
166 /*!
167  \brief Reset spatial index for areas
168 
169  \param Plus pointer to Plus_head structure
170  */
171 void dig_spidx_free_areas(struct Plus_head *Plus)
172 {
173  int ndims;
174 
175  ndims = Plus->with_z ? 3 : 2;
176 
177  /* Area spidx */
178  if (Plus->Area_spidx->fd > -1) {
179  int fd;
180  char *filename;
181 
182  if (Plus->Spidx_new)
183  close(Plus->Area_spidx->fd);
184  RTreeDestroyTree(Plus->Area_spidx);
185  filename = G_tempfile();
186  fd = open(filename, O_RDWR | O_CREAT | O_EXCL, 0600);
187  Plus->Area_spidx = RTreeCreateTree(fd, 0, ndims);
188  remove(filename);
189  if (!Plus->Spidx_new)
190  close(Plus->Area_spidx->fd);
191  }
192  else {
193  RTreeDestroyTree(Plus->Area_spidx);
194  Plus->Area_spidx = RTreeCreateTree(-1, 0, ndims);
195  }
196 }
197 
198 /*!
199  \brief Reset spatial index for isles
200 
201  \param Plus pointer to Plus_head structure
202  */
203 void dig_spidx_free_isles(struct Plus_head *Plus)
204 {
205  int ndims;
206 
207  ndims = Plus->with_z ? 3 : 2;
208 
209  /* Isle spidx */
210  if (Plus->Isle_spidx->fd > -1) {
211  int fd;
212  char *filename;
213 
214  if (Plus->Spidx_new)
215  close(Plus->Isle_spidx->fd);
216  RTreeDestroyTree(Plus->Isle_spidx);
217  filename = G_tempfile();
218  fd = open(filename, O_RDWR | O_CREAT | O_EXCL, 0600);
219  Plus->Isle_spidx = RTreeCreateTree(fd, 0, ndims);
220  remove(filename);
221  if (!Plus->Spidx_new)
222  close(Plus->Isle_spidx->fd);
223  }
224  else {
225  RTreeDestroyTree(Plus->Isle_spidx);
226  Plus->Isle_spidx = RTreeCreateTree(-1, 0, ndims);
227  }
228 }
229 
230 /*!
231  \brief Free spatial index (nodes, lines, areas, isles)
232 
233  \param Plus pointer to Plus_head structure
234  */
235 void dig_spidx_free(struct Plus_head *Plus)
236 {
237  /* close tmp files */
238  if (Plus->Spidx_new) {
239  /* Node spidx */
240  if (Plus->Node_spidx->fd > -1)
241  close(Plus->Node_spidx->fd);
242  /* Line spidx */
243  if (Plus->Spidx_new && Plus->Line_spidx->fd > -1)
244  close(Plus->Line_spidx->fd);
245  /* Area spidx */
246  if (Plus->Area_spidx->fd > -1)
247  close(Plus->Area_spidx->fd);
248  /* Isle spidx */
249  if (Plus->Isle_spidx->fd > -1)
250  close(Plus->Isle_spidx->fd);
251  }
252 
253  /* destroy tree structures */
254  /* Node spidx */
255  if (Plus->Node_spidx)
256  RTreeDestroyTree(Plus->Node_spidx);
257  /* Line spidx */
258  if (Plus->Line_spidx)
259  RTreeDestroyTree(Plus->Line_spidx);
260  /* Area spidx */
261  if (Plus->Area_spidx)
262  RTreeDestroyTree(Plus->Area_spidx);
263  /* Isle spidx */
264  if (Plus->Isle_spidx)
265  RTreeDestroyTree(Plus->Isle_spidx);
266 
267  /* 3D future : */
268  /* Face spidx */
269  /* Volume spidx */
270  /* Hole spidx */
271 }
272 
273 /*!
274  \brief Add new node to spatial index
275 
276  \param Plus pointer to Plus_head structure
277  \param node node id
278  \param x,y,z node coordinates
279 
280  \return 1 OK
281  \return 0 on error
282  */
283 int dig_spidx_add_node(struct Plus_head *Plus, int node, double x, double y,
284  double z)
285 {
286  static struct RTree_Rect rect;
287  static int rect_init = 0;
288 
289  if (!rect_init) {
290  /* always 6 sides for 3D */
291  rect.boundary = G_malloc(6 * sizeof(RectReal));
292  rect_init = 6;
293  }
294 
295  G_debug(3, "dig_spidx_add_node(): node = %d, x,y,z = %f, %f, %f", node, x,
296  y, z);
297 
298  rect.boundary[0] = x;
299  rect.boundary[1] = y;
300  rect.boundary[2] = z;
301  rect.boundary[3] = x;
302  rect.boundary[4] = y;
303  rect.boundary[5] = z;
304  RTreeInsertRect(&rect, node, Plus->Node_spidx);
305 
306  return 1;
307 }
308 
309 /*!
310  \brief Add new line to spatial index
311 
312  \param Plus pointer to Plus_head structure
313  \param line line id
314  \param box bounding box
315 
316  \return 0
317  */
318 int dig_spidx_add_line(struct Plus_head *Plus, int line,
319  const struct bound_box *box)
320 {
321  static struct RTree_Rect rect;
322  static int rect_init = 0;
323 
324  if (!rect_init) {
325  /* always 6 sides for 3D */
326  rect.boundary = G_malloc(6 * sizeof(RectReal));
327  rect_init = 6;
328  }
329 
330  G_debug(3, "dig_spidx_add_line(): line = %d", line);
331 
332  rect.boundary[0] = box->W;
333  rect.boundary[1] = box->S;
334  rect.boundary[2] = box->B;
335  rect.boundary[3] = box->E;
336  rect.boundary[4] = box->N;
337  rect.boundary[5] = box->T;
338  RTreeInsertRect(&rect, line, Plus->Line_spidx);
339 
340  return 0;
341 }
342 
343 /*!
344  \brief Add new area to spatial index
345 
346  \param Plus pointer to Plus_head structure
347  \param area area id
348  \param box bounding box
349 
350  \return 0
351  */
352 int dig_spidx_add_area(struct Plus_head *Plus, int area,
353  const struct bound_box *box)
354 {
355  static struct RTree_Rect rect;
356  static int rect_init = 0;
357 
358  if (!rect_init) {
359  /* always 6 sides for 3D */
360  rect.boundary = G_malloc(6 * sizeof(RectReal));
361  rect_init = 6;
362  }
363 
364  G_debug(3, "dig_spidx_add_area(): area = %d", area);
365 
366  rect.boundary[0] = box->W;
367  rect.boundary[1] = box->S;
368  rect.boundary[2] = box->B;
369  rect.boundary[3] = box->E;
370  rect.boundary[4] = box->N;
371  rect.boundary[5] = box->T;
372  RTreeInsertRect(&rect, area, Plus->Area_spidx);
373 
374  return 0;
375 }
376 
377 /*!
378  \brief Add new island to spatial index
379 
380  \param Plus pointer to Plus_head structure
381  \param isle isle id
382  \param box bounding box
383 
384  \return 0
385  */
386 
387 int dig_spidx_add_isle(struct Plus_head *Plus, int isle,
388  const struct bound_box *box)
389 {
390  static struct RTree_Rect rect;
391  static int rect_init = 0;
392 
393  if (!rect_init) {
394  /* always 6 sides for 3D */
395  rect.boundary = G_malloc(6 * sizeof(RectReal));
396  rect_init = 6;
397  }
398 
399  G_debug(3, "dig_spidx_add_isle(): isle = %d", isle);
400 
401  rect.boundary[0] = box->W;
402  rect.boundary[1] = box->S;
403  rect.boundary[2] = box->B;
404  rect.boundary[3] = box->E;
405  rect.boundary[4] = box->N;
406  rect.boundary[5] = box->T;
407  RTreeInsertRect(&rect, isle, Plus->Isle_spidx);
408 
409  return 0;
410 }
411 
412 /*!
413  \brief Delete node from spatial index
414 
415  G_fatal_error() called on error.
416 
417  \param Plus pointer to Plus_head structure
418  \param node node id
419 
420  \return 0
421  */
422 int dig_spidx_del_node(struct Plus_head *Plus, int node)
423 {
424  int ret;
425  struct P_node *Node;
426  static struct RTree_Rect rect;
427  static int rect_init = 0;
428 
429  if (!rect_init) {
430  /* always 6 sides for 3D */
431  rect.boundary = G_malloc(6 * sizeof(RectReal));
432  rect_init = 6;
433  }
434 
435  G_debug(3, "dig_spidx_del_node(): node = %d", node);
436 
437  Node = Plus->Node[node];
438 
439  rect.boundary[0] = Node->x;
440  rect.boundary[1] = Node->y;
441  rect.boundary[2] = Node->z;
442  rect.boundary[3] = Node->x;
443  rect.boundary[4] = Node->y;
444  rect.boundary[5] = Node->z;
445 
446  ret = RTreeDeleteRect(&rect, node, Plus->Node_spidx);
447 
448  if (ret)
449  G_fatal_error(_("Unable to delete node %d from spatial index"), node);
450 
451  return 0;
452 }
453 
454 /*!
455  \brief Delete line from spatial index
456 
457  G_fatal_error() called on error.
458 
459  \param Plus pointer to Plus_head structure
460  \param line line id
461  \param x,y,z coordinates
462 
463  \return 0
464  */
465 int dig_spidx_del_line(struct Plus_head *Plus, int line, double x, double y,
466  double z)
467 {
468  int ret;
469  static struct RTree_Rect rect;
470  static int rect_init = 0;
471 
472  if (!rect_init) {
473  /* always 6 sides for 3D */
474  rect.boundary = G_malloc(6 * sizeof(RectReal));
475  rect_init = 6;
476  }
477 
478  G_debug(3, "dig_spidx_del_line(): line = %d", line);
479 
480  rect.boundary[0] = x;
481  rect.boundary[1] = y;
482  rect.boundary[2] = z;
483  rect.boundary[3] = x;
484  rect.boundary[4] = y;
485  rect.boundary[5] = z;
486 
487  ret = RTreeDeleteRect(&rect, line, Plus->Line_spidx);
488 
489  G_debug(3, " ret = %d", ret);
490 
491  if (ret)
492  G_fatal_error(_("Unable to delete line %d from spatial index"), line);
493 
494  return 0;
495 }
496 
497 /*!
498  \brief Delete area from spatial index
499 
500  G_fatal_error() called on error.
501 
502  \param Plus pointer to Plus_head structure
503  \param area area id
504 
505  \return 0
506  */
507 int dig_spidx_del_area(struct Plus_head *Plus, int area)
508 {
509  int ret;
510  struct P_area *Area;
511  struct P_line *Line;
512  struct P_node *Node;
513  struct P_topo_b *topo;
514  static struct RTree_Rect rect;
515  static int rect_init = 0;
516 
517  if (!rect_init) {
518  /* always 6 sides for 3D */
519  rect.boundary = G_malloc(6 * sizeof(RectReal));
520  rect_init = 6;
521  }
522 
523  G_debug(3, "dig_spidx_del_area(): area = %d", area);
524 
525  Area = Plus->Area[area];
526 
527  if (Area == NULL) {
528  G_fatal_error(_("Attempt to delete sidx for dead area"));
529  }
530 
531  Line = Plus->Line[abs(Area->lines[0])];
532  topo = (struct P_topo_b *)Line->topo;
533  Node = Plus->Node[topo->N1];
534 
535  rect.boundary[0] = Node->x;
536  rect.boundary[1] = Node->y;
537  rect.boundary[2] = Node->z;
538  rect.boundary[3] = Node->x;
539  rect.boundary[4] = Node->y;
540  rect.boundary[5] = Node->z;
541 
542  ret = RTreeDeleteRect(&rect, area, Plus->Area_spidx);
543 
544  if (ret)
545  G_fatal_error(_("Unable to delete area %d from spatial index"), area);
546 
547  return 0;
548 }
549 
550 /*!
551  \brief Delete isle from spatial index
552 
553  G_fatal_error() called on error.
554 
555  \param Plus pointer to Plus_head structure
556  \param isle isle id
557 
558  \return 0
559  */
560 int dig_spidx_del_isle(struct Plus_head *Plus, int isle)
561 {
562  int ret;
563  struct P_isle *Isle;
564  struct P_line *Line;
565  struct P_node *Node;
566  struct P_topo_b *topo;
567  static struct RTree_Rect rect;
568  static int rect_init = 0;
569 
570  if (!rect_init) {
571  /* always 6 sides for 3D */
572  rect.boundary = G_malloc(6 * sizeof(RectReal));
573  rect_init = 6;
574  }
575 
576  G_debug(3, "dig_spidx_del_isle(): isle = %d", isle);
577 
578  Isle = Plus->Isle[isle];
579 
580  Line = Plus->Line[abs(Isle->lines[0])];
581  topo = (struct P_topo_b *)Line->topo;
582  Node = Plus->Node[topo->N1];
583 
584  rect.boundary[0] = Node->x;
585  rect.boundary[1] = Node->y;
586  rect.boundary[2] = Node->z;
587  rect.boundary[3] = Node->x;
588  rect.boundary[4] = Node->y;
589  rect.boundary[5] = Node->z;
590 
591  ret = RTreeDeleteRect(&rect, isle, Plus->Isle_spidx);
592 
593  if (ret)
594  G_fatal_error(_("Unable to delete isle %d from spatial index"), isle);
595 
596  return 0;
597 }
598 
599 /* This function is called by RTreeSearch() to add selected node/line/area/isle
600  * to the list */
601 static int _add_item(int id, const struct RTree_Rect *rect UNUSED,
602  struct ilist *list)
603 {
604  G_ilist_add(list, id);
605  return 1;
606 }
607 
608 /* This function is called by RTreeSearch() to add
609  * selected node/line/area/isle to the box list */
610 static int _add_item_with_box(int id, const struct RTree_Rect *rect,
611  struct boxlist *list)
612 {
613  struct bound_box box;
614 
615  box.W = rect->boundary[0];
616  box.S = rect->boundary[1];
617  box.B = rect->boundary[2];
618  box.E = rect->boundary[3];
619  box.N = rect->boundary[4];
620  box.T = rect->boundary[5];
621 
622  dig_boxlist_add(list, id, &box);
623  return 1;
624 }
625 
626 struct boxid {
627  int id;
628  struct bound_box *box;
629 };
630 
631 /* This function is called by RTreeSearch() to add
632  * selected node/line/area/isle to the box list */
633 static int _set_item_box(int id, const struct RTree_Rect *rect,
634  struct boxid *box_id)
635 {
636  if (id == box_id->id) {
637 
638  box_id->box->W = rect->boundary[0];
639  box_id->box->S = rect->boundary[1];
640  box_id->box->B = rect->boundary[2];
641  box_id->box->E = rect->boundary[3];
642  box_id->box->N = rect->boundary[4];
643  box_id->box->T = rect->boundary[5];
644 
645  return 0;
646  }
647 
648  return 1;
649 }
650 
651 /*!
652  \brief Select nodes by bbox
653 
654  \param Plus pointer to Plus_head structure
655  \param box bounding box
656  \param list list of selected lines
657 
658  \return number of selected nodes
659  \return -1 on error
660  */
661 int dig_select_nodes(struct Plus_head *Plus, const struct bound_box *box,
662  struct ilist *list)
663 {
664  static struct RTree_Rect rect;
665  static int rect_init = 0;
666 
667  if (!rect_init) {
668  /* always 6 sides for 3D */
669  rect.boundary = G_malloc(6 * sizeof(RectReal));
670  rect_init = 6;
671  }
672 
673  G_debug(3, "dig_select_nodes()");
674 
675  list->n_values = 0;
676 
677  rect.boundary[0] = box->W;
678  rect.boundary[1] = box->S;
679  rect.boundary[2] = box->B;
680  rect.boundary[3] = box->E;
681  rect.boundary[4] = box->N;
682  rect.boundary[5] = box->T;
683 
684  if (Plus->Spidx_new)
685  RTreeSearch(Plus->Node_spidx, &rect, (SearchHitCallback *)_add_item,
686  list);
687  else
688  rtree_search(Plus->Node_spidx, &rect, (SearchHitCallback *)_add_item,
689  list, Plus);
690 
691  return (list->n_values);
692 }
693 
694 /* This function is called by RTreeSearch() for nodes to find the node id */
695 static int _add_node(int id, const struct RTree_Rect *rect UNUSED, int *node)
696 {
697  *node = id;
698  return 0;
699 }
700 
701 /*!
702  \brief Find one node by coordinates
703 
704  \param Plus pointer to Plus_head structure
705  \param x,y,z coordinates
706 
707  \return number of node
708  \return 0 not found
709  */
710 int dig_find_node(struct Plus_head *Plus, double x, double y, double z)
711 {
712  int node;
713  static struct RTree_Rect rect;
714  static int rect_init = 0;
715 
716  if (!rect_init) {
717  /* always 6 sides for 3D */
718  rect.boundary = G_malloc(6 * sizeof(RectReal));
719  rect_init = 6;
720  }
721 
722  G_debug(3, "dig_find_node()");
723 
724  rect.boundary[0] = x;
725  rect.boundary[1] = y;
726  rect.boundary[2] = z;
727  rect.boundary[3] = x;
728  rect.boundary[4] = y;
729  rect.boundary[5] = z;
730 
731  node = 0;
732  if (Plus->Spidx_new)
733  RTreeSearch(Plus->Node_spidx, &rect, (SearchHitCallback *)_add_node,
734  &node);
735  else
736  rtree_search(Plus->Node_spidx, &rect, (SearchHitCallback *)_add_node,
737  &node, Plus);
738 
739  return node;
740 }
741 
742 /*!
743  \brief Select lines with boxes by box
744 
745  \param Plus pointer to Plus_head structure
746  \param box bounding box
747  \param list boxlist of selected lines
748 
749  \return number of selected lines
750  \return 0 not found
751  */
752 int dig_select_lines(struct Plus_head *Plus, const struct bound_box *box,
753  struct boxlist *list)
754 {
755  static struct RTree_Rect rect;
756  static int rect_init = 0;
757 
758  if (!rect_init) {
759  /* always 6 sides for 3D */
760  rect.boundary = G_malloc(6 * sizeof(RectReal));
761  rect_init = 6;
762  }
763 
764  G_debug(3, "dig_select_lines_with_box()");
765 
766  list->n_values = 0;
767 
768  rect.boundary[0] = box->W;
769  rect.boundary[1] = box->S;
770  rect.boundary[2] = box->B;
771  rect.boundary[3] = box->E;
772  rect.boundary[4] = box->N;
773  rect.boundary[5] = box->T;
774 
775  if (Plus->Spidx_new)
776  RTreeSearch(Plus->Line_spidx, &rect,
777  (SearchHitCallback *)_add_item_with_box, list);
778  else
779  rtree_search(Plus->Line_spidx, &rect,
780  (SearchHitCallback *)_add_item_with_box, list, Plus);
781 
782  return (list->n_values);
783 }
784 
785 /*!
786  \brief Find box for line
787 
788  \param Plus pointer to Plus_head structure
789  \param line line id
790  \param[out] box bounding box
791 
792  \return > 0 bounding box for line found
793  \return 0 not found
794  */
795 int dig_find_line_box(struct Plus_head *Plus, int line, struct bound_box *box)
796 {
797  int ret, type;
798  struct P_line *Line;
799  struct boxid box_id;
800  static struct RTree_Rect rect;
801  static int rect_init = 0;
802 
803  G_debug(3, "dig_find_line_box()");
804 
805  if (!rect_init) {
806  /* always 6 sides for 3D */
807  rect.boundary = G_malloc(6 * sizeof(RectReal));
808  rect_init = 6;
809  }
810 
811  Line = Plus->Line[line];
812  type = Line->type;
813 
814  /* GV_LINES: retrieve box from spatial index */
815  if (type & GV_LINES) {
816  struct P_node *Node = NULL;
817 
818  if (type == GV_LINE) {
819  struct P_topo_l *topo = (struct P_topo_l *)Line->topo;
820 
821  Node = Plus->Node[topo->N1];
822  }
823  else if (type == GV_BOUNDARY) {
824  struct P_topo_b *topo = (struct P_topo_b *)Line->topo;
825 
826  Node = Plus->Node[topo->N1];
827  }
828 
829  rect.boundary[0] = Node->x;
830  rect.boundary[1] = Node->y;
831  rect.boundary[2] = Node->z;
832  rect.boundary[3] = Node->x;
833  rect.boundary[4] = Node->y;
834  rect.boundary[5] = Node->z;
835 
836  box_id.id = line;
837  box_id.box = box;
838 
839  if (Plus->Spidx_new)
840  ret = RTreeSearch(Plus->Line_spidx, &rect,
841  (SearchHitCallback *)_set_item_box, &box_id);
842  else
843  ret =
844  rtree_search(Plus->Line_spidx, &rect,
845  (SearchHitCallback *)_set_item_box, &box_id, Plus);
846 
847  return ret;
848  }
849 
850  /* do not translate this error because
851  * 1. this error is not supposed to happen
852  * 2. the maintainer at which this message is directed prefers english */
853  G_fatal_error("Bug in vector lib: dig_find_line_box() may only be used for "
854  "lines and boundaries.");
855 
856  return 0;
857 }
858 
859 /*!
860  \brief Select areas with boxes by box
861 
862  \param Plus pointer to Plus_head structure
863  \param box bounding box
864  \param list boxlist of selected areas
865 
866  \return number of selected areas
867  */
868 int dig_select_areas(struct Plus_head *Plus, const struct bound_box *box,
869  struct boxlist *list)
870 {
871  static struct RTree_Rect rect;
872  static int rect_init = 0;
873 
874  if (!rect_init) {
875  /* always 6 sides for 3D */
876  rect.boundary = G_malloc(6 * sizeof(RectReal));
877  rect_init = 6;
878  }
879 
880  G_debug(3, "dig_select_areas_with_box()");
881 
882  list->n_values = 0;
883 
884  rect.boundary[0] = box->W;
885  rect.boundary[1] = box->S;
886  rect.boundary[2] = box->B;
887  rect.boundary[3] = box->E;
888  rect.boundary[4] = box->N;
889  rect.boundary[5] = box->T;
890 
891  if (Plus->Spidx_new)
892  RTreeSearch(Plus->Area_spidx, &rect,
893  (SearchHitCallback *)_add_item_with_box, list);
894  else
895  rtree_search(Plus->Area_spidx, &rect,
896  (SearchHitCallback *)_add_item_with_box, list, Plus);
897 
898  return (list->n_values);
899 }
900 
901 /*!
902  \brief Find bounding box for given area
903 
904  \param Plus pointer to Plus_head structure
905  \param area area id
906  \param[out] box bounding box
907 
908  \return > 0 bounding box for area found
909  \return 0 not found
910  */
911 int dig_find_area_box(struct Plus_head *Plus, int area, struct bound_box *box)
912 {
913  int ret;
914  struct boxid box_id;
915  struct P_area *Area;
916  struct P_line *Line;
917  struct P_node *Node;
918  struct P_topo_b *topo;
919  static struct RTree_Rect rect;
920  static int rect_init = 0;
921 
922  G_debug(3, "dig_find_area_box()");
923 
924  if (!rect_init) {
925  /* always 6 sides for 3D */
926  rect.boundary = G_malloc(6 * sizeof(RectReal));
927  rect_init = 6;
928  }
929 
930  Area = Plus->Area[area];
931  Line = Plus->Line[abs(Area->lines[0])];
932  topo = (struct P_topo_b *)Line->topo;
933  Node = Plus->Node[topo->N1];
934 
935  rect.boundary[0] = Node->x;
936  rect.boundary[1] = Node->y;
937  rect.boundary[2] = Node->z;
938  rect.boundary[3] = Node->x;
939  rect.boundary[4] = Node->y;
940  rect.boundary[5] = Node->z;
941 
942  box_id.id = area;
943  box_id.box = box;
944 
945  if (Plus->Spidx_new)
946  ret = RTreeSearch(Plus->Area_spidx, &rect,
947  (SearchHitCallback *)_set_item_box, &box_id);
948  else
949  ret = rtree_search(Plus->Area_spidx, &rect,
950  (SearchHitCallback *)_set_item_box, &box_id, Plus);
951 
952  return ret;
953 }
954 
955 /*!
956  \brief Select isles with boxes by box
957 
958  \param Plus pointer to Plus_head structure
959  \param box bounding box
960  \param list boxlist of selected isles
961 
962  \return number of selected isles
963  */
964 int dig_select_isles(struct Plus_head *Plus, const struct bound_box *box,
965  struct boxlist *list)
966 {
967  static struct RTree_Rect rect;
968  static int rect_init = 0;
969 
970  if (!rect_init) {
971  /* always 6 sides for 3D */
972  rect.boundary = G_malloc(6 * sizeof(RectReal));
973  rect_init = 6;
974  }
975 
976  G_debug(3, "dig_select_areas_with_box()");
977 
978  list->n_values = 0;
979 
980  rect.boundary[0] = box->W;
981  rect.boundary[1] = box->S;
982  rect.boundary[2] = box->B;
983  rect.boundary[3] = box->E;
984  rect.boundary[4] = box->N;
985  rect.boundary[5] = box->T;
986 
987  if (Plus->Spidx_new)
988  RTreeSearch(Plus->Isle_spidx, &rect,
989  (SearchHitCallback *)_add_item_with_box, list);
990  else
991  rtree_search(Plus->Isle_spidx, &rect,
992  (SearchHitCallback *)_add_item_with_box, list, Plus);
993 
994  return (list->n_values);
995 }
996 
997 /*!
998  \brief Find box for isle
999 
1000  \param Plus pointer to Plus_head structure
1001  \param isle isle id
1002  \param[out] box bounding box
1003 
1004  \return > 0 bounding box for isle found
1005  \return 0 not found
1006  */
1007 int dig_find_isle_box(struct Plus_head *Plus, int isle, struct bound_box *box)
1008 {
1009  int ret;
1010  struct boxid box_id;
1011  struct P_isle *Isle;
1012  struct P_line *Line;
1013  struct P_node *Node;
1014  struct P_topo_b *topo;
1015  static struct RTree_Rect rect;
1016  static int rect_init = 0;
1017 
1018  G_debug(3, "dig_find_isle_box()");
1019 
1020  if (!rect_init) {
1021  /* always 6 sides for 3D */
1022  rect.boundary = G_malloc(6 * sizeof(RectReal));
1023  rect_init = 6;
1024  }
1025 
1026  Isle = Plus->Isle[isle];
1027  Line = Plus->Line[abs(Isle->lines[0])];
1028  topo = (struct P_topo_b *)Line->topo;
1029  Node = Plus->Node[topo->N1];
1030 
1031  rect.boundary[0] = Node->x;
1032  rect.boundary[1] = Node->y;
1033  rect.boundary[2] = Node->z;
1034  rect.boundary[3] = Node->x;
1035  rect.boundary[4] = Node->y;
1036  rect.boundary[5] = Node->z;
1037 
1038  box_id.id = isle;
1039  box_id.box = box;
1040 
1041  if (Plus->Spidx_new)
1042  ret = RTreeSearch(Plus->Isle_spidx, &rect,
1043  (SearchHitCallback *)_set_item_box, &box_id);
1044  else
1045  ret = rtree_search(Plus->Isle_spidx, &rect,
1046  (SearchHitCallback *)_set_item_box, &box_id, Plus);
1047 
1048  return ret;
1049 }
NULL
#define NULL
Definition: ccmath.h:32
G_fatal_error
void void void void G_fatal_error(const char *,...) __attribute__((format(printf
G_malloc
#define G_malloc(n)
Definition: defs/gis.h:94
G_tempfile
char * G_tempfile(void)
Returns a temporary file name.
Definition: tempfile.c:62
G_ilist_add
void G_ilist_add(struct ilist *, int)
Add item to ilist.
Definition: ilist.c:78
G_debug
int G_debug(int, const char *,...) __attribute__((format(printf
GV_LINE
#define GV_LINE
Definition: dig_defines.h:184
GV_LINES
#define GV_LINES
Definition: dig_defines.h:193
GV_BOUNDARY
#define GV_BOUNDARY
Definition: dig_defines.h:185
rtree_search
int rtree_search(struct RTree *, struct RTree_Rect *, SearchHitCallback, void *, struct Plus_head *)
Search spatial index file Can't use regular RTreeSearch() here because sidx must be read with dig__fr...
Definition: spindex_rw.c:1387
dig_boxlist_add
int dig_boxlist_add(struct boxlist *, int, const struct bound_box *)
Definition: vector/diglib/list.c:34
FALSE
#define FALSE
Definition: gis.h:83
UNUSED
#define UNUSED
A macro for an attribute, if attached to a variable, indicating that the variable is not used.
Definition: gis.h:47
_
#define _(str)
Definition: glocale.h:10
SearchHitCallback
int SearchHitCallback(int id, const struct RTree_Rect *rect, void *arg)
Definition: rtree.h:86
RectReal
double RectReal
Definition: rtree.h:26
dig_select_isles
int dig_select_isles(struct Plus_head *Plus, const struct bound_box *box, struct boxlist *list)
Select isles with boxes by box.
Definition: spindex.c:964
dig_spidx_del_area
int dig_spidx_del_area(struct Plus_head *Plus, int area)
Delete area from spatial index.
Definition: spindex.c:507
dig_spidx_free_areas
void dig_spidx_free_areas(struct Plus_head *Plus)
Reset spatial index for areas.
Definition: spindex.c:171
dig_spidx_add_line
int dig_spidx_add_line(struct Plus_head *Plus, int line, const struct bound_box *box)
Add new line to spatial index.
Definition: spindex.c:318
dig_spidx_del_isle
int dig_spidx_del_isle(struct Plus_head *Plus, int isle)
Delete isle from spatial index.
Definition: spindex.c:560
dig_find_node
int dig_find_node(struct Plus_head *Plus, double x, double y, double z)
Find one node by coordinates.
Definition: spindex.c:710
dig_find_isle_box
int dig_find_isle_box(struct Plus_head *Plus, int isle, struct bound_box *box)
Find box for isle.
Definition: spindex.c:1007
dig_spidx_free_lines
void dig_spidx_free_lines(struct Plus_head *Plus)
Free spatial index for lines.
Definition: spindex.c:139
dig_select_areas
int dig_select_areas(struct Plus_head *Plus, const struct bound_box *box, struct boxlist *list)
Select areas with boxes by box.
Definition: spindex.c:868
dig_spidx_add_node
int dig_spidx_add_node(struct Plus_head *Plus, int node, double x, double y, double z)
Add new node to spatial index.
Definition: spindex.c:283
dig_select_nodes
int dig_select_nodes(struct Plus_head *Plus, const struct bound_box *box, struct ilist *list)
Select nodes by bbox.
Definition: spindex.c:661
dig_spidx_free_isles
void dig_spidx_free_isles(struct Plus_head *Plus)
Reset spatial index for isles.
Definition: spindex.c:203
dig_spidx_free_nodes
void dig_spidx_free_nodes(struct Plus_head *Plus)
Free spatial index for nodes.
Definition: spindex.c:107
dig_spidx_add_area
int dig_spidx_add_area(struct Plus_head *Plus, int area, const struct bound_box *box)
Add new area to spatial index.
Definition: spindex.c:352
dig_spidx_del_node
int dig_spidx_del_node(struct Plus_head *Plus, int node)
Delete node from spatial index.
Definition: spindex.c:422
dig_spidx_del_line
int dig_spidx_del_line(struct Plus_head *Plus, int line, double x, double y, double z)
Delete line from spatial index.
Definition: spindex.c:465
dig_find_line_box
int dig_find_line_box(struct Plus_head *Plus, int line, struct bound_box *box)
Find box for line.
Definition: spindex.c:795
dig_spidx_free
void dig_spidx_free(struct Plus_head *Plus)
Free spatial index (nodes, lines, areas, isles)
Definition: spindex.c:235
dig_spidx_init
int dig_spidx_init(struct Plus_head *Plus)
Initit spatial index (nodes, lines, areas, isles)
Definition: spindex.c:35
dig_select_lines
int dig_select_lines(struct Plus_head *Plus, const struct bound_box *box, struct boxlist *list)
Select lines with boxes by box.
Definition: spindex.c:752
dig_find_area_box
int dig_find_area_box(struct Plus_head *Plus, int area, struct bound_box *box)
Find bounding box for given area.
Definition: spindex.c:911
dig_spidx_add_isle
int dig_spidx_add_isle(struct Plus_head *Plus, int isle, const struct bound_box *box)
Add new island to spatial index.
Definition: spindex.c:387
if
if(!(yy_init))
Definition: sqlp.yy.c:775
P_area
Area (topology) info.
Definition: dig_structs.h:1583
P_area::lines
plus_t * lines
List of boundary lines.
Definition: dig_structs.h:1598
P_isle
Isle (topology) info.
Definition: dig_structs.h:1623
P_isle::lines
plus_t * lines
List of boundary lines.
Definition: dig_structs.h:1638
P_line
Vector geometry.
Definition: dig_structs.h:1553
P_line::type
char type
Line type.
Definition: dig_structs.h:1564
P_line::topo
void * topo
Topology info.
Definition: dig_structs.h:1577
P_node
Topological feature - node.
Definition: dig_structs.h:1433
P_node::x
double x
X coordinate.
Definition: dig_structs.h:1437
P_node::z
double z
Z coordinate (used only for 3D data)
Definition: dig_structs.h:1445
P_node::y
double y
Y coordinate.
Definition: dig_structs.h:1441
P_topo_b
Boundary topology.
Definition: dig_structs.h:1492
P_topo_b::N1
plus_t N1
Start node.
Definition: dig_structs.h:1496
P_topo_l
Line topology.
Definition: dig_structs.h:1478
P_topo_l::N1
plus_t N1
Start node.
Definition: dig_structs.h:1482
Plus_head
Basic topology-related info.
Definition: dig_structs.h:769
Plus_head::Spidx_built
int Spidx_built
Spatial index built?
Definition: dig_structs.h:1037
Plus_head::Area_spidx_offset
off_t Area_spidx_offset
Offset of areas in sidx file.
Definition: dig_structs.h:1067
Plus_head::with_z
int with_z
2D/3D vector data
Definition: dig_structs.h:786
Plus_head::Isle_spidx_offset
off_t Isle_spidx_offset
Offset of isles in sidx file.
Definition: dig_structs.h:1071
Plus_head::Line
struct P_line ** Line
Array of vector geometries.
Definition: dig_structs.h:871
Plus_head::Hole_spidx_offset
off_t Hole_spidx_offset
Offset of holes in sidx file.
Definition: dig_structs.h:1083
Plus_head::Spidx_new
int Spidx_new
Build new spatial index.
Definition: dig_structs.h:1043
Plus_head::Isle_spidx
struct RTree * Isle_spidx
Isles spatial index.
Definition: dig_structs.h:1100
Plus_head::Face_spidx_offset
off_t Face_spidx_offset
Offset of faces in sidx file.
Definition: dig_structs.h:1075
Plus_head::Area_spidx
struct RTree * Area_spidx
Area spatial index.
Definition: dig_structs.h:1096
Plus_head::Spidx_file
int Spidx_file
Build new spatial index in file.
Definition: dig_structs.h:1049
Plus_head::Volume_spidx_offset
off_t Volume_spidx_offset
Offset of volumes in sidx file.
Definition: dig_structs.h:1079
Plus_head::Line_spidx
struct RTree * Line_spidx
Line spatial index.
Definition: dig_structs.h:1092
Plus_head::Area
struct P_area ** Area
Array of areas.
Definition: dig_structs.h:875
Plus_head::Volume_spidx
struct RTree * Volume_spidx
Volumes spatial index.
Definition: dig_structs.h:1108
Plus_head::spidx_with_z
int spidx_with_z
2D/3D spatial index
Definition: dig_structs.h:793
Plus_head::Face_spidx
struct RTree * Face_spidx
Faces spatial index.
Definition: dig_structs.h:1104
Plus_head::Line_spidx_offset
off_t Line_spidx_offset
Offset of lines in sidx file.
Definition: dig_structs.h:1063
Plus_head::Node_spidx
struct RTree * Node_spidx
Node spatial index.
Definition: dig_structs.h:1088
Plus_head::Isle
struct P_isle ** Isle
Array of isles.
Definition: dig_structs.h:879
Plus_head::Node
struct P_node ** Node
Array of nodes.
Definition: dig_structs.h:867
Plus_head::Node_spidx_offset
off_t Node_spidx_offset
Offset of nodes in sidx file.
Definition: dig_structs.h:1059
Plus_head::Hole_spidx
struct RTree * Hole_spidx
Holes spatial index.
Definition: dig_structs.h:1112
RTree_Rect
Definition: rtree.h:54
RTree_Rect::boundary
RectReal * boundary
Definition: rtree.h:55
RTree::fd
int fd
Definition: rtree.h:125
bound_box
Bounding box.
Definition: dig_structs.h:64
bound_box::W
double W
West.
Definition: dig_structs.h:80
bound_box::T
double T
Top.
Definition: dig_structs.h:84
bound_box::S
double S
South.
Definition: dig_structs.h:72
bound_box::N
double N
North.
Definition: dig_structs.h:68
bound_box::E
double E
East.
Definition: dig_structs.h:76
bound_box::B
double B
Bottom.
Definition: dig_structs.h:88
boxlist
List of bounding boxes with id.
Definition: dig_structs.h:1723
ilist
List of integers.
Definition: gis.h:706
list
Definition: manage.h:4
RTreeDeleteRect
int RTreeDeleteRect(struct RTree_Rect *r, int tid, struct RTree *t)
Delete an item from a R*-Tree.
Definition: vector/rtree/index.c:347
RTreeInsertRect
int RTreeInsertRect(struct RTree_Rect *r, int tid, struct RTree *t)
Insert an item into a R*-Tree.
Definition: vector/rtree/index.c:320
RTreeDestroyTree
void RTreeDestroyTree(struct RTree *t)
Destroy an R*-Tree.
Definition: vector/rtree/index.c:227
RTreeSearch
int RTreeSearch(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb, void *cbarg)
Search an R*-Tree.
Definition: vector/rtree/index.c:303
RTreeCreateTree
struct RTree * RTreeCreateTree(int fd, off_t rootpos, int ndims)
Create new empty R*-Tree.
Definition: vector/rtree/index.c:61
x
#define x