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