GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
Vlib/snap.c
Go to the documentation of this file.
1 /*!
2  * \file lib/vector/Vlib/snap.c
3  *
4  * \brief Vector library - Clean vector map (snap lines)
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 to 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 #include <grass/kdtree.h>
25 
26 /* translate segment to box and back */
27 #define X1W 0x01 /* x1 is West, x2 East */
28 #define Y1S 0x02 /* y1 is South, y2 North */
29 #define Z1B 0x04 /* z1 is Bottom, z2 Top */
30 
31 /* Vertex */
32 typedef struct
33 {
34  double x, y, z;
35  int anchor; /* 0 - anchor, do not snap this point, that means snap others to this */
36  /* >0 - index of anchor to which snap this point */
37  /* -1 - init value */
38 } XPNT;
39 
40 typedef struct
41 {
42  int anchor;
43  double along;
44 } NEW;
45 
46 /* for qsort */
47 static int sort_new(const void *pa, const void *pb)
48 {
49  NEW *p1 = (NEW *) pa;
50  NEW *p2 = (NEW *) pb;
51 
52  return (p1->along < p2->along ? -1 : (p1->along > p2->along));
53 
54  /*
55  if (p1->along < p2->along)
56  return -1;
57  if (p1->along > p2->along)
58  return 1;
59  return 1;
60  */
61 }
62 
63 typedef struct
64 {
65  double x, y, z, along;
66 } NEW2;
67 
68 /* for qsort */
69 static int sort_new2(const void *pa, const void *pb)
70 {
71  NEW2 *p1 = (NEW2 *) pa;
72  NEW2 *p2 = (NEW2 *) pb;
73 
74  return (p1->along < p2->along ? -1 : (p1->along > p2->along));
75 }
76 
77 /* This function is called by RTreeSearch() to find a vertex */
78 static int find_item(int id, const struct RTree_Rect *rect, void *list)
79 {
80  G_ilist_add((struct ilist *)list, id);
81  return 0;
82 }
83 
84 /* This function is called by RTreeSearch() to add selected node/line/area/isle to the list */
85 static int add_item(int id, const struct RTree_Rect *rect, void *list)
86 {
87  G_ilist_add((struct ilist *)list, id);
88  return 1;
89 }
90 
91 /* This function is called by RTreeSearch() to add selected node/line/area/isle to the list */
92 static int find_item_box(int id, const struct RTree_Rect *rect, void *list)
93 {
94  struct bound_box box;
95 
96  box.W = rect->boundary[0];
97  box.S = rect->boundary[1];
98  box.B = rect->boundary[2];
99  box.E = rect->boundary[3];
100  box.N = rect->boundary[4];
101  box.T = rect->boundary[5];
102 
103  dig_boxlist_add((struct boxlist *)list, id, &box);
104 
105  return 0;
106 }
107 
108 /* This function is called by RTreeSearch() to add selected node/line/area/isle to the list */
109 static int add_item_box(int id, const struct RTree_Rect *rect, void *list)
110 {
111  struct bound_box box;
112 
113  box.W = rect->boundary[0];
114  box.S = rect->boundary[1];
115  box.B = rect->boundary[2];
116  box.E = rect->boundary[3];
117  box.N = rect->boundary[4];
118  box.T = rect->boundary[5];
119 
120  dig_boxlist_add((struct boxlist *)list, id, &box);
121 
122  return 1;
123 }
124 
125 static void
126 Vect_snap_lines_list_rtree(struct Map_info *, const struct ilist *,
127  double, struct Map_info *);
128 
129 static void
130 Vect_snap_lines_list_kdtree(struct Map_info *, const struct ilist *,
131  double, struct Map_info *);
132 
133 /*!
134  \brief Snap selected lines to existing vertex in threshold.
135 
136  Snap selected lines to existing vertices of other selected lines.
137  3D snapping is not supported.
138 
139  Lines showing how vertices were snapped may be optionally written to error map.
140  Input map must be opened on level 2 for update at least on GV_BUILD_BASE.
141 
142  As mentioned above, lines are not necessarily snapped to nearest vertex! For example:
143  <pre>
144  |
145  | 1 line 3 is snapped to line 1,
146  | then line 2 is not snapped to common node at lines 1 and 3,
147  because it is already outside of threshold
148  ----------- 3
149 
150  |
151  | 2
152  |
153  </pre>
154 
155  The algorithm selects anchor vertices and snaps non-anchor vertices
156  to these anchors.
157  The distance between anchor vertices is always > threshold.
158  If there is more than one anchor vertex within threshold around a
159  non-anchor vertex, this vertex is snapped to the nearest anchor
160  vertex within threshold.
161 
162  \param Map input map where vertices will be snapped
163  \param List_lines list of lines to snap
164  \param thresh threshold in which snap vertices
165  \param[out] Err vector map where lines representing snap are written or NULL
166 
167  \return void
168 */
169 void
170 Vect_snap_lines_list(struct Map_info *Map, const struct ilist *List_lines,
171  double thresh, struct Map_info *Err)
172 {
173  if (getenv("GRASS_VECTOR_LOWMEM"))
174  Vect_snap_lines_list_rtree(Map, List_lines, thresh, Err);
175  else
176  Vect_snap_lines_list_kdtree(Map, List_lines, thresh, Err);
177 }
178 
179 static void
180 Vect_snap_lines_list_kdtree(struct Map_info *Map, const struct ilist *List_lines,
181  double thresh, struct Map_info *Err)
182 {
183  struct line_pnts *Points, *NPoints;
184  struct line_cats *Cats;
185  int line, ltype, line_idx;
186  double thresh2;
187 
188  int point; /* index in points array */
189  int nanchors, ntosnap; /* number of anchors and number of points to be snapped */
190  int nsnapped, ncreated; /* number of snapped verices, number of new vertices (on segments) */
191  int apoints, npoints, nvertices; /* number of allocated points, registered points, vertices */
192  XPNT *XPnts; /* Array of points */
193  NEW *New = NULL; /* Array of new points */
194  int anew = 0, nnew; /* allocated new points , number of new points */
195  struct ilist *List;
196  int *Index = NULL; /* indexes of anchors for vertices */
197  int aindex = 0; /* allocated Index */
198 
199  struct kdtree *KDTree;
200  double c[2];
201  double *kdd;
202  int *kduid, kd_found;
203 
204 
205  if (List_lines->n_values < 1)
206  return;
207 
208  Points = Vect_new_line_struct();
209  NPoints = Vect_new_line_struct();
210  Cats = Vect_new_cats_struct();
211  List = Vect_new_list();
212 
213  KDTree = kdtree_create(2, NULL);
214 
215  thresh2 = thresh * thresh;
216 
217  /* Go through all lines in vector, and add each point to structure of points */
218  apoints = 0;
219  point = 1; /* index starts from 1 ! */
220  nvertices = 0;
221  XPnts = NULL;
222 
223  G_important_message(_("Snap vertices Pass 1: select points"));
224  for (line_idx = 0; line_idx < List_lines->n_values; line_idx++) {
225  int v;
226 
227  G_percent(line_idx, List_lines->n_values, 2);
228 
229  line = List_lines->value[line_idx];
230 
231  G_debug(3, "line = %d", line);
232  if (!Vect_line_alive(Map, line))
233  continue;
234 
235  ltype = Vect_read_line(Map, Points, Cats, line);
236 
237  for (v = 0; v < Points->n_points; v++) {
238 
239  G_debug(3, " vertex v = %d", v);
240  nvertices++;
241 
242  /* coords */
243  c[0] = Points->x[v];
244  c[1] = Points->y[v];
245 
246  if (kdtree_insert(KDTree, c, point, 0)) {
247  /* Add to structure */
248  if ((point - 1) == apoints) {
249  apoints += 10000;
250  XPnts =
251  (XPNT *) G_realloc(XPnts,
252  (apoints + 1) * sizeof(XPNT));
253  }
254  XPnts[point].x = Points->x[v];
255  XPnts[point].y = Points->y[v];
256  XPnts[point].anchor = -1;
257  point++;
258  }
259  }
260  }
261  G_percent(line_idx, List_lines->n_values, 2); /* finish it */
262 
263  npoints = point - 1;
264 
265  /* Go through all registered points and if not yet marked mark it as anchor and assign this anchor
266  * to all not yet marked points in threshold */
267 
268  G_important_message(_("Snap vertices Pass 2: assign anchor vertices"));
269 
270  nanchors = ntosnap = 0;
271  for (point = 1; point <= npoints; point++) {
272  int i;
273 
274  G_percent(point, npoints, 4);
275 
276  G_debug(3, " point = %d", point);
277 
278  if (XPnts[point].anchor >= 0)
279  continue;
280 
281  XPnts[point].anchor = 0; /* make it anchor */
282  nanchors++;
283 
284  /* Find points in threshold */
285  c[0] = XPnts[point].x;
286  c[1] = XPnts[point].y;
287 
288  Vect_reset_list(List);
289  kd_found = kdtree_dnn(KDTree, c, &kduid, &kdd, thresh, &point);
290  G_debug(4, " %d points in threshold box", kd_found);
291 
292  for (i = 0; i < kd_found; i++) {
293  int pointb;
294  double dx, dy, dist2;
295 
296  pointb = kduid[i];
297  if (pointb == point)
298  continue;
299 
300  dx = XPnts[pointb].x - XPnts[point].x;
301  dy = XPnts[pointb].y - XPnts[point].y;
302  dist2 = dx * dx + dy * dy;
303 
304  if (dist2 > thresh2) /* outside threshold */
305  continue;
306 
307  /* doesn't have an anchor yet */
308  if (XPnts[pointb].anchor == -1) {
309  XPnts[pointb].anchor = point;
310  ntosnap++;
311  }
312  else if (XPnts[pointb].anchor > 0) { /* check distance to previously assigned anchor */
313  double dist2_a;
314 
315  dx = XPnts[XPnts[pointb].anchor].x - XPnts[pointb].x;
316  dy = XPnts[XPnts[pointb].anchor].y - XPnts[pointb].y;
317  dist2_a = dx * dx + dy * dy;
318 
319  /* replace old anchor */
320  if (dist2 < dist2_a) {
321  XPnts[pointb].anchor = point;
322  }
323  }
324  }
325  if (kd_found) {
326  G_free(kdd);
327  G_free(kduid);
328  }
329  }
330 
331  /* Go through all lines and:
332  * 1) for all vertices: if not anchor snap it to its anchor
333  * 2) for all segments: snap it to all anchors in threshold (except anchors of vertices of course) */
334 
335  nsnapped = ncreated = 0;
336 
337  G_important_message(_("Snap vertices Pass 3: snap to assigned points"));
338 
339  for (line_idx = 0; line_idx < List_lines->n_values; line_idx++) {
340  int v, spoint, anchor;
341  int changed = 0;
342  double kddist;
343 
344  G_percent(line_idx, List_lines->n_values, 2);
345 
346  line = List_lines->value[line_idx];
347 
348  G_debug(3, "line = %d", line);
349  if (!Vect_line_alive(Map, line))
350  continue;
351 
352  ltype = Vect_read_line(Map, Points, Cats, line);
353 
354  if (Points->n_points >= aindex) {
355  aindex = Points->n_points;
356  Index = (int *)G_realloc(Index, aindex * sizeof(int));
357  }
358 
359  /* Snap all vertices */
360  G_debug(3, "Snap all vertices");
361  for (v = 0; v < Points->n_points; v++) {
362  /* Box */
363  c[0] = Points->x[v];
364  c[1] = Points->y[v];
365 
366  /* Find point ( should always find one point ) */
367  Vect_reset_list(List);
368 
369  spoint = -1;
370  kdtree_knn(KDTree, c, &spoint, &kddist, 1, NULL);
371  if (spoint == -1)
372  G_fatal_error("Point not in KD Tree");
373 
374  anchor = XPnts[spoint].anchor;
375 
376  if (anchor > 0) { /* to be snapped */
377  Points->x[v] = XPnts[anchor].x;
378  Points->y[v] = XPnts[anchor].y;
379  nsnapped++;
380  changed = 1;
381  Index[v] = anchor; /* point on new location */
382  }
383  else {
384  Index[v] = spoint; /* old point */
385  }
386  }
387 
388  /* New points */
389  Vect_reset_line(NPoints);
390 
391  /* Snap all segments to anchors in threshold */
392  G_debug(3, "Snap all segments");
393  for (v = 0; v < Points->n_points - 1; v++) {
394  int i;
395  double x1, x2, y1, y2, xmin, xmax, ymin, ymax;
396  double rc[4];
397 
398  G_debug(3, " segment = %d end anchors : %d %d", v, Index[v],
399  Index[v + 1]);
400 
401  x1 = Points->x[v];
402  x2 = Points->x[v + 1];
403  y1 = Points->y[v];
404  y2 = Points->y[v + 1];
405 
406  Vect_append_point(NPoints, Points->x[v], Points->y[v],
407  Points->z[v]);
408 
409  /* Box */
410  if (x1 <= x2) {
411  xmin = x1;
412  xmax = x2;
413  }
414  else {
415  xmin = x2;
416  xmax = x1;
417  }
418  if (y1 <= y2) {
419  ymin = y1;
420  ymax = y2;
421  }
422  else {
423  ymin = y2;
424  ymax = y1;
425  }
426 
427  /* Find points */
428  Vect_reset_list(List);
429  G_debug(3, " search anchors for segment %g,%g to %g,%g", x1, y1, x2, y2);
430  /* distance search: circle around midpoint encompassing
431  * endpoints
432  * box search: box encompassing endpoints,
433  * smaller than corresponding circle */
434  rc[0] = xmin - thresh * 2;
435  rc[1] = ymin - thresh * 2;
436  rc[2] = xmax + thresh * 2;
437  rc[3] = ymax + thresh * 2;
438 
439  kd_found = kdtree_rnn(KDTree, rc, &kduid, NULL);
440 
441  G_debug(3, " %d points in box", kd_found);
442 
443  /* Snap to anchor in threshold different from end points */
444  nnew = 0;
445  for (i = 0; i < kd_found; i++) {
446  double dist2, along;
447  int status;
448 
449  spoint = kduid[i];
450  G_debug(4, " spoint = %d anchor = %d", spoint,
451  XPnts[spoint].anchor);
452 
453  if (spoint == Index[v] || spoint == Index[v + 1])
454  continue; /* end point */
455  if (XPnts[spoint].anchor > 0)
456  continue; /* point is not anchor */
457 
458  /* Check the distance */
459  dist2 =
460  dig_distance2_point_to_line(XPnts[spoint].x,
461  XPnts[spoint].y, 0, x1, y1, 0,
462  x2, y2, 0, 0, NULL, NULL,
463  NULL, &along, &status);
464 
465  G_debug(4, " distance = %lf", sqrt(dist2));
466 
467  if (status == 0 && dist2 <= thresh2) {
468  G_debug(4, " anchor in thresh, along = %lf", along);
469 
470  if (nnew == anew) {
471  anew += 100;
472  New = (NEW *) G_realloc(New, anew * sizeof(NEW));
473  }
474  New[nnew].anchor = spoint;
475  New[nnew].along = along;
476  nnew++;
477  }
478  }
479  if (kd_found) {
480  G_free(kduid);
481  }
482  G_debug(3, " nnew = %d", nnew);
483  /* insert new vertices */
484  if (nnew > 0) {
485  /* sort by distance along the segment */
486  qsort(New, sizeof(char) * nnew, sizeof(NEW), sort_new);
487 
488  for (i = 0; i < nnew; i++) {
489  anchor = New[i].anchor;
490  /* Vect_line_insert_point ( Points, ++v, XPnts[anchor].x, XPnts[anchor].y, 0); */
491  Vect_append_point(NPoints, XPnts[anchor].x,
492  XPnts[anchor].y, 0);
493  ncreated++;
494  }
495  changed = 1;
496  }
497  }
498 
499  /* append end point */
500  v = Points->n_points - 1;
501  Vect_append_point(NPoints, Points->x[v], Points->y[v], Points->z[v]);
502 
503  if (changed) { /* rewrite the line */
504  Vect_line_prune(NPoints); /* remove duplicates */
505  if (NPoints->n_points > 1 || !(ltype & GV_LINES)) {
506  Vect_rewrite_line(Map, line, ltype, NPoints, Cats);
507  }
508  else {
509  Vect_delete_line(Map, line);
510  }
511  if (Err) {
512  Vect_write_line(Err, ltype, Points, Cats);
513  }
514  }
515  } /* for each line */
516  G_percent(line_idx, List_lines->n_values, 2); /* finish it */
517 
518  Vect_destroy_line_struct(Points);
519  Vect_destroy_line_struct(NPoints);
520  Vect_destroy_cats_struct(Cats);
521  G_free(XPnts);
522  G_free(Index);
523  G_free(New);
524  kdtree_destroy(KDTree);
525 
526  G_verbose_message(_("Snapped vertices: %d"), nsnapped);
527  G_verbose_message(_("New vertices: %d"), ncreated);
528 }
529 
530 static void
531 Vect_snap_lines_list_rtree(struct Map_info *Map, const struct ilist *List_lines,
532  double thresh, struct Map_info *Err)
533 {
534  struct line_pnts *Points, *NPoints;
535  struct line_cats *Cats;
536  int line, ltype, line_idx;
537  double thresh2;
538 
539  int point; /* index in points array */
540  int nanchors, ntosnap; /* number of anchors and number of points to be snapped */
541  int nsnapped, ncreated; /* number of snapped verices, number of new vertices (on segments) */
542  int apoints, npoints, nvertices; /* number of allocated points, registered points, vertices */
543  XPNT *XPnts; /* Array of points */
544  NEW *New = NULL; /* Array of new points */
545  int anew = 0, nnew; /* allocated new points , number of new points */
546  struct ilist *List;
547  int *Index = NULL; /* indexes of anchors for vertices */
548  int aindex = 0; /* allocated Index */
549 
550  struct RTree *RTree;
551  int rtreefd = -1;
552  static struct RTree_Rect rect;
553  static int rect_init = 0;
554 
555  if (!rect_init) {
556  rect.boundary = G_malloc(6 * sizeof(RectReal));
557  rect_init = 6;
558  }
559 
560  if (List_lines->n_values < 1)
561  return;
562 
563  Points = Vect_new_line_struct();
564  NPoints = Vect_new_line_struct();
565  Cats = Vect_new_cats_struct();
566  List = Vect_new_list();
567  if (getenv("GRASS_VECTOR_LOWMEM")) {
568  char *filename = G_tempfile();
569 
570  rtreefd = open(filename, O_RDWR | O_CREAT | O_EXCL, 0600);
571  remove(filename);
572  }
573  RTree = RTreeCreateTree(rtreefd, 0, 2);
574 
575  thresh2 = thresh * thresh;
576 
577  /* Go through all lines in vector, and add each point to structure of points */
578  apoints = 0;
579  point = 1; /* index starts from 1 ! */
580  nvertices = 0;
581  XPnts = NULL;
582 
583  G_important_message(_("Snap vertices Pass 1: select points"));
584  for (line_idx = 0; line_idx < List_lines->n_values; line_idx++) {
585  int v;
586 
587  G_percent(line_idx, List_lines->n_values, 2);
588 
589  line = List_lines->value[line_idx];
590 
591  G_debug(3, "line = %d", line);
592  if (!Vect_line_alive(Map, line))
593  continue;
594 
595  ltype = Vect_read_line(Map, Points, Cats, line);
596 
597  for (v = 0; v < Points->n_points; v++) {
598  G_debug(3, " vertex v = %d", v);
599  nvertices++;
600 
601  /* Box */
602  rect.boundary[0] = Points->x[v];
603  rect.boundary[3] = Points->x[v];
604  rect.boundary[1] = Points->y[v];
605  rect.boundary[4] = Points->y[v];
606  rect.boundary[2] = 0;
607  rect.boundary[5] = 0;
608 
609  /* Already registered ? */
610  Vect_reset_list(List);
611  RTreeSearch(RTree, &rect, find_item, List);
612  G_debug(3, "List : nvalues = %d", List->n_values);
613 
614  if (List->n_values == 0) { /* Not found */
615  /* Add to tree and to structure */
616  RTreeInsertRect(&rect, point, RTree);
617  if ((point - 1) == apoints) {
618  apoints += 10000;
619  XPnts =
620  (XPNT *) G_realloc(XPnts,
621  (apoints + 1) * sizeof(XPNT));
622  }
623  XPnts[point].x = Points->x[v];
624  XPnts[point].y = Points->y[v];
625  XPnts[point].anchor = -1;
626  point++;
627  }
628  }
629  }
630  G_percent(line_idx, List_lines->n_values, 2); /* finish it */
631 
632  npoints = point - 1;
633 
634  /* Go through all registered points and if not yet marked mark it as anchor and assign this anchor
635  * to all not yet marked points in threshold */
636 
637  G_important_message(_("Snap vertices Pass 2: assign anchor vertices"));
638 
639  nanchors = ntosnap = 0;
640  for (point = 1; point <= npoints; point++) {
641  int i;
642 
643  G_percent(point, npoints, 4);
644 
645  G_debug(3, " point = %d", point);
646 
647  if (XPnts[point].anchor >= 0)
648  continue;
649 
650  XPnts[point].anchor = 0; /* make it anchor */
651  nanchors++;
652 
653  /* Find points in threshold */
654  rect.boundary[0] = XPnts[point].x - thresh;
655  rect.boundary[3] = XPnts[point].x + thresh;
656  rect.boundary[1] = XPnts[point].y - thresh;
657  rect.boundary[4] = XPnts[point].y + thresh;
658  rect.boundary[2] = 0;
659  rect.boundary[5] = 0;
660 
661  Vect_reset_list(List);
662  RTreeSearch(RTree, &rect, add_item, List);
663  G_debug(4, " %d points in threshold box", List->n_values);
664 
665  for (i = 0; i < List->n_values; i++) {
666  int pointb;
667  double dx, dy, dist2;
668 
669  pointb = List->value[i];
670  if (pointb == point)
671  continue;
672 
673  dx = XPnts[pointb].x - XPnts[point].x;
674  dy = XPnts[pointb].y - XPnts[point].y;
675  dist2 = dx * dx + dy * dy;
676 
677  if (dist2 > thresh2) /* outside threshold */
678  continue;
679 
680  /* doesn't have an anchor yet */
681  if (XPnts[pointb].anchor == -1) {
682  XPnts[pointb].anchor = point;
683  ntosnap++;
684  }
685  else if (XPnts[pointb].anchor > 0) { /* check distance to previously assigned anchor */
686  double dist2_a;
687 
688  dx = XPnts[XPnts[pointb].anchor].x - XPnts[pointb].x;
689  dy = XPnts[XPnts[pointb].anchor].y - XPnts[pointb].y;
690  dist2_a = dx * dx + dy * dy;
691 
692  /* replace old anchor */
693  if (dist2 < dist2_a) {
694  XPnts[pointb].anchor = point;
695  }
696  }
697  }
698  }
699 
700  /* Go through all lines and:
701  * 1) for all vertices: if not anchor snap it to its anchor
702  * 2) for all segments: snap it to all anchors in threshold (except anchors of vertices of course) */
703 
704  nsnapped = ncreated = 0;
705 
706  G_important_message(_("Snap vertices Pass 3: snap to assigned points"));
707 
708  for (line_idx = 0; line_idx < List_lines->n_values; line_idx++) {
709  int v, spoint, anchor;
710  int changed = 0;
711 
712  G_percent(line_idx, List_lines->n_values, 2);
713 
714  line = List_lines->value[line_idx];
715 
716  G_debug(3, "line = %d", line);
717  if (!Vect_line_alive(Map, line))
718  continue;
719 
720  ltype = Vect_read_line(Map, Points, Cats, line);
721 
722  if (Points->n_points >= aindex) {
723  aindex = Points->n_points;
724  Index = (int *)G_realloc(Index, aindex * sizeof(int));
725  }
726 
727  /* Snap all vertices */
728  for (v = 0; v < Points->n_points; v++) {
729  /* Box */
730  rect.boundary[0] = Points->x[v];
731  rect.boundary[3] = Points->x[v];
732  rect.boundary[1] = Points->y[v];
733  rect.boundary[4] = Points->y[v];
734  rect.boundary[2] = 0;
735  rect.boundary[5] = 0;
736 
737  /* Find point ( should always find one point ) */
738  Vect_reset_list(List);
739 
740  RTreeSearch(RTree, &rect, add_item, List);
741 
742  spoint = List->value[0];
743  anchor = XPnts[spoint].anchor;
744 
745  if (anchor > 0) { /* to be snapped */
746  Points->x[v] = XPnts[anchor].x;
747  Points->y[v] = XPnts[anchor].y;
748  nsnapped++;
749  changed = 1;
750  Index[v] = anchor; /* point on new location */
751  }
752  else {
753  Index[v] = spoint; /* old point */
754  }
755  }
756 
757  /* New points */
758  Vect_reset_line(NPoints);
759 
760  /* Snap all segments to anchors in threshold */
761  for (v = 0; v < Points->n_points - 1; v++) {
762  int i;
763  double x1, x2, y1, y2, xmin, xmax, ymin, ymax;
764 
765  G_debug(3, " segment = %d end anchors : %d %d", v, Index[v],
766  Index[v + 1]);
767 
768  x1 = Points->x[v];
769  x2 = Points->x[v + 1];
770  y1 = Points->y[v];
771  y2 = Points->y[v + 1];
772 
773  Vect_append_point(NPoints, Points->x[v], Points->y[v],
774  Points->z[v]);
775 
776  /* Box */
777  if (x1 <= x2) {
778  xmin = x1;
779  xmax = x2;
780  }
781  else {
782  xmin = x2;
783  xmax = x1;
784  }
785  if (y1 <= y2) {
786  ymin = y1;
787  ymax = y2;
788  }
789  else {
790  ymin = y2;
791  ymax = y1;
792  }
793 
794  rect.boundary[0] = xmin - thresh;
795  rect.boundary[3] = xmax + thresh;
796  rect.boundary[1] = ymin - thresh;
797  rect.boundary[4] = ymax + thresh;
798  rect.boundary[2] = 0;
799  rect.boundary[5] = 0;
800 
801  /* Find points */
802  Vect_reset_list(List);
803  RTreeSearch(RTree, &rect, add_item, List);
804 
805  G_debug(3, " %d points in box", List->n_values);
806 
807  /* Snap to anchor in threshold different from end points */
808  nnew = 0;
809  for (i = 0; i < List->n_values; i++) {
810  double dist2, along;
811  int status;
812 
813  spoint = List->value[i];
814  G_debug(4, " spoint = %d anchor = %d", spoint,
815  XPnts[spoint].anchor);
816 
817  if (spoint == Index[v] || spoint == Index[v + 1])
818  continue; /* end point */
819  if (XPnts[spoint].anchor > 0)
820  continue; /* point is not anchor */
821 
822  /* Check the distance */
823  dist2 =
824  dig_distance2_point_to_line(XPnts[spoint].x,
825  XPnts[spoint].y, 0, x1, y1, 0,
826  x2, y2, 0, 0, NULL, NULL,
827  NULL, &along, &status);
828 
829  G_debug(4, " distance = %lf", sqrt(dist2));
830 
831  if (status == 0 && dist2 <= thresh2) {
832  G_debug(4, " anchor in thresh, along = %lf", along);
833 
834  if (nnew == anew) {
835  anew += 100;
836  New = (NEW *) G_realloc(New, anew * sizeof(NEW));
837  }
838  New[nnew].anchor = spoint;
839  New[nnew].along = along;
840  nnew++;
841  }
842  }
843  G_debug(3, " nnew = %d", nnew);
844  /* insert new vertices */
845  if (nnew > 0) {
846  /* sort by distance along the segment */
847  qsort(New, sizeof(char) * nnew, sizeof(NEW), sort_new);
848 
849  for (i = 0; i < nnew; i++) {
850  anchor = New[i].anchor;
851  /* Vect_line_insert_point ( Points, ++v, XPnts[anchor].x, XPnts[anchor].y, 0); */
852  Vect_append_point(NPoints, XPnts[anchor].x,
853  XPnts[anchor].y, 0);
854  ncreated++;
855  }
856  changed = 1;
857  }
858  }
859 
860  /* append end point */
861  v = Points->n_points - 1;
862  Vect_append_point(NPoints, Points->x[v], Points->y[v], Points->z[v]);
863 
864  if (changed) { /* rewrite the line */
865  Vect_line_prune(NPoints); /* remove duplicates */
866  if (NPoints->n_points > 1 || !(ltype & GV_LINES)) {
867  Vect_rewrite_line(Map, line, ltype, NPoints, Cats);
868  }
869  else {
870  Vect_delete_line(Map, line);
871  }
872  if (Err) {
873  Vect_write_line(Err, ltype, Points, Cats);
874  }
875  }
876  } /* for each line */
877  G_percent(line_idx, List_lines->n_values, 2); /* finish it */
878 
879  Vect_destroy_line_struct(Points);
880  Vect_destroy_line_struct(NPoints);
881  Vect_destroy_cats_struct(Cats);
882  G_free(XPnts);
883  G_free(Index);
884  G_free(New);
885  RTreeDestroyTree(RTree);
886  if (rtreefd >= 0)
887  close(rtreefd);
888 
889  G_verbose_message(_("Snapped vertices: %d"), nsnapped);
890  G_verbose_message(_("New vertices: %d"), ncreated);
891 }
892 
893 
894 /*!
895  \brief Snap lines in vector map to existing vertex in threshold.
896 
897  For details see Vect_snap_lines_list()
898 
899  \param[in] Map input map where vertices will be snapped
900  \param[in] type type of lines to snap
901  \param[in] thresh threshold in which snap vertices
902  \param[out] Err vector map where lines representing snap are written or NULL
903 
904  \return void
905  */
906 void
907 Vect_snap_lines(struct Map_info *Map, int type, double thresh,
908  struct Map_info *Err)
909 {
910  int line, nlines, ltype;
911  struct ilist *List;
912 
913  List = Vect_new_list();
914 
915  nlines = Vect_get_num_lines(Map);
916 
917  G_important_message(_("Reading features..."));
918  for (line = 1; line <= nlines; line++) {
919  G_debug(3, "line = %d", line);
920 
921  if (!Vect_line_alive(Map, line))
922  continue;
923 
924  ltype = Vect_read_line(Map, NULL, NULL, line);
925 
926  if (!(ltype & type))
927  continue;
928 
929  G_ilist_add(List, line);
930  }
931 
932  Vect_snap_lines_list(Map, List, thresh, Err);
933 
934  Vect_destroy_list(List);
935 
936  return;
937 }
938 
939 /*!
940  \brief Snap a line to reference lines in Map with threshold.
941 
942  3D snapping is supported. The line to snap and the reference lines
943  can but do not need to be in different vector maps.
944 
945  Vect_snap_line() uses less memory, but is slower than
946  Vect_snap_lines_list()
947 
948  For details on snapping, see Vect_snap_lines_list()
949 
950  \param[in] Map input map with reference lines
951  \param[in] reflist list of reference lines
952  \param[in,out] Points line points to snap
953  \param[in] thresh threshold in which to snap vertices
954  \param[in] with_z 2D or 3D snapping
955  \param[in,out] nsnapped number of snapped vertices
956  \param[in,out] ncreated number of new vertices (on segments)
957 
958  \return 1 if line was changed, otherwise 0
959  */
960 int
961 Vect_snap_line(struct Map_info *Map, struct ilist *reflist,
962  struct line_pnts *Points, double thresh, int with_z,
963  int *nsnapped, int *ncreated)
964 {
965  struct line_pnts *LPoints, *NPoints;
966  struct line_cats *Cats;
967  int i, v, line, nlines;
968  int changed;
969  double thresh2;
970 
971  int point; /* index in points array */
972  int segment; /* index in segments array */
973  int asegments; /* number of allocated segments */
974  int nvertices; /* number of vertices */
975  char *XSegs = NULL; /* Array of segments */
976  NEW2 *New = NULL; /* Array of new points */
977  int anew = 0, nnew; /* allocated new points , number of new points */
978  struct boxlist *List;
979 
980  struct RTree *pnt_tree, /* spatial index for reference points */
981  *seg_tree; /* spatial index for reference segments */
982  struct RTree_Rect rect;
983 
984  rect.boundary = G_malloc(6 * sizeof(RectReal));
985  rect.boundary[0] = 0;
986  rect.boundary[1] = 0;
987  rect.boundary[2] = 0;
988  rect.boundary[3] = 0;
989  rect.boundary[4] = 0;
990  rect.boundary[5] = 0;
991 
992  changed = 0;
993  if (nsnapped)
994  *nsnapped = 0;
995  if (ncreated)
996  *ncreated = 0;
997 
998  point = Points->n_points;
999  Vect_line_prune(Points);
1000  if (point != Points->n_points)
1001  changed = 1;
1002 
1003  nlines = reflist->n_values;
1004  if (nlines < 1)
1005  return changed;
1006 
1007  LPoints = Vect_new_line_struct();
1008  NPoints = Vect_new_line_struct();
1009  Cats = Vect_new_cats_struct();
1010  List = Vect_new_boxlist(1);
1011  with_z = (with_z != 0);
1012  pnt_tree = RTreeCreateTree(-1, 0, 2 + with_z);
1013  RTreeSetOverflow(pnt_tree, 0);
1014  seg_tree = RTreeCreateTree(-1, 0, 2 + with_z);
1015  RTreeSetOverflow(seg_tree, 0);
1016 
1017  thresh2 = thresh * thresh;
1018 
1019  point = segment = 1; /* index starts from 1 ! */
1020  nvertices = 0;
1021  asegments = 0;
1022 
1023  /* Add all vertices and all segments of all reference lines
1024  * to spatial indices */
1025  nlines = reflist->n_values;
1026  for (i = 0; i < nlines; i++) {
1027 
1028  line = reflist->value[i];
1029 
1030  G_debug(3, "line = %d", line);
1031  if (!Vect_line_alive(Map, line))
1032  continue;
1033 
1034  Vect_read_line(Map, LPoints, Cats, line);
1035  Vect_line_prune(LPoints);
1036 
1037  for (v = 0; v < LPoints->n_points; v++) {
1038  G_debug(3, " vertex v = %d", v);
1039  nvertices++;
1040 
1041  /* Box */
1042  rect.boundary[0] = LPoints->x[v];
1043  rect.boundary[3] = LPoints->x[v];
1044  rect.boundary[1] = LPoints->y[v];
1045  rect.boundary[4] = LPoints->y[v];
1046  if (with_z) {
1047  rect.boundary[2] = LPoints->z[v];
1048  rect.boundary[5] = LPoints->z[v];
1049  }
1050 
1051  /* Already registered ? */
1052  Vect_reset_boxlist(List);
1053  RTreeSearch(pnt_tree, &rect, find_item_box, (void *)List);
1054  G_debug(3, "List : nvalues = %d", List->n_values);
1055 
1056  if (List->n_values == 0) { /* Not found */
1057 
1058  /* Add to points tree */
1059  RTreeInsertRect(&rect, point, pnt_tree);
1060 
1061  point++;
1062  }
1063 
1064  /* reference segments */
1065  if (v) {
1066  char sides = 0;
1067 
1068  /* Box */
1069  if (LPoints->x[v - 1] < LPoints->x[v]) {
1070  rect.boundary[0] = LPoints->x[v - 1];
1071  rect.boundary[3] = LPoints->x[v];
1072  sides |= X1W;
1073  }
1074  else {
1075  rect.boundary[0] = LPoints->x[v];
1076  rect.boundary[3] = LPoints->x[v - 1];
1077  }
1078  if (LPoints->y[v - 1] < LPoints->y[v]) {
1079  rect.boundary[1] = LPoints->y[v - 1];
1080  rect.boundary[4] = LPoints->y[v];
1081  sides |= Y1S;
1082  }
1083  else {
1084  rect.boundary[1] = LPoints->y[v];
1085  rect.boundary[4] = LPoints->y[v - 1];
1086  }
1087  if (LPoints->z[v - 1] < LPoints->z[v]) {
1088  rect.boundary[2] = LPoints->z[v - 1];
1089  rect.boundary[5] = LPoints->z[v];
1090  sides |= Z1B;
1091  }
1092  else {
1093  rect.boundary[2] = LPoints->z[v];
1094  rect.boundary[5] = LPoints->z[v - 1];
1095  }
1096 
1097  /* do not check for duplicates, too costly
1098  * because different segments can have identical boxes */
1099  RTreeInsertRect(&rect, segment, seg_tree);
1100 
1101  if ((segment - 1) == asegments) {
1102  asegments += 1000;
1103  XSegs =
1104  (char *) G_realloc(XSegs,
1105  (asegments + 1) * sizeof(char));
1106  }
1107  XSegs[segment] = sides;
1108  segment++;
1109  }
1110  }
1111  }
1112 
1113  /* go through all vertices of the line to snap */
1114  /* find nearest reference vertex */
1115  for (v = 0; v < Points->n_points; v++) {
1116  double dist2, tmpdist2;
1117  double x, y, z;
1118 
1119  dist2 = thresh2 + thresh2;
1120  x = Points->x[v];
1121  y = Points->y[v];
1122  z = Points->z[v];
1123 
1124  /* Box */
1125  rect.boundary[0] = Points->x[v] - thresh;
1126  rect.boundary[3] = Points->x[v] + thresh;
1127  rect.boundary[1] = Points->y[v] - thresh;
1128  rect.boundary[4] = Points->y[v] + thresh;
1129  if (with_z) {
1130  rect.boundary[2] = Points->z[v] - thresh;
1131  rect.boundary[5] = Points->z[v] + thresh;
1132  }
1133 
1134  Vect_reset_boxlist(List);
1135 
1136  RTreeSearch(pnt_tree, &rect, add_item_box, (void *)List);
1137 
1138  for (i = 0; i < List->n_values; i++) {
1139  double dx = List->box[i].E - Points->x[v];
1140  double dy = List->box[i].N - Points->y[v];
1141  double dz = 0;
1142 
1143  if (with_z)
1144  dz = List->box[i].T - Points->z[v];
1145 
1146  tmpdist2 = dx * dx + dy * dy + dz * dz;
1147 
1148  if (tmpdist2 < dist2) {
1149  dist2 = tmpdist2;
1150 
1151  x = List->box[i].E;
1152  y = List->box[i].N;
1153  z = List->box[i].T;
1154  }
1155  }
1156 
1157  if (dist2 <= thresh2 && dist2 > 0) {
1158  Points->x[v] = x;
1159  Points->y[v] = y;
1160  Points->z[v] = z;
1161 
1162  changed = 1;
1163  if (nsnapped)
1164  (*nsnapped)++;
1165  }
1166  }
1167 
1168  /* go through all vertices of the line to snap */
1169  /* find nearest reference segment */
1170  for (v = 0; v < Points->n_points; v++) {
1171  double dist2, tmpdist2;
1172  double x, y, z;
1173 
1174  dist2 = thresh2 + thresh2;
1175  x = Points->x[v];
1176  y = Points->y[v];
1177  z = Points->z[v];
1178 
1179  /* Box */
1180  rect.boundary[0] = Points->x[v] - thresh;
1181  rect.boundary[3] = Points->x[v] + thresh;
1182  rect.boundary[1] = Points->y[v] - thresh;
1183  rect.boundary[4] = Points->y[v] + thresh;
1184  if (with_z) {
1185  rect.boundary[2] = Points->z[v] - thresh;
1186  rect.boundary[5] = Points->z[v] + thresh;
1187  }
1188 
1189  Vect_reset_boxlist(List);
1190 
1191  RTreeSearch(seg_tree, &rect, add_item_box, (void *)List);
1192 
1193  for (i = 0; i < List->n_values; i++) {
1194  double x1, y1, z1, x2, y2, z2;
1195  double tmpx, tmpy, tmpz;
1196  int status;
1197 
1198  segment = List->id[i];
1199 
1200  if (XSegs[segment] & X1W) {
1201  x1 = List->box[i].W;
1202  x2 = List->box[i].E;
1203  }
1204  else {
1205  x1 = List->box[i].E;
1206  x2 = List->box[i].W;
1207  }
1208  if (XSegs[segment] & Y1S) {
1209  y1 = List->box[i].S;
1210  y2 = List->box[i].N;
1211  }
1212  else {
1213  y1 = List->box[i].N;
1214  y2 = List->box[i].S;
1215  }
1216  if (XSegs[segment] & Z1B) {
1217  z1 = List->box[i].B;
1218  z2 = List->box[i].T;
1219  }
1220  else {
1221  z1 = List->box[i].T;
1222  z2 = List->box[i].B;
1223  }
1224 
1225  /* Check the distance */
1226  tmpdist2 =
1227  dig_distance2_point_to_line(Points->x[v],
1228  Points->y[v],
1229  Points->z[v],
1230  x1, y1, z1, x2, y2, z2,
1231  with_z, &tmpx, &tmpy, &tmpz,
1232  NULL, &status);
1233 
1234  if (tmpdist2 < dist2 && status == 0) {
1235  dist2 = tmpdist2;
1236 
1237  x = tmpx;
1238  y = tmpy;
1239  z = tmpz;
1240  }
1241  }
1242 
1243  if (dist2 <= thresh2 && dist2 > 0) {
1244  Points->x[v] = x;
1245  Points->y[v] = y;
1246  Points->z[v] = z;
1247 
1248  changed = 1;
1249  if (nsnapped)
1250  (*nsnapped)++;
1251  }
1252  }
1253 
1254  RTreeDestroyTree(seg_tree);
1255  G_free(XSegs);
1256 
1257  /* go through all segments of the line to snap */
1258  /* find nearest reference vertex, add this vertex */
1259  for (v = 0; v < Points->n_points - 1; v++) {
1260  double x1, x2, y1, y2, z1, z2;
1261  double xmin, xmax, ymin, ymax, zmin, zmax;
1262 
1263  x1 = Points->x[v];
1264  x2 = Points->x[v + 1];
1265  y1 = Points->y[v];
1266  y2 = Points->y[v + 1];
1267  if (with_z) {
1268  z1 = Points->z[v];
1269  z2 = Points->z[v + 1];
1270  }
1271  else {
1272  z1 = z2 = 0;
1273  }
1274 
1275  Vect_append_point(NPoints, Points->x[v], Points->y[v],
1276  Points->z[v]);
1277 
1278  /* Box */
1279  if (x1 <= x2) {
1280  xmin = x1;
1281  xmax = x2;
1282  }
1283  else {
1284  xmin = x2;
1285  xmax = x1;
1286  }
1287  if (y1 <= y2) {
1288  ymin = y1;
1289  ymax = y2;
1290  }
1291  else {
1292  ymin = y2;
1293  ymax = y1;
1294  }
1295  if (z1 <= z2) {
1296  zmin = z1;
1297  zmax = z2;
1298  }
1299  else {
1300  zmin = z2;
1301  zmax = z1;
1302  }
1303 
1304  rect.boundary[0] = xmin - thresh;
1305  rect.boundary[3] = xmax + thresh;
1306  rect.boundary[1] = ymin - thresh;
1307  rect.boundary[4] = ymax + thresh;
1308  rect.boundary[2] = zmin - thresh;
1309  rect.boundary[5] = zmax + thresh;
1310 
1311  /* Find points */
1312  Vect_reset_boxlist(List);
1313  RTreeSearch(pnt_tree, &rect, add_item_box, (void *)List);
1314 
1315  G_debug(3, " %d points in box", List->n_values);
1316 
1317  /* Snap to vertex in threshold different from end points */
1318  nnew = 0;
1319  for (i = 0; i < List->n_values; i++) {
1320  double dist2, along;
1321  int status;
1322 
1323  if (!with_z)
1324  List->box[i].T = 0;
1325 
1326  if (Points->x[v] == List->box[i].E &&
1327  Points->y[v] == List->box[i].N &&
1328  Points->z[v] == List->box[i].T)
1329  continue; /* start point */
1330 
1331  if (Points->x[v + 1] == List->box[i].E &&
1332  Points->y[v + 1] == List->box[i].N &&
1333  Points->z[v + 1] == List->box[i].T)
1334  continue; /* end point */
1335 
1336  /* Check the distance */
1337  dist2 =
1338  dig_distance2_point_to_line(List->box[i].E,
1339  List->box[i].N,
1340  List->box[i].T, x1, y1, z1,
1341  x2, y2, z2, with_z, NULL, NULL,
1342  NULL, &along, &status);
1343 
1344  if (dist2 <= thresh2 && status == 0) {
1345  G_debug(4, " anchor in thresh, along = %lf", along);
1346 
1347  if (nnew == anew) {
1348  anew += 100;
1349  New = (NEW2 *) G_realloc(New, anew * sizeof(NEW2));
1350  }
1351  New[nnew].x = List->box[i].E;
1352  New[nnew].y = List->box[i].N;
1353  New[nnew].z = List->box[i].T;
1354  New[nnew].along = along;
1355  nnew++;
1356  }
1357  G_debug(3, "dist: %g, thresh: %g", dist2, thresh2);
1358  }
1359  G_debug(3, " nnew = %d", nnew);
1360  /* insert new vertices */
1361  if (nnew > 0) {
1362  /* sort by distance along the segment */
1363  qsort(New, nnew, sizeof(NEW2), sort_new2);
1364 
1365  for (i = 0; i < nnew; i++) {
1366  Vect_append_point(NPoints, New[i].x, New[i].y, New[i].z);
1367  if (ncreated)
1368  (*ncreated)++;
1369  }
1370  changed = 1;
1371  }
1372  }
1373 
1374  /* append end point */
1375  v = Points->n_points - 1;
1376  Vect_append_point(NPoints, Points->x[v], Points->y[v], Points->z[v]);
1377 
1378  if (Points->n_points != NPoints->n_points) {
1379  Vect_line_prune(NPoints); /* remove duplicates */
1380  Vect_reset_line(Points);
1381  Vect_append_points(Points, NPoints, GV_FORWARD);
1382  }
1383 
1384  Vect_destroy_line_struct(LPoints);
1385  Vect_destroy_line_struct(NPoints);
1386  Vect_destroy_cats_struct(Cats);
1387  Vect_destroy_boxlist(List);
1388  G_free(New);
1389  RTreeDestroyTree(pnt_tree);
1390  G_free(rect.boundary);
1391 
1392  return changed;
1393 }
Vect_destroy_boxlist
void Vect_destroy_boxlist(struct boxlist *)
Frees all memory associated with a struct boxlist, including the struct itself.
Definition: vector/Vlib/list.c:265
Vect_append_points
int Vect_append_points(struct line_pnts *, const struct line_pnts *, int)
Appends points to the end of a line.
Definition: line.c:337
G_malloc
#define G_malloc(n)
Definition: defs/gis.h:112
RTreeInsertRect
int RTreeInsertRect(struct RTree_Rect *r, int tid, struct RTree *t)
Insert an item into a R*-Tree.
Definition: vector/rtree/index.c:315
RectReal
double RectReal
Definition: rtree.h:28
bound_box
Bounding box.
Definition: dig_structs.h:65
GV_FORWARD
#define GV_FORWARD
Line direction indicator forward/backward.
Definition: dig_defines.h:178
G_fatal_error
void void void void G_fatal_error(const char *,...) __attribute__((format(printf
G_important_message
void void void G_important_message(const char *,...) __attribute__((format(printf
bound_box::W
double W
West.
Definition: dig_structs.h:82
Vect_reset_list
int Vect_reset_list(struct ilist *)
Reset ilist structure.
Definition: vector/Vlib/list.c:57
RTreeDestroyTree
void RTreeDestroyTree(struct RTree *t)
Destroy an R*-Tree.
Definition: vector/rtree/index.c:222
Vect_snap_line
int Vect_snap_line(struct Map_info *Map, struct ilist *reflist, struct line_pnts *Points, double thresh, int with_z, int *nsnapped, int *ncreated)
Snap a line to reference lines in Map with threshold.
Definition: Vlib/snap.c:961
Vect_get_num_lines
plus_t Vect_get_num_lines(const struct Map_info *)
Fetch number of features (points, lines, boundaries, centroids) in vector map.
Definition: level_two.c:74
Vect_rewrite_line
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)
Definition: vector/Vlib/write.c:220
RTreeSearch
int RTreeSearch(struct RTree *t, struct RTree_Rect *r, SearchHitCallback *shcb, void *cbarg)
Search an R*-Tree.
Definition: vector/rtree/index.c:298
line_pnts::n_points
int n_points
Number of points.
Definition: dig_structs.h:1692
kdtree_rnn
int kdtree_rnn(struct kdtree *t, double *c, int **puid, int *skip)
Definition: kdtree.c:739
ilist::n_values
int n_values
Number of values in the list.
Definition: gis.h:709
G_free
void G_free(void *)
Free allocated memory.
Definition: gis/alloc.c:149
Z1B
#define Z1B
Definition: Vlib/snap.c:29
kdtree_dnn
int kdtree_dnn(struct kdtree *t, double *c, int **puid, double **pd, double maxdist, int *skip)
Definition: kdtree.c:624
bound_box::E
double E
East.
Definition: dig_structs.h:78
Vect_line_prune
int Vect_line_prune(struct line_pnts *)
Remove duplicate points, i.e. zero length segments.
Definition: line.c:281
NULL
#define NULL
Definition: ccmath.h:32
x
#define x
kdtree_create
struct kdtree * kdtree_create(char ndims, int *btol)
Definition: kdtree.c:110
Vect_snap_lines
void Vect_snap_lines(struct Map_info *Map, int type, double thresh, struct Map_info *Err)
Snap lines in vector map to existing vertex in threshold.
Definition: Vlib/snap.c:907
dig_boxlist_add
int dig_boxlist_add(struct boxlist *, int, const struct bound_box *)
Definition: vector/diglib/list.c:34
line_cats
Feature category info.
Definition: dig_structs.h:1702
bound_box::N
double N
North.
Definition: dig_structs.h:70
line_pnts::x
double * x
Array of X coordinates.
Definition: dig_structs.h:1680
G_ilist_add
void G_ilist_add(struct ilist *, int)
Add item to ilist.
Definition: ilist.c:77
line_pnts
Feature geometry info - coordinates.
Definition: dig_structs.h:1675
X1W
#define X1W
Definition: Vlib/snap.c:27
Vect_destroy_list
void Vect_destroy_list(struct ilist *)
Frees all memory associated with a struct ilist, including the struct itself.
Definition: vector/Vlib/list.c:70
Vect_new_line_struct
struct line_pnts * Vect_new_line_struct(void)
Creates and initializes a line_pnts structure.
Definition: line.c:45
Vect_destroy_cats_struct
void Vect_destroy_cats_struct(struct line_cats *)
Frees all memory associated with line_cats structure, including the struct itself.
Definition: vector/Vlib/cats.c:80
G_tempfile
char * G_tempfile(void)
Returns a temporary file name.
Definition: tempfile.c:62
kdtree
k-d tree
Definition: kdtree.h:80
Vect_write_line
off_t Vect_write_line(struct Map_info *, int, const struct line_pnts *, const struct line_cats *)
Writes a new feature.
Definition: vector/Vlib/write.c:178
dig_distance2_point_to_line
double dig_distance2_point_to_line(double, double, double, double, double, double, double, double, double, int, double *, double *, double *, double *, int *)
Definition: vector/diglib/line_dist.c:45
RTreeSetOverflow
void RTreeSetOverflow(struct RTree *t, char overflow)
Enable/disable R*-tree forced reinsertion (overflow)
Definition: vector/rtree/index.c:204
Vect_append_point
int Vect_append_point(struct line_pnts *, double, double, double)
Appends one point to the end of a line.
Definition: line.c:149
bound_box::B
double B
Bottom.
Definition: dig_structs.h:90
kdtree_destroy
void kdtree_destroy(struct kdtree *t)
Definition: kdtree.c:166
kdtree_knn
int kdtree_knn(struct kdtree *t, double *c, int *uid, double *d, int k, int *skip)
Definition: kdtree.c:501
bound_box::T
double T
Top.
Definition: dig_structs.h:86
kdtree_insert
int kdtree_insert(struct kdtree *t, double *c, int uid, int dc)
Definition: kdtree.c:178
Y1S
#define Y1S
Definition: Vlib/snap.c:28
Vect_reset_boxlist
int Vect_reset_boxlist(struct boxlist *)
Reset boxlist structure.
Definition: vector/Vlib/list.c:252
G_percent
void G_percent(long, long, int)
Print percent complete messages.
Definition: percent.c:62
Map_info
Vector map info.
Definition: dig_structs.h:1259
Vect_snap_lines_list
void Vect_snap_lines_list(struct Map_info *Map, const struct ilist *List_lines, double thresh, struct Map_info *Err)
Snap selected lines to existing vertex in threshold.
Definition: Vlib/snap.c:170
line_pnts::y
double * y
Array of Y coordinates.
Definition: dig_structs.h:1684
RTree_Rect::boundary
RectReal * boundary
Definition: rtree.h:59
Vect_new_list
struct ilist * Vect_new_list(void)
Creates and initializes a struct ilist.
Definition: vector/Vlib/list.c:32
Vect_delete_line
int Vect_delete_line(struct Map_info *, off_t)
Delete existing feature (topological level required)
Definition: vector/Vlib/write.c:253
Vect_new_cats_struct
struct line_cats * Vect_new_cats_struct(void)
Creates and initializes line_cats structure.
Definition: vector/Vlib/cats.c:40
list
Definition: manage.h:4
boxlist
List of bounding boxes with id.
Definition: dig_structs.h:1750
RTree_Rect
Definition: rtree.h:57
bound_box::S
double S
South.
Definition: dig_structs.h:74
Vect_line_alive
int Vect_line_alive(const struct Map_info *, int)
Check if feature is alive or dead (topological level required)
Definition: vector/Vlib/read.c:197
G_realloc
#define G_realloc(p, n)
Definition: defs/gis.h:114
line_pnts::z
double * z
Array of Z coordinates.
Definition: dig_structs.h:1688
_
#define _(str)
Definition: glocale.h:10
ilist
List of integers.
Definition: gis.h:700
ilist::value
int * value
Array of values.
Definition: gis.h:705
GV_LINES
#define GV_LINES
Definition: dig_defines.h:192
Vect_new_boxlist
struct boxlist * Vect_new_boxlist(int)
Creates and initializes a struct boxlist.
Definition: vector/Vlib/list.c:225
Vect_destroy_line_struct
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
getenv
char * getenv()
G_verbose_message
void void G_verbose_message(const char *,...) __attribute__((format(printf
Vect_read_line
int Vect_read_line(const struct Map_info *, struct line_pnts *, struct line_cats *, int)
Read vector feature (topological level required)
Definition: vector/Vlib/read.c:160
RTree
Definition: rtree.h:128
G_debug
int G_debug(int, const char *,...) __attribute__((format(printf
RTreeCreateTree
struct RTree * RTreeCreateTree(int fd, off_t rootpos, int ndims)
Create new empty R*-Tree.
Definition: vector/rtree/index.c:61
Vect_reset_line
void Vect_reset_line(struct line_pnts *)
Reset line.
Definition: line.c:130