GRASS 8 Programmer's Manual  8.5.0dev(2025)-c070206eb1
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);
124  RTreeDestroyTree(Plus->Node_spidx);
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 {
134  RTreeDestroyTree(Plus->Node_spidx);
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);
157  RTreeDestroyTree(Plus->Line_spidx);
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 {
167  RTreeDestroyTree(Plus->Line_spidx);
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);
190  RTreeDestroyTree(Plus->Area_spidx);
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 {
200  RTreeDestroyTree(Plus->Area_spidx);
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);
223  RTreeDestroyTree(Plus->Isle_spidx);
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 {
233  RTreeDestroyTree(Plus->Isle_spidx);
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)
264  RTreeDestroyTree(Plus->Node_spidx);
265  /* Line spidx */
266  if (Plus->Line_spidx)
267  RTreeDestroyTree(Plus->Line_spidx);
268  /* Area spidx */
269  if (Plus->Area_spidx)
270  RTreeDestroyTree(Plus->Area_spidx);
271  /* Isle spidx */
272  if (Plus->Isle_spidx)
273  RTreeDestroyTree(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 int dig_spidx_add_isle(struct Plus_head *Plus, int isle,
395  const struct bound_box *box)
396 {
397  static struct RTree_Rect rect;
398  static int rect_init = 0;
399 
400  if (!rect_init) {
401  /* always 6 sides for 3D */
402  rect.boundary = G_malloc(6 * sizeof(RectReal));
403  rect_init = 6;
404  }
405 
406  G_debug(3, "dig_spidx_add_isle(): isle = %d", isle);
407 
408  rect.boundary[0] = box->W;
409  rect.boundary[1] = box->S;
410  rect.boundary[2] = box->B;
411  rect.boundary[3] = box->E;
412  rect.boundary[4] = box->N;
413  rect.boundary[5] = box->T;
414  RTreeInsertRect(&rect, isle, Plus->Isle_spidx);
415 
416  return 0;
417 }
418 
419 /*!
420  \brief Delete node from spatial index
421 
422  G_fatal_error() called on error.
423 
424  \param Plus pointer to Plus_head structure
425  \param node node id
426 
427  \return 0
428  */
429 int dig_spidx_del_node(struct Plus_head *Plus, int node)
430 {
431  int ret;
432  struct P_node *Node;
433  static struct RTree_Rect rect;
434  static int rect_init = 0;
435 
436  if (!rect_init) {
437  /* always 6 sides for 3D */
438  rect.boundary = G_malloc(6 * sizeof(RectReal));
439  rect_init = 6;
440  }
441 
442  G_debug(3, "dig_spidx_del_node(): node = %d", node);
443 
444  Node = Plus->Node[node];
445 
446  rect.boundary[0] = Node->x;
447  rect.boundary[1] = Node->y;
448  rect.boundary[2] = Node->z;
449  rect.boundary[3] = Node->x;
450  rect.boundary[4] = Node->y;
451  rect.boundary[5] = Node->z;
452 
453  ret = RTreeDeleteRect(&rect, node, Plus->Node_spidx);
454 
455  if (ret)
456  G_fatal_error(_("Unable to delete node %d from spatial index"), node);
457 
458  return 0;
459 }
460 
461 /*!
462  \brief Delete line from spatial index
463 
464  G_fatal_error() called on error.
465 
466  \param Plus pointer to Plus_head structure
467  \param line line id
468  \param x,y,z coordinates
469 
470  \return 0
471  */
472 int dig_spidx_del_line(struct Plus_head *Plus, int line, double x, double y,
473  double z)
474 {
475  int ret;
476  static struct RTree_Rect rect;
477  static int rect_init = 0;
478 
479  if (!rect_init) {
480  /* always 6 sides for 3D */
481  rect.boundary = G_malloc(6 * sizeof(RectReal));
482  rect_init = 6;
483  }
484 
485  G_debug(3, "dig_spidx_del_line(): line = %d", line);
486 
487  rect.boundary[0] = x;
488  rect.boundary[1] = y;
489  rect.boundary[2] = z;
490  rect.boundary[3] = x;
491  rect.boundary[4] = y;
492  rect.boundary[5] = z;
493 
494  ret = RTreeDeleteRect(&rect, line, Plus->Line_spidx);
495 
496  G_debug(3, " ret = %d", ret);
497 
498  if (ret)
499  G_fatal_error(_("Unable to delete line %d from spatial index"), line);
500 
501  return 0;
502 }
503 
504 /*!
505  \brief Delete area from spatial index
506 
507  G_fatal_error() called on error.
508 
509  \param Plus pointer to Plus_head structure
510  \param area area id
511 
512  \return 0
513  */
514 int dig_spidx_del_area(struct Plus_head *Plus, int area)
515 {
516  int ret;
517  struct P_area *Area;
518  struct P_line *Line;
519  struct P_node *Node;
520  struct P_topo_b *topo;
521  static struct RTree_Rect rect;
522  static int rect_init = 0;
523 
524  if (!rect_init) {
525  /* always 6 sides for 3D */
526  rect.boundary = G_malloc(6 * sizeof(RectReal));
527  rect_init = 6;
528  }
529 
530  G_debug(3, "dig_spidx_del_area(): area = %d", area);
531 
532  Area = Plus->Area[area];
533 
534  if (Area == NULL) {
535  G_fatal_error(_("Attempt to delete sidx for dead area"));
536  }
537 
538  Line = Plus->Line[abs(Area->lines[0])];
539  topo = (struct P_topo_b *)Line->topo;
540  Node = Plus->Node[topo->N1];
541 
542  rect.boundary[0] = Node->x;
543  rect.boundary[1] = Node->y;
544  rect.boundary[2] = Node->z;
545  rect.boundary[3] = Node->x;
546  rect.boundary[4] = Node->y;
547  rect.boundary[5] = Node->z;
548 
549  ret = RTreeDeleteRect(&rect, area, Plus->Area_spidx);
550 
551  if (ret)
552  G_fatal_error(_("Unable to delete area %d from spatial index"), area);
553 
554  return 0;
555 }
556 
557 /*!
558  \brief Delete isle from spatial index
559 
560  G_fatal_error() called on error.
561 
562  \param Plus pointer to Plus_head structure
563  \param isle isle id
564 
565  \return 0
566  */
567 int dig_spidx_del_isle(struct Plus_head *Plus, int isle)
568 {
569  int ret;
570  struct P_isle *Isle;
571  struct P_line *Line;
572  struct P_node *Node;
573  struct P_topo_b *topo;
574  static struct RTree_Rect rect;
575  static int rect_init = 0;
576 
577  if (!rect_init) {
578  /* always 6 sides for 3D */
579  rect.boundary = G_malloc(6 * sizeof(RectReal));
580  rect_init = 6;
581  }
582 
583  G_debug(3, "dig_spidx_del_isle(): isle = %d", isle);
584 
585  Isle = Plus->Isle[isle];
586 
587  Line = Plus->Line[abs(Isle->lines[0])];
588  topo = (struct P_topo_b *)Line->topo;
589  Node = Plus->Node[topo->N1];
590 
591  rect.boundary[0] = Node->x;
592  rect.boundary[1] = Node->y;
593  rect.boundary[2] = Node->z;
594  rect.boundary[3] = Node->x;
595  rect.boundary[4] = Node->y;
596  rect.boundary[5] = Node->z;
597 
598  ret = RTreeDeleteRect(&rect, isle, Plus->Isle_spidx);
599 
600  if (ret)
601  G_fatal_error(_("Unable to delete isle %d from spatial index"), isle);
602 
603  return 0;
604 }
605 
606 /* This function is called by RTreeSearch() to add selected node/line/area/isle
607  * to the list */
608 static int _add_item(int id, const struct RTree_Rect *rect UNUSED,
609  struct ilist *list)
610 {
611  G_ilist_add(list, id);
612  return 1;
613 }
614 
615 /* This function is called by RTreeSearch() to add
616  * selected node/line/area/isle to the box list */
617 static int _add_item_with_box(int id, const struct RTree_Rect *rect,
618  struct boxlist *list)
619 {
620  struct bound_box box;
621 
622  box.W = rect->boundary[0];
623  box.S = rect->boundary[1];
624  box.B = rect->boundary[2];
625  box.E = rect->boundary[3];
626  box.N = rect->boundary[4];
627  box.T = rect->boundary[5];
628 
629  dig_boxlist_add(list, id, &box);
630  return 1;
631 }
632 
633 struct boxid {
634  int id;
635  struct bound_box *box;
636 };
637 
638 /* This function is called by RTreeSearch() to add
639  * selected node/line/area/isle to the box list */
640 static int _set_item_box(int id, const struct RTree_Rect *rect,
641  struct boxid *box_id)
642 {
643  if (id == box_id->id) {
644 
645  box_id->box->W = rect->boundary[0];
646  box_id->box->S = rect->boundary[1];
647  box_id->box->B = rect->boundary[2];
648  box_id->box->E = rect->boundary[3];
649  box_id->box->N = rect->boundary[4];
650  box_id->box->T = rect->boundary[5];
651 
652  return 0;
653  }
654 
655  return 1;
656 }
657 
658 /*!
659  \brief Select nodes by bbox
660 
661  \param Plus pointer to Plus_head structure
662  \param box bounding box
663  \param list list of selected lines
664 
665  \return number of selected nodes
666  \return -1 on error
667  */
668 int dig_select_nodes(struct Plus_head *Plus, const struct bound_box *box,
669  struct ilist *list)
670 {
671  static struct RTree_Rect rect;
672  static int rect_init = 0;
673 
674  if (!rect_init) {
675  /* always 6 sides for 3D */
676  rect.boundary = G_malloc(6 * sizeof(RectReal));
677  rect_init = 6;
678  }
679 
680  G_debug(3, "dig_select_nodes()");
681 
682  list->n_values = 0;
683 
684  rect.boundary[0] = box->W;
685  rect.boundary[1] = box->S;
686  rect.boundary[2] = box->B;
687  rect.boundary[3] = box->E;
688  rect.boundary[4] = box->N;
689  rect.boundary[5] = box->T;
690 
691  if (Plus->Spidx_new)
692  RTreeSearch(Plus->Node_spidx, &rect, (SearchHitCallback *)_add_item,
693  list);
694  else
695  rtree_search(Plus->Node_spidx, &rect, (SearchHitCallback *)_add_item,
696  list, Plus);
697 
698  return (list->n_values);
699 }
700 
701 /* This function is called by RTreeSearch() for nodes to find the node id */
702 static int _add_node(int id, const struct RTree_Rect *rect UNUSED, int *node)
703 {
704  *node = id;
705  return 0;
706 }
707 
708 /*!
709  \brief Find one node by coordinates
710 
711  \param Plus pointer to Plus_head structure
712  \param x,y,z coordinates
713 
714  \return number of node
715  \return 0 not found
716  */
717 int dig_find_node(struct Plus_head *Plus, double x, double y, double z)
718 {
719  int node;
720  static struct RTree_Rect rect;
721  static int rect_init = 0;
722 
723  if (!rect_init) {
724  /* always 6 sides for 3D */
725  rect.boundary = G_malloc(6 * sizeof(RectReal));
726  rect_init = 6;
727  }
728 
729  G_debug(3, "dig_find_node()");
730 
731  rect.boundary[0] = x;
732  rect.boundary[1] = y;
733  rect.boundary[2] = z;
734  rect.boundary[3] = x;
735  rect.boundary[4] = y;
736  rect.boundary[5] = z;
737 
738  node = 0;
739  if (Plus->Spidx_new)
740  RTreeSearch(Plus->Node_spidx, &rect, (SearchHitCallback *)_add_node,
741  &node);
742  else
743  rtree_search(Plus->Node_spidx, &rect, (SearchHitCallback *)_add_node,
744  &node, Plus);
745 
746  return node;
747 }
748 
749 /*!
750  \brief Select lines with boxes by box
751 
752  \param Plus pointer to Plus_head structure
753  \param box bounding box
754  \param list boxlist of selected lines
755 
756  \return number of selected lines
757  \return 0 not found
758  */
759 int dig_select_lines(struct Plus_head *Plus, const struct bound_box *box,
760  struct boxlist *list)
761 {
762  static struct RTree_Rect rect;
763  static int rect_init = 0;
764 
765  if (!rect_init) {
766  /* always 6 sides for 3D */
767  rect.boundary = G_malloc(6 * sizeof(RectReal));
768  rect_init = 6;
769  }
770 
771  G_debug(3, "dig_select_lines_with_box()");
772 
773  list->n_values = 0;
774 
775  rect.boundary[0] = box->W;
776  rect.boundary[1] = box->S;
777  rect.boundary[2] = box->B;
778  rect.boundary[3] = box->E;
779  rect.boundary[4] = box->N;
780  rect.boundary[5] = box->T;
781 
782  if (Plus->Spidx_new)
783  RTreeSearch(Plus->Line_spidx, &rect,
784  (SearchHitCallback *)_add_item_with_box, list);
785  else
786  rtree_search(Plus->Line_spidx, &rect,
787  (SearchHitCallback *)_add_item_with_box, list, Plus);
788 
789  return (list->n_values);
790 }
791 
792 /*!
793  \brief Find box for line
794 
795  \param Plus pointer to Plus_head structure
796  \param line line id
797  \param[out] box bounding box
798 
799  \return > 0 bounding box for line found
800  \return 0 not found
801  */
802 int dig_find_line_box(struct Plus_head *Plus, int line, struct bound_box *box)
803 {
804  int ret, type;
805  struct P_line *Line;
806  struct boxid box_id;
807  static struct RTree_Rect rect;
808  static int rect_init = 0;
809 
810  G_debug(3, "dig_find_line_box()");
811 
812  if (!rect_init) {
813  /* always 6 sides for 3D */
814  rect.boundary = G_malloc(6 * sizeof(RectReal));
815  rect_init = 6;
816  }
817 
818  Line = Plus->Line[line];
819  type = Line->type;
820 
821  /* GV_LINES: retrieve box from spatial index */
822  if (type & GV_LINES) {
823  struct P_node *Node = NULL;
824 
825  if (type == GV_LINE) {
826  struct P_topo_l *topo = (struct P_topo_l *)Line->topo;
827 
828  Node = Plus->Node[topo->N1];
829  }
830  else if (type == GV_BOUNDARY) {
831  struct P_topo_b *topo = (struct P_topo_b *)Line->topo;
832 
833  Node = Plus->Node[topo->N1];
834  }
835 
836  rect.boundary[0] = Node->x;
837  rect.boundary[1] = Node->y;
838  rect.boundary[2] = Node->z;
839  rect.boundary[3] = Node->x;
840  rect.boundary[4] = Node->y;
841  rect.boundary[5] = Node->z;
842 
843  box_id.id = line;
844  box_id.box = box;
845 
846  if (Plus->Spidx_new)
847  ret = RTreeSearch(Plus->Line_spidx, &rect,
848  (SearchHitCallback *)_set_item_box, &box_id);
849  else
850  ret =
851  rtree_search(Plus->Line_spidx, &rect,
852  (SearchHitCallback *)_set_item_box, &box_id, Plus);
853 
854  return ret;
855  }
856 
857  /* do not translate this error because
858  * 1. this error is not supposed to happen
859  * 2. the maintainer at which this message is directed prefers english */
860  G_fatal_error("Bug in vector lib: dig_find_line_box() may only be used for "
861  "lines and boundaries.");
862 
863  return 0;
864 }
865 
866 /*!
867  \brief Select areas with boxes by box
868 
869  \param Plus pointer to Plus_head structure
870  \param box bounding box
871  \param list boxlist of selected areas
872 
873  \return number of selected areas
874  */
875 int dig_select_areas(struct Plus_head *Plus, const struct bound_box *box,
876  struct boxlist *list)
877 {
878  static struct RTree_Rect rect;
879  static int rect_init = 0;
880 
881  if (!rect_init) {
882  /* always 6 sides for 3D */
883  rect.boundary = G_malloc(6 * sizeof(RectReal));
884  rect_init = 6;
885  }
886 
887  G_debug(3, "dig_select_areas_with_box()");
888 
889  list->n_values = 0;
890 
891  rect.boundary[0] = box->W;
892  rect.boundary[1] = box->S;
893  rect.boundary[2] = box->B;
894  rect.boundary[3] = box->E;
895  rect.boundary[4] = box->N;
896  rect.boundary[5] = box->T;
897 
898  if (Plus->Spidx_new)
899  RTreeSearch(Plus->Area_spidx, &rect,
900  (SearchHitCallback *)_add_item_with_box, list);
901  else
902  rtree_search(Plus->Area_spidx, &rect,
903  (SearchHitCallback *)_add_item_with_box, list, Plus);
904 
905  return (list->n_values);
906 }
907 
908 /*!
909  \brief Find bounding box for given area
910 
911  \param Plus pointer to Plus_head structure
912  \param area area id
913  \param[out] box bounding box
914 
915  \return > 0 bounding box for area found
916  \return 0 not found
917  */
918 int dig_find_area_box(struct Plus_head *Plus, int area, struct bound_box *box)
919 {
920  int ret;
921  struct boxid box_id;
922  struct P_area *Area;
923  struct P_line *Line;
924  struct P_node *Node;
925  struct P_topo_b *topo;
926  static struct RTree_Rect rect;
927  static int rect_init = 0;
928 
929  G_debug(3, "dig_find_area_box()");
930 
931  if (!rect_init) {
932  /* always 6 sides for 3D */
933  rect.boundary = G_malloc(6 * sizeof(RectReal));
934  rect_init = 6;
935  }
936 
937  Area = Plus->Area[area];
938  Line = Plus->Line[abs(Area->lines[0])];
939  topo = (struct P_topo_b *)Line->topo;
940  Node = Plus->Node[topo->N1];
941 
942  rect.boundary[0] = Node->x;
943  rect.boundary[1] = Node->y;
944  rect.boundary[2] = Node->z;
945  rect.boundary[3] = Node->x;
946  rect.boundary[4] = Node->y;
947  rect.boundary[5] = Node->z;
948 
949  box_id.id = area;
950  box_id.box = box;
951 
952  if (Plus->Spidx_new)
953  ret = RTreeSearch(Plus->Area_spidx, &rect,
954  (SearchHitCallback *)_set_item_box, &box_id);
955  else
956  ret = rtree_search(Plus->Area_spidx, &rect,
957  (SearchHitCallback *)_set_item_box, &box_id, Plus);
958 
959  return ret;
960 }
961 
962 /*!
963  \brief Select isles with boxes by box
964 
965  \param Plus pointer to Plus_head structure
966  \param box bounding box
967  \param list boxlist of selected isles
968 
969  \return number of selected isles
970  */
971 int dig_select_isles(struct Plus_head *Plus, const struct bound_box *box,
972  struct boxlist *list)
973 {
974  static struct RTree_Rect rect;
975  static int rect_init = 0;
976 
977  if (!rect_init) {
978  /* always 6 sides for 3D */
979  rect.boundary = G_malloc(6 * sizeof(RectReal));
980  rect_init = 6;
981  }
982 
983  G_debug(3, "dig_select_areas_with_box()");
984 
985  list->n_values = 0;
986 
987  rect.boundary[0] = box->W;
988  rect.boundary[1] = box->S;
989  rect.boundary[2] = box->B;
990  rect.boundary[3] = box->E;
991  rect.boundary[4] = box->N;
992  rect.boundary[5] = box->T;
993 
994  if (Plus->Spidx_new)
995  RTreeSearch(Plus->Isle_spidx, &rect,
996  (SearchHitCallback *)_add_item_with_box, list);
997  else
998  rtree_search(Plus->Isle_spidx, &rect,
999  (SearchHitCallback *)_add_item_with_box, list, Plus);
1000 
1001  return (list->n_values);
1002 }
1003 
1004 /*!
1005  \brief Find box for isle
1006 
1007  \param Plus pointer to Plus_head structure
1008  \param isle isle id
1009  \param[out] box bounding box
1010 
1011  \return > 0 bounding box for isle found
1012  \return 0 not found
1013  */
1014 int dig_find_isle_box(struct Plus_head *Plus, int isle, struct bound_box *box)
1015 {
1016  int ret;
1017  struct boxid box_id;
1018  struct P_isle *Isle;
1019  struct P_line *Line;
1020  struct P_node *Node;
1021  struct P_topo_b *topo;
1022  static struct RTree_Rect rect;
1023  static int rect_init = 0;
1024 
1025  G_debug(3, "dig_find_isle_box()");
1026 
1027  if (!rect_init) {
1028  /* always 6 sides for 3D */
1029  rect.boundary = G_malloc(6 * sizeof(RectReal));
1030  rect_init = 6;
1031  }
1032 
1033  Isle = Plus->Isle[isle];
1034  Line = Plus->Line[abs(Isle->lines[0])];
1035  topo = (struct P_topo_b *)Line->topo;
1036  Node = Plus->Node[topo->N1];
1037 
1038  rect.boundary[0] = Node->x;
1039  rect.boundary[1] = Node->y;
1040  rect.boundary[2] = Node->z;
1041  rect.boundary[3] = Node->x;
1042  rect.boundary[4] = Node->y;
1043  rect.boundary[5] = Node->z;
1044 
1045  box_id.id = isle;
1046  box_id.box = box;
1047 
1048  if (Plus->Spidx_new)
1049  ret = RTreeSearch(Plus->Isle_spidx, &rect,
1050  (SearchHitCallback *)_set_item_box, &box_id);
1051  else
1052  ret = rtree_search(Plus->Isle_spidx, &rect,
1053  (SearchHitCallback *)_set_item_box, &box_id, Plus);
1054 
1055  return ret;
1056 }
NULL
#define NULL
Definition: ccmath.h:32
G_free
void G_free(void *)
Free allocated memory.
Definition: gis/alloc.c:147
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:1383
dig_boxlist_add
int dig_boxlist_add(struct boxlist *, int, const struct bound_box *)
Definition: vector/diglib/list.c:34
fcntl.h
Header file for msvc/fcntl.c.
open
#define open
Definition: fcntl.h:33
FALSE
#define FALSE
Definition: gis.h:82
UNUSED
#define UNUSED
A macro for an attribute, if attached to a variable, indicating that the variable is not used.
Definition: gis.h:46
_
#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:971
dig_spidx_del_area
int dig_spidx_del_area(struct Plus_head *Plus, int area)
Delete area from spatial index.
Definition: spindex.c:514
dig_spidx_free_areas
void dig_spidx_free_areas(struct Plus_head *Plus)
Reset spatial index for areas.
Definition: spindex.c:177
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:326
dig_spidx_del_isle
int dig_spidx_del_isle(struct Plus_head *Plus, int isle)
Delete isle from spatial index.
Definition: spindex.c:567
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:717
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:1014
dig_spidx_free_lines
void dig_spidx_free_lines(struct Plus_head *Plus)
Free spatial index for lines.
Definition: spindex.c:144
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:875
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:291
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:668
dig_spidx_free_isles
void dig_spidx_free_isles(struct Plus_head *Plus)
Reset spatial index for isles.
Definition: spindex.c:210
dig_spidx_free_nodes
void dig_spidx_free_nodes(struct Plus_head *Plus)
Free spatial index for nodes.
Definition: spindex.c:111
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:360
dig_spidx_del_node
int dig_spidx_del_node(struct Plus_head *Plus, int node)
Delete node from spatial index.
Definition: spindex.c:429
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:472
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:802
dig_spidx_free
void dig_spidx_free(struct Plus_head *Plus)
Free spatial index (nodes, lines, areas, isles)
Definition: spindex.c:243
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:759
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:918
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:394
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:715
list
Definition: manage.h:4
close
#define close
Definition: unistd.h:8
RTreeDeleteRect
int RTreeDeleteRect(struct RTree_Rect *r, int tid, struct RTree *t)
Delete an item from a R*-Tree.
Definition: vector/rtree/index.c:346
RTreeInsertRect
int RTreeInsertRect(struct RTree_Rect *r, int tid, struct RTree *t)
Insert an item into a R*-Tree.
Definition: vector/rtree/index.c:319
RTreeDestroyTree
void RTreeDestroyTree(struct RTree *t)
Destroy an R*-Tree.
Definition: vector/rtree/index.c:226
RTreeSearch
int RTreeSearch(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb, void *cbarg)
Search an R*-Tree.
Definition: vector/rtree/index.c:302
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