GRASS GIS 7 Programmer's Manual  7.5.svn(2017)-r71817
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
break_polygons.c
Go to the documentation of this file.
1 /*!
2  \file lib/vector/Vlib/break_polygons.c
3 
4  \brief Vector library - clean geometry (break polygons)
5 
6  Higher 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 Radim Blazek
14  \author Update for GRASS 7 Markus Metz
15  */
16 
17 #include <stdlib.h>
18 #include <sys/stat.h>
19 #include <fcntl.h>
20 #include <unistd.h>
21 #include <math.h>
22 #include <grass/vector.h>
23 #include <grass/glocale.h>
24 
25 /* TODO: 3D support
26  *
27  * atan2() gives angle from x-axis
28  * this is unambiguous only in 2D, not in 3D
29  *
30  * one possibility would be to store unit vectors of length 1
31  * in struct XPNT
32  * double a1[3], a2[3];
33  *
34  * length = sqrt(dx * dx + dy * dy + dz * dz);
35  * dx /= length; dy /= length; dz /=length;
36  * a1[0] = dx; a1[1] = dy; a1[2] = dz;
37  *
38  * get second dx, dy, dz
39  * length = sqrt(dx * dx + dy * dy + dz * dz);
40  * dx /= length; dy /= length; dz /=length;
41  * a2[0] = dx; a2[1] = dy; a2[2] = dz;
42  *
43  * equal angles
44  * if (a1[0] == a2[0] && a1[1] == a2[1] && a1[2] == a2[2])
45  *
46  * disadvantage: increased memory consumption
47  *
48  * new function Vect_break_faces() ?
49  *
50  */
51 
52 typedef struct
53 {
54  double x, y; /* coords */
55  double a1, a2; /* angles */
56  char cross; /* 0 - do not break, 1 - break */
57  char used; /* 0 - was not used to break line, 1 - was used to break line
58  * this is stored because points are automatically marked as cross, even if not used
59  * later to break lines */
60 } XPNT;
61 
62 typedef struct
63 {
64  double a1, a2; /* angles */
65  char cross; /* 0 - do not break, 1 - break */
66  char used; /* 0 - was not used to break line, 1 - was used to break line
67  * this is stored because points are automatically marked as cross, even if not used
68  * later to break lines */
69 } XPNT2;
70 
71 static int fpoint;
72 
73 /* Function called from RTreeSearch for point found */
74 static int srch(int id, const struct RTree_Rect *rect, void *arg)
75 {
76  fpoint = id;
77 
78  return 0; /* stop searching */
79 }
80 
81 /* function used by binary tree to compare items */
82 static int compare_xpnts(const void *Xpnta, const void *Xpntb)
83 {
84  XPNT *a, *b;
85 
86  a = (XPNT *)Xpnta;
87  b = (XPNT *)Xpntb;
88 
89  if (a->x > b->x)
90  return 1;
91  else if (a->x < b->x)
92  return -1;
93  else {
94  if (a->y > b->y)
95  return 1;
96  else if (a->y < b->y)
97  return -1;
98  else
99  return 0;
100  }
101 
102  G_warning(_("Break polygons: Bug in binary tree!"));
103  return 1;
104 }
105 
106 /* break polygons using a file-based search index */
107 void Vect_break_polygons_file(struct Map_info *Map, int type, struct Map_info *Err)
108 {
109  struct line_pnts *BPoints, *Points;
110  struct line_cats *Cats, *ErrCats;
111  int i, j, k, ret, ltype, broken, last, nlines;
112  int nbreaks;
113  struct RTree *RTree;
114  int npoints, nallpoints, nmarks;
115  XPNT2 XPnt;
116  double dx, dy, a1 = 0, a2 = 0;
117  int closed, last_point;
118  char cross;
119  int fd, xpntfd;
120  char *filename;
121  static struct RTree_Rect rect;
122  static int rect_init = 0;
123 
124  if (!rect_init) {
125  rect.boundary = G_malloc(6 * sizeof(RectReal));
126  rect_init = 6;
127  }
128 
129  G_debug(1, "File-based version of Vect_break_polygons()");
130 
131  filename = G_tempfile();
132  fd = open(filename, O_RDWR | O_CREAT | O_EXCL, 0600);
133  RTree = RTreeCreateTree(fd, 0, 2);
134  remove(filename);
135 
136  filename = G_tempfile();
137  xpntfd = open(filename, O_RDWR | O_CREAT | O_EXCL, 0600);
138  remove(filename);
139 
140  BPoints = Vect_new_line_struct();
141  Points = Vect_new_line_struct();
142  Cats = Vect_new_cats_struct();
143  ErrCats = Vect_new_cats_struct();
144 
145  nlines = Vect_get_num_lines(Map);
146 
147  G_debug(3, "nlines = %d", nlines);
148  /* Go through all lines in vector, and add each point to structure of points,
149  * if such point already exists check angles of segments and if differ mark for break */
150 
151  nmarks = 0;
152  npoints = 1; /* index starts from 1 ! */
153  nallpoints = 0;
154  XPnt.used = 0;
155 
156  G_message(_("Breaking polygons (pass 1: select break points)..."));
157 
158  for (i = 1; i <= nlines; i++) {
159  G_percent(i, nlines, 1);
160  G_debug(3, "i = %d", i);
161  if (!Vect_line_alive(Map, i))
162  continue;
163 
164  ltype = Vect_read_line(Map, Points, Cats, i);
165  if (!(ltype & type))
166  continue;
167 
168  /* This would be confused by duplicate coordinates (angle cannot be calculated) ->
169  * prune line first */
170  Vect_line_prune(Points);
171 
172  /* If first and last point are identical it is close polygon, we don't need to register last point
173  * and we can calculate angle for first.
174  * If first and last point are not identical we have to mark for break both */
175  last_point = Points->n_points - 1;
176  if (Points->x[0] == Points->x[last_point] &&
177  Points->y[0] == Points->y[last_point])
178  closed = 1;
179  else
180  closed = 0;
181 
182  for (j = 0; j < Points->n_points; j++) {
183  G_debug(3, "j = %d", j);
184  nallpoints++;
185 
186  if (j == last_point && closed)
187  continue; /* do not register last of close polygon */
188 
189  /* Box */
190  rect.boundary[0] = Points->x[j];
191  rect.boundary[3] = Points->x[j];
192  rect.boundary[1] = Points->y[j];
193  rect.boundary[4] = Points->y[j];
194  rect.boundary[2] = 0;
195  rect.boundary[5] = 0;
196 
197  /* Already in DB? */
198  fpoint = -1;
199  RTreeSearch(RTree, &rect, srch, NULL);
200  G_debug(3, "fpoint = %d", fpoint);
201 
202  if (Points->n_points <= 2 ||
203  (!closed && (j == 0 || j == last_point))) {
204  cross = 1; /* mark for cross in any case */
205  }
206  else { /* calculate angles */
207  cross = 0;
208  if (j == 0 && closed) { /* closed polygon */
209  dx = Points->x[last_point] - Points->x[0];
210  dy = Points->y[last_point] - Points->y[0];
211  a1 = atan2(dy, dx);
212  dx = Points->x[1] - Points->x[0];
213  dy = Points->y[1] - Points->y[0];
214  a2 = atan2(dy, dx);
215  }
216  else {
217  dx = Points->x[j - 1] - Points->x[j];
218  dy = Points->y[j - 1] - Points->y[j];
219  a1 = atan2(dy, dx);
220  dx = Points->x[j + 1] - Points->x[j];
221  dy = Points->y[j + 1] - Points->y[j];
222  a2 = atan2(dy, dx);
223  }
224  }
225 
226  if (fpoint > 0) { /* Found */
227  /* read point */
228  lseek(xpntfd, (off_t) (fpoint - 1) * sizeof(XPNT2), SEEK_SET);
229  read(xpntfd, &XPnt, sizeof(XPNT2));
230  if (XPnt.cross == 1)
231  continue; /* already marked */
232 
233  /* Check angles */
234  if (cross) {
235  XPnt.cross = 1;
236  nmarks++;
237  /* write point */
238  lseek(xpntfd, (off_t) (fpoint - 1) * sizeof(XPNT2), SEEK_SET);
239  write(xpntfd, &XPnt, sizeof(XPNT2));
240  }
241  else {
242  G_debug(3, "a1 = %f xa1 = %f a2 = %f xa2 = %f", a1,
243  XPnt.a1, a2, XPnt.a2);
244  if ((a1 == XPnt.a1 && a2 == XPnt.a2) ||
245  (a1 == XPnt.a2 && a2 == XPnt.a1)) { /* identical */
246 
247  }
248  else {
249  XPnt.cross = 1;
250  nmarks++;
251  /* write point */
252  lseek(xpntfd, (off_t) (fpoint - 1) * sizeof(XPNT2), SEEK_SET);
253  write(xpntfd, &XPnt, sizeof(XPNT2));
254  }
255  }
256  }
257  else {
258  /* Add to tree and to structure */
259  RTreeInsertRect(&rect, npoints, RTree);
260  if (j == 0 || j == (Points->n_points - 1) ||
261  Points->n_points < 3) {
262  XPnt.a1 = 0;
263  XPnt.a2 = 0;
264  XPnt.cross = 1;
265  nmarks++;
266  }
267  else {
268  XPnt.a1 = a1;
269  XPnt.a2 = a2;
270  XPnt.cross = 0;
271  }
272  /* write point */
273  lseek(xpntfd, (off_t) (npoints - 1) * sizeof(XPNT2), SEEK_SET);
274  write(xpntfd, &XPnt, sizeof(XPNT2));
275 
276  npoints++;
277  }
278  }
279  }
280 
281  nbreaks = 0;
282 
283  /* Second loop through lines (existing when loop is started, no need to process lines written again)
284  * and break at points marked for break */
285 
286  G_message(_("Breaking polygons (pass 2: break at selected points)..."));
287 
288  for (i = 1; i <= nlines; i++) {
289  int n_orig_points;
290 
291  G_percent(i, nlines, 1);
292  G_debug(3, "i = %d", i);
293  if (!Vect_line_alive(Map, i))
294  continue;
295 
296  ltype = Vect_read_line(Map, Points, Cats, i);
297  if (!(ltype & type))
298  continue;
299  if (!(ltype & GV_LINES))
300  continue; /* Nonsense to break points */
301 
302  /* Duplicates would result in zero length lines -> prune line first */
303  n_orig_points = Points->n_points;
304  Vect_line_prune(Points);
305 
306  broken = 0;
307  last = 0;
308  G_debug(3, "n_points = %d", Points->n_points);
309  for (j = 1; j < Points->n_points; j++) {
310  G_debug(3, "j = %d", j);
311  nallpoints++;
312 
313  /* Box */
314  rect.boundary[0] = Points->x[j];
315  rect.boundary[3] = Points->x[j];
316  rect.boundary[1] = Points->y[j];
317  rect.boundary[4] = Points->y[j];
318  rect.boundary[2] = 0;
319  rect.boundary[5] = 0;
320 
321  if (Points->n_points <= 1 ||
322  (j == (Points->n_points - 1) && !broken))
323  break;
324  /* One point only or
325  * last point and line is not broken, do nothing */
326 
327  RTreeSearch(RTree, &rect, srch, NULL);
328  G_debug(3, "fpoint = %d", fpoint);
329 
330  /* read point */
331  lseek(xpntfd, (off_t) (fpoint - 1) * sizeof(XPNT2), SEEK_SET);
332  read(xpntfd, &XPnt, sizeof(XPNT2));
333 
334  /* break or write last segment of broken line */
335  if ((j == (Points->n_points - 1) && broken) ||
336  XPnt.cross) {
337  Vect_reset_line(BPoints);
338  for (k = last; k <= j; k++) {
339  Vect_append_point(BPoints, Points->x[k], Points->y[k],
340  Points->z[k]);
341  }
342 
343  /* Result may collapse to one point */
344  Vect_line_prune(BPoints);
345  if (BPoints->n_points > 1) {
346  ret = Vect_write_line(Map, ltype, BPoints, Cats);
347  G_debug(3,
348  "Line %d written j = %d n_points(orig,pruned) = %d n_points(new) = %d",
349  ret, j, Points->n_points, BPoints->n_points);
350  }
351 
352  if (!broken)
353  Vect_delete_line(Map, i); /* not yet deleted */
354 
355  /* Write points on breaks */
356  if (Err) {
357  if (XPnt.cross && !XPnt.used) {
358  Vect_reset_line(BPoints);
359  Vect_append_point(BPoints, Points->x[j], Points->y[j], 0);
360  Vect_write_line(Err, GV_POINT, BPoints, ErrCats);
361  }
362  if (!XPnt.used) {
363  XPnt.used = 1;
364  /* write point */
365  lseek(xpntfd, (off_t) (fpoint - 1) * sizeof(XPNT2), SEEK_SET);
366  write(xpntfd, &XPnt, sizeof(XPNT2));
367  }
368  }
369 
370  last = j;
371  broken = 1;
372  nbreaks++;
373  }
374  }
375  if (!broken && n_orig_points > Points->n_points) { /* was pruned before -> rewrite */
376  if (Points->n_points > 1) {
377  Vect_rewrite_line(Map, i, ltype, Points, Cats);
378  G_debug(3, "Line %d pruned, npoints = %d", i,
379  Points->n_points);
380  }
381  else {
382  Vect_delete_line(Map, i);
383  G_debug(3, "Line %d was deleted", i);
384  }
385  }
386  else {
387  G_debug(3, "Line %d was not changed", i);
388  }
389  }
390 
391  close(RTree->fd);
392  RTreeDestroyTree(RTree);
393  close(xpntfd);
394  Vect_destroy_line_struct(Points);
395  Vect_destroy_line_struct(BPoints);
397  Vect_destroy_cats_struct(ErrCats);
398  G_verbose_message(_("Breaks: %d"), nbreaks);
399 }
400 
401 
402 /* break polygons using a memory-based search index */
403 void Vect_break_polygons_mem(struct Map_info *Map, int type, struct Map_info *Err)
404 {
405  struct line_pnts *BPoints, *Points;
406  struct line_cats *Cats, *ErrCats;
407  int i, j, k, ret, ltype, broken, last, nlines;
408  int nbreaks;
409  struct RB_TREE *RBTree;
410  int npoints, nallpoints, nmarks;
411  XPNT *XPnt_found, XPnt_search;
412  double dx, dy, a1 = 0, a2 = 0;
413  int closed, last_point, cross;
414 
415  G_debug(1, "Memory-based version of Vect_break_polygons()");
416 
417  RBTree = rbtree_create(compare_xpnts, sizeof(XPNT));
418 
419  BPoints = Vect_new_line_struct();
420  Points = Vect_new_line_struct();
421  Cats = Vect_new_cats_struct();
422  ErrCats = Vect_new_cats_struct();
423 
424  nlines = Vect_get_num_lines(Map);
425 
426  G_debug(3, "nlines = %d", nlines);
427  /* Go through all lines in vector, and add each point to structure of points,
428  * if such point already exists check angles of segments and if differ mark for break */
429 
430  nmarks = 0;
431  npoints = 0;
432  nallpoints = 0;
433  XPnt_search.used = 0;
434 
435  G_message(_("Breaking polygons (pass 1: select break points)..."));
436 
437  for (i = 1; i <= nlines; i++) {
438  G_percent(i, nlines, 1);
439  G_debug(3, "i = %d", i);
440  if (!Vect_line_alive(Map, i))
441  continue;
442 
443  ltype = Vect_read_line(Map, Points, Cats, i);
444  if (!(ltype & type))
445  continue;
446 
447  /* This would be confused by duplicate coordinates (angle cannot be calculated) ->
448  * prune line first */
449  Vect_line_prune(Points);
450 
451  /* If first and last point are identical it is close polygon, we don't need to register last point
452  * and we can calculate angle for first.
453  * If first and last point are not identical we have to mark for break both */
454  last_point = Points->n_points - 1;
455  if (Points->x[0] == Points->x[last_point] &&
456  Points->y[0] == Points->y[last_point])
457  closed = 1;
458  else
459  closed = 0;
460 
461  for (j = 0; j < Points->n_points; j++) {
462  G_debug(3, "j = %d", j);
463  nallpoints++;
464 
465  if (j == last_point && closed)
466  continue; /* do not register last of close polygon */
467 
468  XPnt_search.x = Points->x[j];
469  XPnt_search.y = Points->y[j];
470 
471  /* Already in DB? */
472  XPnt_found = rbtree_find(RBTree, &XPnt_search);
473 
474  if (Points->n_points <= 2 ||
475  (!closed && (j == 0 || j == last_point))) {
476  cross = 1; /* mark for cross in any case */
477  }
478  else { /* calculate angles */
479  cross = 0;
480  if (j == 0 && closed) { /* closed polygon */
481  dx = Points->x[last_point] - Points->x[0];
482  dy = Points->y[last_point] - Points->y[0];
483  a1 = atan2(dy, dx);
484  dx = Points->x[1] - Points->x[0];
485  dy = Points->y[1] - Points->y[0];
486  a2 = atan2(dy, dx);
487  }
488  else {
489  dx = Points->x[j - 1] - Points->x[j];
490  dy = Points->y[j - 1] - Points->y[j];
491  a1 = atan2(dy, dx);
492  dx = Points->x[j + 1] - Points->x[j];
493  dy = Points->y[j + 1] - Points->y[j];
494  a2 = atan2(dy, dx);
495  }
496  }
497 
498  if (XPnt_found) { /* found */
499  if (XPnt_found->cross == 1)
500  continue; /* already marked */
501 
502  /* check angles */
503  if (cross) {
504  XPnt_found->cross = 1;
505  nmarks++;
506  }
507  else {
508  G_debug(3, "a1 = %f xa1 = %f a2 = %f xa2 = %f", a1,
509  XPnt_found->a1, a2, XPnt_found->a2);
510  if ((a1 == XPnt_found->a1 && a2 == XPnt_found->a2) ||
511  (a1 == XPnt_found->a2 && a2 == XPnt_found->a1)) { /* identical */
512 
513  }
514  else {
515  XPnt_found->cross = 1;
516  nmarks++;
517  }
518  }
519  }
520  else {
521  if (j == 0 || j == (Points->n_points - 1) ||
522  Points->n_points < 3) {
523  XPnt_search.a1 = 0;
524  XPnt_search.a2 = 0;
525  XPnt_search.cross = 1;
526  nmarks++;
527  }
528  else {
529  XPnt_search.a1 = a1;
530  XPnt_search.a2 = a2;
531  XPnt_search.cross = 0;
532  }
533 
534  /* Add to tree */
535  rbtree_insert(RBTree, &XPnt_search);
536  npoints++;
537  }
538  }
539  }
540 
541  nbreaks = 0;
542  nallpoints = 0;
543  G_debug(2, "Break polygons: unique vertices: %ld", (long int)RBTree->count);
544 
545  /* uncomment to check if search tree is healthy */
546  /* if (rbtree_debug(RBTree, RBTree->root) == 0)
547  G_warning("Break polygons: RBTree not ok"); */
548 
549  /* Second loop through lines (existing when loop is started, no need to process lines written again)
550  * and break at points marked for break */
551 
552  G_message(_("Breaking polygons (pass 2: break at selected points)..."));
553 
554  for (i = 1; i <= nlines; i++) {
555  int n_orig_points;
556 
557  G_percent(i, nlines, 1);
558  G_debug(3, "i = %d", i);
559  if (!Vect_line_alive(Map, i))
560  continue;
561 
562  ltype = Vect_read_line(Map, Points, Cats, i);
563  if (!(ltype & type))
564  continue;
565  if (!(ltype & GV_LINES))
566  continue; /* Nonsense to break points */
567 
568  /* Duplicates would result in zero length lines -> prune line first */
569  n_orig_points = Points->n_points;
570  Vect_line_prune(Points);
571 
572  broken = 0;
573  last = 0;
574  G_debug(3, "n_points = %d", Points->n_points);
575  for (j = 1; j < Points->n_points; j++) {
576  G_debug(3, "j = %d", j);
577  nallpoints++;
578 
579  if (Points->n_points <= 1 ||
580  (j == (Points->n_points - 1) && !broken))
581  break;
582  /* One point only or
583  * last point and line is not broken, do nothing */
584 
585  XPnt_search.x = Points->x[j];
586  XPnt_search.y = Points->y[j];
587 
588  XPnt_found = rbtree_find(RBTree, &XPnt_search);
589 
590  /* all points must be in the search tree, without duplicates */
591  if (XPnt_found == NULL)
592  G_fatal_error(_("Point not in search tree!"));
593 
594  /* break or write last segment of broken line */
595  if ((j == (Points->n_points - 1) && broken) ||
596  XPnt_found->cross) {
597  Vect_reset_line(BPoints);
598  for (k = last; k <= j; k++) {
599  Vect_append_point(BPoints, Points->x[k], Points->y[k],
600  Points->z[k]);
601  }
602 
603  /* Result may collapse to one point */
604  Vect_line_prune(BPoints);
605  if (BPoints->n_points > 1) {
606  ret = Vect_write_line(Map, ltype, BPoints, Cats);
607  G_debug(3,
608  "Line %d written j = %d n_points(orig,pruned) = %d n_points(new) = %d",
609  ret, j, Points->n_points, BPoints->n_points);
610  }
611 
612  if (!broken)
613  Vect_delete_line(Map, i); /* not yet deleted */
614 
615  /* Write points on breaks */
616  if (Err) {
617  if (XPnt_found->cross && !XPnt_found->used) {
618  Vect_reset_line(BPoints);
619  Vect_append_point(BPoints, Points->x[j], Points->y[j], 0);
620  Vect_write_line(Err, GV_POINT, BPoints, ErrCats);
621  }
622  XPnt_found->used = 1;
623  }
624 
625  last = j;
626  broken = 1;
627  nbreaks++;
628  }
629  }
630  if (!broken && n_orig_points > Points->n_points) { /* was pruned before -> rewrite */
631  if (Points->n_points > 1) {
632  Vect_rewrite_line(Map, i, ltype, Points, Cats);
633  G_debug(3, "Line %d pruned, npoints = %d", i,
634  Points->n_points);
635  }
636  else {
637  Vect_delete_line(Map, i);
638  G_debug(3, "Line %d was deleted", i);
639  }
640  }
641  else {
642  G_debug(3, "Line %d was not changed", i);
643  }
644  }
645 
646  rbtree_destroy(RBTree);
647  Vect_destroy_line_struct(Points);
648  Vect_destroy_line_struct(BPoints);
650  G_verbose_message(_("Breaks: %d"), nbreaks);
651 }
652 
653 /*!
654  \brief Break polygons in vector map
655 
656  Breaks lines specified by type in vector map. Points at
657  intersections may be optionally written to error map. Input vector
658  map must be opened on level 2 for update at least on GV_BUILD_BASE.
659 
660  Function is optimized for closed polygons rings (e.g. imported from
661  OGR) but with clean geometry - adjacent polygons mostly have
662  identical boundary. Function creates database of ALL points in the
663  vector map, and then is looking for those where polygons should be
664  broken. Lines may be broken only at points existing in input
665  vector map!
666 
667  \param Map input map where polygons will be broken
668  \param type type of line to be broken (GV_LINE or GV_BOUNDARY)
669  \param Err vector map where points at intersections will be written or NULL
670  */
671 void Vect_break_polygons(struct Map_info *Map, int type, struct Map_info *Err)
672 {
673  if (getenv("GRASS_VECTOR_LOWMEM"))
674  Vect_break_polygons_file(Map, type, Err);
675  else
676  Vect_break_polygons_mem(Map, type, Err);
677 }
int RTreeInsertRect(struct RTree_Rect *r, int tid, struct RTree *t)
Insert an item into a R*-Tree.
double RectReal
Definition: rtree.h:28
void * rbtree_find(struct RB_TREE *tree, const void *data)
Definition: rbtree.c:243
void G_verbose_message(const char *msg,...)
Print a message to stderr but only if module is in verbose mode.
Definition: gis/error.c:108
off_t Vect_rewrite_line(struct Map_info *Map, off_t line, int type, const struct line_pnts *points, const struct line_cats *cats)
Rewrites existing feature (topological level required)
void RTreeDestroyTree(struct RTree *t)
Destroy an R*-Tree.
void Vect_break_polygons(struct Map_info *Map, int type, struct Map_info *Err)
Break polygons in vector map.
struct line_pnts * Vect_new_line_struct()
Creates and initializes a line_pnts structure.
Definition: line.c:45
off_t Vect_write_line(struct Map_info *Map, int type, const struct line_pnts *points, const struct line_cats *cats)
Writes a new feature.
int RTreeSearch(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb, void *cbarg)
Search an R*-Tree.
int n_points
Number of points.
Definition: dig_structs.h:1692
int Vect_line_alive(const struct Map_info *Map, int line)
Check if feature is alive or dead (topological level required)
void Vect_destroy_line_struct(struct line_pnts *p)
Frees all memory associated with a line_pnts structure, including the structure itself.
Definition: line.c:77
char * G_tempfile(void)
Returns a temporary file name.
Definition: tempfile.c:62
void rbtree_destroy(struct RB_TREE *tree)
Definition: rbtree.c:520
struct RB_TREE * rbtree_create(rb_compare_fn *compare, size_t rb_datasize)
Definition: rbtree.c:50
void Vect_destroy_cats_struct(struct line_cats *p)
Frees all memory associated with line_cats structure, including the struct itself.
#define NULL
Definition: ccmath.h:32
int Vect_delete_line(struct Map_info *Map, off_t line)
Delete existing feature (topological level required)
#define x
#define GV_POINT
Feature types used in memory on run time (may change)
Definition: dig_defines.h:182
Definition: rbtree.h:85
int Vect_append_point(struct line_pnts *Points, double x, double y, double z)
Appends one point to the end of a line.
Definition: line.c:149
fd
Definition: d/range.c:69
void G_fatal_error(const char *msg,...)
Print a fatal error message to stderr.
Definition: gis/error.c:159
Feature category info.
Definition: dig_structs.h:1702
void Vect_break_polygons_mem(struct Map_info *Map, int type, struct Map_info *Err)
double * x
Array of X coordinates.
Definition: dig_structs.h:1680
Feature geometry info - coordinates.
Definition: dig_structs.h:1675
size_t count
Definition: rbtree.h:89
double b
Definition: r_raster.c:39
void Vect_break_polygons_file(struct Map_info *Map, int type, struct Map_info *Err)
int G_debug(int level, const char *msg,...)
Print debugging message.
Definition: debug.c:65
void G_percent(long n, long d, int s)
Print percent complete messages.
Definition: percent.c:62
int fd
Definition: rtree.h:131
Vector map info.
Definition: dig_structs.h:1259
double * y
Array of Y coordinates.
Definition: dig_structs.h:1684
RectReal * boundary
Definition: rtree.h:59
struct line_cats * Vect_new_cats_struct()
Creates and initializes line_cats structure.
int Vect_line_prune(struct line_pnts *Points)
Remove duplicate points, i.e. zero length segments.
Definition: line.c:281
plus_t Vect_get_num_lines(const struct Map_info *Map)
Fetch number of features (points, lines, boundaries, centroids) in vector map.
Definition: level_two.c:74
double * z
Array of Z coordinates.
Definition: dig_structs.h:1688
#define _(str)
Definition: glocale.h:13
void G_message(const char *msg,...)
Print a message to stderr.
Definition: gis/error.c:89
int Vect_read_line(const struct Map_info *Map, struct line_pnts *line_p, struct line_cats *line_c, int line)
Read vector feature (topological level required)
void Vect_reset_line(struct line_pnts *Points)
Reset line.
Definition: line.c:130
#define GV_LINES
Definition: dig_defines.h:192
close(fd)
int rbtree_insert(struct RB_TREE *tree, void *data)
Definition: rbtree.c:74
char * getenv()
Definition: rtree.h:128
void G_warning(const char *msg,...)
Print a warning message to stderr.
Definition: gis/error.c:203
struct RTree * RTreeCreateTree(int fd, off_t rootpos, int ndims)
Create new empty R*-Tree.