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