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