GRASS Programmer's Manual  6.5.svn(2014)-r66266
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Vlib/snap.c
Go to the documentation of this file.
1 
20 #include <math.h>
21 #include <stdlib.h>
22 
23 #include <grass/gis.h>
24 #include <grass/Vect.h>
25 #include <grass/glocale.h>
26 
27 /* function prototypes */
28 static int sort_new(const void *pa, const void *pb);
29 
30 /* Vertex */
31 typedef struct
32 {
33  double x, y;
34  int anchor; /* 0 - anchor, do not snap this point, that means snap others to this */
35  /* >0 - index of anchor to which snap this point */
36  /* -1 - init value */
37 } XPNT;
38 
39 /* Segment */
40 typedef struct
41 {
42  double x1, y1, /* start point */
43  x2, y2; /* end point */
44 } XSEG;
45 
46 typedef struct
47 {
48  int anchor;
49  double along;
50 } NEW;
51 
52 typedef struct
53 {
54  double x, y, z, along;
55 } NEW2;
56 
57 /* for qsort */
58 static int sort_new2(const void *pa, const void *pb)
59 {
60  NEW2 *p1 = (NEW2 *) pa;
61  NEW2 *p2 = (NEW2 *) pb;
62 
63  return (p1->along < p2->along ? -1 : (p1->along > p2->along));
64 }
65 
66 /* This function is called by RTreeSearch() to add selected node/line/area/isle to the list */
67 static int add_item(int id, struct ilist *list)
68 {
69  dig_list_add(list, id);
70  return 1;
71 }
72 
73 /* This function is called by RTreeSearch() to find an item in the list */
74 static int find_item(int id, struct ilist *list)
75 {
76  dig_list_add(list, id);
77  return 0;
78 }
79 
98 /* As mentioned above, lines are not necessarily snapped to nearest vertex! For example:
99  |
100  | 1 line 3 is snapped to line 1,
101  | then line 2 is not snapped to common node at lines 1 and 3,
102  because it is already outside of threshold
103  ----------- 3
104 
105  |
106  | 2
107  |
108  */
109 void
110 Vect_snap_lines_list(struct Map_info *Map, struct ilist *List_lines,
111  double thresh, struct Map_info *Err)
112 {
113  struct line_pnts *Points, *NPoints;
114  struct line_cats *Cats;
115  int line, ltype, line_idx;
116  double thresh2;
117 
118  struct Node *RTree;
119  int point; /* index in points array */
120  int nanchors, ntosnap; /* number of anchors and number of points to be snapped */
121  int nsnapped, ncreated; /* number of snapped verices, number of new vertices (on segments) */
122  int apoints, npoints, nvertices; /* number of allocated points, registered points, vertices */
123  XPNT *XPnts; /* Array of points */
124  NEW *New = NULL; /* Array of new points */
125  int anew = 0, nnew; /* allocated new points , number of new points */
126  struct Rect rect;
127  struct ilist *List;
128  int *Index = NULL; /* indexes of anchors for vertices */
129  int aindex = 0; /* allocated Index */
130 
131  if (List_lines->n_values < 1)
132  return;
133 
134  Points = Vect_new_line_struct();
135  NPoints = Vect_new_line_struct();
136  Cats = Vect_new_cats_struct();
137  List = Vect_new_list();
138  RTree = RTreeNewIndex();
139 
140  thresh2 = thresh * thresh;
141 
142  /* Go through all lines in vector, and add each point to structure of points */
143  apoints = 0;
144  point = 1; /* index starts from 1 ! */
145  nvertices = 0;
146  XPnts = NULL;
147 
148  G_verbose_message(_("Snap vertices Pass 1: select points"));
149  for (line_idx = 0; line_idx < List_lines->n_values; line_idx++) {
150  int v;
151 
152  G_percent(line_idx, List_lines->n_values, 2);
153 
154  line = List_lines->value[line_idx];
155 
156  G_debug(3, "line = %d", line);
157  if (!Vect_line_alive(Map, line))
158  continue;
159 
160  ltype = Vect_read_line(Map, Points, Cats, line);
161 
162  for (v = 0; v < Points->n_points; v++) {
163  G_debug(3, " vertex v = %d", v);
164  nvertices++;
165 
166  /* Box */
167  rect.boundary[0] = Points->x[v];
168  rect.boundary[3] = Points->x[v];
169  rect.boundary[1] = Points->y[v];
170  rect.boundary[4] = Points->y[v];
171  rect.boundary[2] = 0;
172  rect.boundary[5] = 0;
173 
174  /* Already registered ? */
175  Vect_reset_list(List);
176  RTreeSearch(RTree, &rect, (void *)add_item, List);
177  G_debug(3, "List : nvalues = %d", List->n_values);
178 
179  if (List->n_values == 0) { /* Not found */
180  /* Add to tree and to structure */
181  RTreeInsertRect(&rect, point, &RTree, 0);
182  if ((point - 1) == apoints) {
183  apoints += 10000;
184  XPnts =
185  (XPNT *) G_realloc(XPnts,
186  (apoints + 1) * sizeof(XPNT));
187  }
188  XPnts[point].x = Points->x[v];
189  XPnts[point].y = Points->y[v];
190  XPnts[point].anchor = -1;
191  point++;
192  }
193  }
194  }
195  G_percent(line_idx, List_lines->n_values, 2); /* finish it */
196 
197  npoints = point - 1;
198 
199  /* Go through all registered points and if not yet marked mark it as anchor and assign this anchor
200  * to all not yet marked points in threshold */
201 
202  G_verbose_message(_("Snap vertices Pass 2: assign anchor vertices"));
203 
204  nanchors = ntosnap = 0;
205  for (point = 1; point <= npoints; point++) {
206  int i;
207 
208  G_percent(point, npoints, 2);
209 
210  G_debug(3, " point = %d", point);
211 
212  if (XPnts[point].anchor >= 0)
213  continue;
214 
215  XPnts[point].anchor = 0; /* make it anchor */
216  nanchors++;
217 
218  /* Find points in threshold */
219  rect.boundary[0] = XPnts[point].x - thresh;
220  rect.boundary[3] = XPnts[point].x + thresh;
221  rect.boundary[1] = XPnts[point].y - thresh;
222  rect.boundary[4] = XPnts[point].y + thresh;
223  rect.boundary[2] = 0;
224  rect.boundary[5] = 0;
225 
226  Vect_reset_list(List);
227  RTreeSearch(RTree, &rect, (void *)add_item, List);
228  G_debug(4, " %d points in threshold box", List->n_values);
229 
230  for (i = 0; i < List->n_values; i++) {
231  int pointb;
232  double dx, dy, dist2;
233 
234  pointb = List->value[i];
235  if (pointb == point)
236  continue;
237 
238  dx = XPnts[pointb].x - XPnts[point].x;
239  dy = XPnts[pointb].y - XPnts[point].y;
240  dist2 = dx * dx + dy * dy;
241 
242  if (dist2 > thresh2) /* outside threshold */
243  continue;
244 
245  /* doesn't have an anchor yet */
246  if (XPnts[pointb].anchor == -1) {
247  XPnts[pointb].anchor = point;
248  ntosnap++;
249  }
250  else if (XPnts[pointb].anchor > 0) { /* check distance to previously assigned anchor */
251  double dist2_a;
252 
253  dx = XPnts[XPnts[pointb].anchor].x - XPnts[pointb].x;
254  dy = XPnts[XPnts[pointb].anchor].y - XPnts[pointb].y;
255  dist2_a = dx * dx + dy * dy;
256 
257  /* replace old anchor */
258  if (dist2 < dist2_a) {
259  XPnts[pointb].anchor = point;
260  }
261  }
262  }
263  }
264 
265  /* Go through all lines and:
266  * 1) for all vertices: if not anchor snap it to its anchor
267  * 2) for all segments: snap it to all anchors in threshold (except anchors of vertices of course) */
268 
269  nsnapped = ncreated = 0;
270 
271  G_verbose_message(_("Snap vertices Pass 3: snap to assigned points"));
272 
273  for (line_idx = 0; line_idx < List_lines->n_values; line_idx++) {
274  int v, spoint, anchor;
275  int changed = 0;
276 
277  G_percent(line_idx, List_lines->n_values, 2);
278 
279  line = List_lines->value[line_idx];
280 
281  G_debug(3, "line = %d", line);
282  if (!Vect_line_alive(Map, line))
283  continue;
284 
285  ltype = Vect_read_line(Map, Points, Cats, line);
286 
287  if (Points->n_points >= aindex) {
288  aindex = Points->n_points;
289  Index = (int *)G_realloc(Index, aindex * sizeof(int));
290  }
291 
292  /* Snap all vertices */
293  for (v = 0; v < Points->n_points; v++) {
294  /* Box */
295  rect.boundary[0] = Points->x[v];
296  rect.boundary[3] = Points->x[v];
297  rect.boundary[1] = Points->y[v];
298  rect.boundary[4] = Points->y[v];
299  rect.boundary[2] = 0;
300  rect.boundary[5] = 0;
301 
302  /* Find point ( should always find one point ) */
303  Vect_reset_list(List);
304 
305  RTreeSearch(RTree, &rect, (void *)add_item, List);
306 
307  spoint = List->value[0];
308  anchor = XPnts[spoint].anchor;
309 
310  if (anchor > 0) { /* to be snapped */
311  Points->x[v] = XPnts[anchor].x;
312  Points->y[v] = XPnts[anchor].y;
313  nsnapped++;
314  changed = 1;
315  Index[v] = anchor; /* point on new location */
316  }
317  else {
318  Index[v] = spoint; /* old point */
319  }
320  }
321 
322  /* New points */
323  Vect_reset_line(NPoints);
324 
325  /* Snap all segments to anchors in threshold */
326  for (v = 0; v < Points->n_points - 1; v++) {
327  int i;
328  double x1, x2, y1, y2, xmin, xmax, ymin, ymax;
329 
330  G_debug(3, " segment = %d end anchors : %d %d", v, Index[v],
331  Index[v + 1]);
332 
333  x1 = Points->x[v];
334  x2 = Points->x[v + 1];
335  y1 = Points->y[v];
336  y2 = Points->y[v + 1];
337 
338  Vect_append_point(NPoints, Points->x[v], Points->y[v],
339  Points->z[v]);
340 
341  /* Box */
342  if (x1 <= x2) {
343  xmin = x1;
344  xmax = x2;
345  }
346  else {
347  xmin = x2;
348  xmax = x1;
349  }
350  if (y1 <= y2) {
351  ymin = y1;
352  ymax = y2;
353  }
354  else {
355  ymin = y2;
356  ymax = y1;
357  }
358 
359  rect.boundary[0] = xmin - thresh;
360  rect.boundary[3] = xmax + thresh;
361  rect.boundary[1] = ymin - thresh;
362  rect.boundary[4] = ymax + thresh;
363  rect.boundary[2] = 0;
364  rect.boundary[5] = 0;
365 
366  /* Find points */
367  Vect_reset_list(List);
368  RTreeSearch(RTree, &rect, (void *)add_item, List);
369 
370  G_debug(3, " %d points in box", List->n_values);
371 
372  /* Snap to anchor in threshold different from end points */
373  nnew = 0;
374  for (i = 0; i < List->n_values; i++) {
375  double dist2, along;
376 
377  spoint = List->value[i];
378  G_debug(4, " spoint = %d anchor = %d", spoint,
379  XPnts[spoint].anchor);
380 
381  if (spoint == Index[v] || spoint == Index[v + 1])
382  continue; /* end point */
383  if (XPnts[spoint].anchor > 0)
384  continue; /* point is not anchor */
385 
386  /* Check the distance */
387  dist2 =
388  dig_distance2_point_to_line(XPnts[spoint].x,
389  XPnts[spoint].y, 0, x1, y1, 0,
390  x2, y2, 0, 0, NULL, NULL,
391  NULL, &along, NULL);
392 
393  G_debug(4, " distance = %lf", sqrt(dist2));
394 
395  if (dist2 <= thresh2) {
396  G_debug(4, " anchor in thresh, along = %lf", along);
397 
398  if (nnew == anew) {
399  anew += 100;
400  New = (NEW *) G_realloc(New, anew * sizeof(NEW));
401  }
402  New[nnew].anchor = spoint;
403  New[nnew].along = along;
404  nnew++;
405  }
406  }
407  G_debug(3, " nnew = %d", nnew);
408  /* insert new vertices */
409  if (nnew > 0) {
410  /* sort by distance along the segment */
411  qsort(New, sizeof(char) * nnew, sizeof(NEW), sort_new);
412 
413  for (i = 0; i < nnew; i++) {
414  anchor = New[i].anchor;
415  /* Vect_line_insert_point ( Points, ++v, XPnts[anchor].x, XPnts[anchor].y, 0); */
416  Vect_append_point(NPoints, XPnts[anchor].x,
417  XPnts[anchor].y, 0);
418  ncreated++;
419  }
420  changed = 1;
421  }
422  }
423 
424  /* append end point */
425  v = Points->n_points - 1;
426  Vect_append_point(NPoints, Points->x[v], Points->y[v], Points->z[v]);
427 
428  if (changed) { /* rewrite the line */
429  Vect_line_prune(NPoints); /* remove duplicates */
430  if (NPoints->n_points > 1 || ltype & GV_LINES) {
431  Vect_rewrite_line(Map, line, ltype, NPoints, Cats);
432  }
433  else {
434  Vect_delete_line(Map, line);
435  }
436  if (Err) {
437  Vect_write_line(Err, ltype, Points, Cats);
438  }
439  }
440  } /* for each line */
441  G_percent(line_idx, List_lines->n_values, 2); /* finish it */
442 
443  Vect_destroy_line_struct(Points);
444  Vect_destroy_line_struct(NPoints);
446  G_free(XPnts);
447  G_free(Index);
448  G_free(New);
449  RTreeDestroyNode(RTree);
450 
451  G_verbose_message(_("Snapped vertices: %d"), nsnapped);
452  G_verbose_message(_("New vertices: %d"), ncreated);
453 }
454 
455 /* for qsort */
456 static int sort_new(const void *pa, const void *pb)
457 {
458  NEW *p1 = (NEW *) pa;
459  NEW *p2 = (NEW *) pb;
460 
461  if (p1->along < p2->along)
462  return -1;
463  if (p1->along > p2->along)
464  return 1;
465  return 1;
466 }
467 
480 void
481 Vect_snap_lines(struct Map_info *Map, int type, double thresh,
482  struct Map_info *Err)
483 {
484  int line, nlines, ltype;
485 
486  struct ilist *List;
487 
488  List = Vect_new_list();
489 
490  nlines = Vect_get_num_lines(Map);
491 
492  for (line = 1; line <= nlines; line++) {
493  G_debug(3, "line = %d", line);
494 
495  if (!Vect_line_alive(Map, line))
496  continue;
497 
498  ltype = Vect_read_line(Map, NULL, NULL, line);
499 
500  if (!(ltype & type))
501  continue;
502 
503  /* Vect_list_append(List, line); */
504  dig_list_add(List, line);
505  }
506 
507  Vect_snap_lines_list(Map, List, thresh, Err);
508 
509  Vect_destroy_list(List);
510 
511  return;
512 }
513 
534 int
535 Vect_snap_line(struct Map_info *Map, struct ilist *reflist,
536  struct line_pnts *Points, double thresh,
537  int *nsnapped, int *ncreated)
538 {
539  struct line_pnts *LPoints, *NPoints;
540  struct line_cats *Cats;
541  int i, v, line, nlines;
542  int changed;
543  double thresh2;
544 
545  int point; /* index in points array */
546  int segment; /* index in segments array */
547  int asegments; /* number of allocated segments */
548  int apoints, nvertices; /* number of allocated points and registered vertices */
549  XSEG *XSegs = NULL; /* Array of segments */
550  XPNT *XPnts = NULL; /* Array of points */
551  NEW2 *New = NULL; /* Array of new points */
552  int anew = 0, nnew; /* allocated new points , number of new points */
553  struct ilist *List;
554 
555  struct Node *pnt_tree, /* spatial index for reference points */
556  *seg_tree; /* spatial index for reference segments */
557  struct Rect rect;
558 
559  rect.boundary[0] = 0;
560  rect.boundary[1] = 0;
561  rect.boundary[2] = 0;
562  rect.boundary[3] = 0;
563  rect.boundary[4] = 0;
564  rect.boundary[5] = 0;
565 
566  changed = 0;
567  if (nsnapped)
568  *nsnapped = 0;
569  if (ncreated)
570  *ncreated = 0;
571 
572  point = Points->n_points;
573  Vect_line_prune(Points);
574  if (point != Points->n_points)
575  changed = 1;
576 
577  nlines = reflist->n_values;
578  if (nlines < 1)
579  return changed;
580 
581  LPoints = Vect_new_line_struct();
582  NPoints = Vect_new_line_struct();
583  Cats = Vect_new_cats_struct();
584  List = Vect_new_list();
585  pnt_tree = RTreeNewIndex();
586  seg_tree = RTreeNewIndex();
587 
588  thresh2 = thresh * thresh;
589 
590  point = segment = 1; /* index starts from 1 ! */
591  nvertices = 0;
592  asegments = 0;
593  apoints = 0;
594 
595  /* Add all vertices and all segments of all reference lines
596  * to spatial indices */
597  nlines = reflist->n_values;
598  for (i = 0; i < nlines; i++) {
599 
600  line = reflist->value[i];
601 
602  G_debug(3, "line = %d", line);
603  if (!Vect_line_alive(Map, line))
604  continue;
605 
606  Vect_read_line(Map, LPoints, Cats, line);
607  Vect_line_prune(LPoints);
608 
609  for (v = 0; v < LPoints->n_points; v++) {
610  G_debug(3, " vertex v = %d", v);
611  nvertices++;
612 
613  /* Box */
614  rect.boundary[0] = LPoints->x[v];
615  rect.boundary[3] = LPoints->x[v];
616  rect.boundary[1] = LPoints->y[v];
617  rect.boundary[4] = LPoints->y[v];
618 
619  /* Already registered ? */
620  Vect_reset_list(List);
621  RTreeSearch(pnt_tree, &rect, (void *)find_item, List);
622  G_debug(3, "List : nvalues = %d", List->n_values);
623 
624  if (List->n_values == 0) { /* Not found */
625 
626  /* Add to points tree */
627  RTreeInsertRect(&rect, point, &pnt_tree, 0);
628 
629  if ((point - 1) == apoints) {
630  apoints += 10000;
631  XPnts =
632  (XPNT *) G_realloc(XPnts,
633  (apoints + 1) * sizeof(XPNT));
634  }
635  XPnts[point].x = LPoints->x[v];
636  XPnts[point].y = LPoints->y[v];
637  XPnts[point].anchor = 0;
638 
639  point++;
640  }
641 
642  /* reference segments */
643  if (v) {
644  /* Box */
645  if (LPoints->x[v - 1] < LPoints->x[v]) {
646  rect.boundary[0] = LPoints->x[v - 1];
647  rect.boundary[3] = LPoints->x[v];
648  }
649  else {
650  rect.boundary[0] = LPoints->x[v];
651  rect.boundary[3] = LPoints->x[v - 1];
652  }
653  if (LPoints->y[v - 1] < LPoints->y[v]) {
654  rect.boundary[1] = LPoints->y[v - 1];
655  rect.boundary[4] = LPoints->y[v];
656  }
657  else {
658  rect.boundary[1] = LPoints->y[v];
659  rect.boundary[4] = LPoints->y[v - 1];
660  }
661 
662  /* do not check for duplicates, too costly
663  * because different segments can have identical boxes */
664  RTreeInsertRect(&rect, segment, &seg_tree, 0);
665 
666  if ((segment - 1) == asegments) {
667  asegments += 1000;
668  XSegs =
669  (XSEG *) G_realloc(XSegs,
670  (asegments + 1) * sizeof(XSEG));
671  }
672  XSegs[segment].x1 = LPoints->x[v - 1];
673  XSegs[segment].x2 = LPoints->x[v];
674  XSegs[segment].y1 = LPoints->y[v - 1];
675  XSegs[segment].y2 = LPoints->y[v];
676 
677  segment++;
678  }
679  }
680  }
681 
682  /* go through all vertices of the line to snap */
683  for (v = 0; v < Points->n_points; v++) {
684  double dist2, tmpdist2;
685  double x, y;
686 
687  dist2 = thresh2 + thresh2;
688  x = Points->x[v];
689  y = Points->y[v];
690 
691  /* Box */
692  rect.boundary[0] = Points->x[v] - thresh;
693  rect.boundary[3] = Points->x[v] + thresh;
694  rect.boundary[1] = Points->y[v] - thresh;
695  rect.boundary[4] = Points->y[v] + thresh;
696 
697  /* find nearest reference vertex */
698  Vect_reset_list(List);
699 
700  RTreeSearch(pnt_tree, &rect, (void *)add_item, List);
701 
702  for (i = 0; i < List->n_values; i++) {
703  double dx, dy;
704 
705  point = List->value[i];
706 
707  dx = Points->x[v] - XPnts[point].x;
708  dy = Points->y[v] - XPnts[point].y;
709 
710  tmpdist2 = dx * dx + dy * dy;
711 
712  if (tmpdist2 < dist2) {
713  dist2 = tmpdist2;
714 
715  x = XPnts[point].x;
716  y = XPnts[point].y;
717  }
718  }
719 
720  if (dist2 <= thresh2 && dist2 > 0) {
721  Points->x[v] = x;
722  Points->y[v] = y;
723 
724  changed = 1;
725  if (nsnapped)
726  (*nsnapped)++;
727  }
728  }
729 
730  /* go through all vertices of the line to snap */
731  for (v = 0; v < Points->n_points; v++) {
732  double dist2, tmpdist2;
733  double x, y;
734 
735  dist2 = thresh2 + thresh2;
736  x = Points->x[v];
737  y = Points->y[v];
738 
739  /* Box */
740  rect.boundary[0] = Points->x[v] - thresh;
741  rect.boundary[3] = Points->x[v] + thresh;
742  rect.boundary[1] = Points->y[v] - thresh;
743  rect.boundary[4] = Points->y[v] + thresh;
744 
745  /* find nearest reference segment */
746  Vect_reset_list(List);
747 
748  RTreeSearch(seg_tree, &rect, (void *)add_item, List);
749 
750  for (i = 0; i < List->n_values; i++) {
751  double tmpx, tmpy;
752  int segment, status;
753 
754  segment = List->value[i];
755 
756  /* Check the distance */
757  tmpdist2 =
758  dig_distance2_point_to_line(Points->x[v],
759  Points->y[v],
760  0,
761  XSegs[segment].x1,
762  XSegs[segment].y1,
763  0,
764  XSegs[segment].x2,
765  XSegs[segment].y2,
766  0,
767  0, &tmpx, &tmpy, NULL,
768  NULL, &status);
769 
770  if (tmpdist2 < dist2 && status == 0) {
771  dist2 = tmpdist2;
772 
773  x = tmpx;
774  y = tmpy;
775  }
776  }
777 
778  if (dist2 <= thresh2 && dist2 > 0) {
779  Points->x[v] = x;
780  Points->y[v] = y;
781 
782  changed = 1;
783  if (nsnapped)
784  (*nsnapped)++;
785  }
786  }
787 
788  RTreeDestroyNode(seg_tree);
789  G_free(XSegs);
790 
791  /* go through all segments of the line to snap */
792  /* find nearest reference vertex, add this vertex */
793  for (v = 0; v < Points->n_points - 1; v++) {
794  double x1, x2, y1, y2;
795  double xmin, xmax, ymin, ymax;
796 
797  x1 = Points->x[v];
798  x2 = Points->x[v + 1];
799  y1 = Points->y[v];
800  y2 = Points->y[v + 1];
801 
802  Vect_append_point(NPoints, Points->x[v], Points->y[v],
803  Points->z[v]);
804 
805  /* Box */
806  if (x1 <= x2) {
807  xmin = x1;
808  xmax = x2;
809  }
810  else {
811  xmin = x2;
812  xmax = x1;
813  }
814  if (y1 <= y2) {
815  ymin = y1;
816  ymax = y2;
817  }
818  else {
819  ymin = y2;
820  ymax = y1;
821  }
822 
823  rect.boundary[0] = xmin - thresh;
824  rect.boundary[3] = xmax + thresh;
825  rect.boundary[1] = ymin - thresh;
826  rect.boundary[4] = ymax + thresh;
827 
828  /* Find points */
829  Vect_reset_list(List);
830  RTreeSearch(pnt_tree, &rect, (void *)add_item, List);
831 
832  G_debug(3, " %d points in box", List->n_values);
833 
834  /* Snap to vertex in threshold different from end points */
835  nnew = 0;
836  for (i = 0; i < List->n_values; i++) {
837  double dist2, along;
838  int status;
839 
840  point = List->value[i];
841 
842  if (Points->x[v] == XPnts[i].x &&
843  Points->y[v] == XPnts[i].y)
844  continue; /* start point */
845 
846  if (Points->x[v + 1] == XPnts[i].x &&
847  Points->y[v + 1] == XPnts[i].y)
848  continue; /* end point */
849 
850  /* Check the distance */
851  dist2 =
852  dig_distance2_point_to_line(XPnts[i].x,
853  XPnts[i].y,
854  0, x1, y1, 0,
855  x2, y2, 0, 0, NULL, NULL,
856  NULL, &along, &status);
857 
858  if (dist2 <= thresh2 && status == 0) {
859  G_debug(4, " anchor in thresh, along = %lf", along);
860 
861  if (nnew == anew) {
862  anew += 100;
863  New = (NEW2 *) G_realloc(New, anew * sizeof(NEW2));
864  }
865  New[nnew].x = XPnts[i].x;
866  New[nnew].y = XPnts[i].y;
867  New[nnew].along = along;
868  nnew++;
869  }
870  G_debug(3, "dist: %g, thresh: %g", dist2, thresh2);
871  }
872  G_debug(3, " nnew = %d", nnew);
873  /* insert new vertices */
874  if (nnew > 0) {
875  /* sort by distance along the segment */
876  qsort(New, nnew, sizeof(NEW2), sort_new2);
877 
878  for (i = 0; i < nnew; i++) {
879  Vect_append_point(NPoints, New[i].x, New[i].y, 0);
880  if (ncreated)
881  (*ncreated)++;
882  }
883  changed = 1;
884  }
885  }
886 
887  /* append end point */
888  v = Points->n_points - 1;
889  Vect_append_point(NPoints, Points->x[v], Points->y[v], Points->z[v]);
890 
891  if (Points->n_points != NPoints->n_points) {
892  Vect_line_prune(NPoints); /* remove duplicates */
893  Vect_reset_line(Points);
894  Vect_append_points(Points, NPoints, GV_FORWARD);
895  }
896 
897  Vect_destroy_line_struct(LPoints);
898  Vect_destroy_line_struct(NPoints);
900  Vect_destroy_list(List);
901  G_free(New);
902  G_free(XPnts);
903  RTreeDestroyNode(pnt_tree);
904 
905  return changed;
906 }
RectReal boundary[NUMSIDES]
Definition: index.h:42
int Vect_destroy_list(struct ilist *list)
Frees all memory associated with a struct ilist, including the struct itself.
void G_free(void *buf)
Free allocated memory.
Definition: gis/alloc.c:142
double y
double xmax
Definition: dataquad.c:293
struct triple * point
Definition: dataquad.c:294
int dig_list_add(struct ilist *list, int val)
double x
double along
Definition: Vlib/snap.c:54
struct line_pnts * Vect_new_line_struct()
Creates and initializes a struct line_pnts.
Definition: line.c:57
struct ilist * Vect_new_list(void)
Creates and initializes a struct ilist.
int RTreeSearch(struct Node *N, struct Rect *R, SearchHitCallback shcb, void *cbarg)
Definition: index.h:56
double xmin
Definition: dataquad.c:293
void RTreeDestroyNode(struct Node *)
Definition: node.c:217
int anchor
Definition: Vlib/snap.c:34
int Vect_append_points(struct line_pnts *Points, struct line_pnts *APoints, int direction)
Appends points to the end of a line.
Definition: line.c:312
int Vect_reset_line(struct line_pnts *Points)
Reset line.
Definition: line.c:148
double ymin
Definition: dataquad.c:293
Definition: Vlib/snap.c:40
double dig_distance2_point_to_line(double x, double y, double z, double x1, double y1, double z1, double x2, double y2, double z2, int with_z, double *px, double *py, double *pz, double *pdist, int *status)
int RTreeInsertRect(struct Rect *R, int Tid, struct Node **Root, int Level)
int y
Definition: plot.c:34
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:168
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:481
double x
Definition: Vlib/snap.c:54
int G_percent(long n, long d, int s)
Print percent complete messages.
Definition: percent.c:63
double y2
Definition: Vlib/snap.c:42
#define NEW
Definition: ask.c:100
double y
Definition: Vlib/snap.c:54
void G_verbose_message(const char *msg,...)
Print a message to stderr but only if module is in verbose mode.
Definition: lib/gis/error.c:95
int Vect_rewrite_line(struct Map_info *Map, int line, int type, struct line_pnts *points, struct line_cats *cats)
Rewrites feature info at the given offset.
ITEM * find_item(PAD *pad, const char *name)
Definition: pad.c:135
double x2
Definition: Vlib/snap.c:42
void Vect_snap_lines_list(struct Map_info *Map, struct ilist *List_lines, double thresh, struct Map_info *Err)
Snap selected lines to existing vertex in threshold.
Definition: Vlib/snap.c:110
int GV_LINES
Definition: vdigit/main.py:24
int Vect_reset_list(struct ilist *list)
Reset ilist structure.
int Vect_destroy_cats_struct(struct line_cats *p)
Frees all memory associated with line_cats structure, including the struct itself.
double ymax
Definition: dataquad.c:293
double x1
Definition: Vlib/snap.c:42
int Vect_line_alive(struct Map_info *Map, int line)
Check if feature is alive or dead.
struct line_cats * Vect_new_cats_struct()
Creates and initializes line_cats structure.
return NULL
Definition: dbfopen.c:1394
int Vect_line_prune(struct line_pnts *Points)
Remove duplicate points, i.e. zero length segments.
Definition: line.c:255
int Vect_get_num_lines(struct Map_info *map)
Fetch number of features (points, lines, boundaries, centroids) in vector map.
Definition: level_two.c:69
double z
Definition: Vlib/snap.c:54
Definition: Vlib/snap.c:52
tuple Map
Definition: render.py:1310
int G_debug(int level, const char *msg,...)
Print debugging message.
Definition: gis/debug.c:51
int Vect_delete_line(struct Map_info *Map, int line)
Delete feature.
double y1
Definition: Vlib/snap.c:42
struct Node * RTreeNewIndex(void)
double along
Definition: Vlib/snap.c:49
long Vect_write_line(struct Map_info *Map, int type, struct line_pnts *points, struct line_cats *cats)
Writes new feature to the end of file (table)
Definition: Vlib/snap.c:46
Definition: index.h:40
int Vect_snap_line(struct Map_info *Map, struct ilist *reflist, struct line_pnts *Points, double thresh, int *nsnapped, int *ncreated)
Snap a line to reference lines in Map with threshold.
Definition: Vlib/snap.c:535
int anchor
Definition: Vlib/snap.c:48
int Vect_destroy_line_struct(struct line_pnts *p)
Frees all memory associated with a struct line_pnts, including the struct itself. ...
Definition: line.c:90
int Vect_read_line(struct Map_info *Map, struct line_pnts *line_p, struct line_cats *line_c, int line)
Read vector feature.