GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
merge.c
Go to the documentation of this file.
1 /*!
2  \file lib/vector/vedit/merge.c
3 
4  \brief Vedit library - merge lines
5 
6  (C) 2006-2008 by the GRASS Development Team
7 
8  This program is free software under the GNU General Public License
9  (>=v2). Read the file COPYING that comes with GRASS for details.
10 
11  \author Jachym Cepicky <jachym.cepicky gmail.com>
12  \author Martin Landa <landa.martin gmail.com>
13 */
14 
15 #include <grass/vedit.h>
16 
17 /*!
18  \brief Merge two given lines a, b
19 
20  a : Points1/Cats1
21  b : Points2/Cats2
22  merged line : Points/Cats
23 
24  \param Points1,Cats1 first line
25  \param Points2,Cats2 second line
26  \param thresh threshold value
27  \param[out] Points result line
28 
29  \return 1 on success
30  \return 0 on error
31 */
32 static int merge_lines(struct line_pnts *Points1, struct line_cats *Cats1,
33  struct line_pnts *Points2, struct line_cats *Cats2,
34  double thresh, struct line_pnts **Points);
35 
36 /*!
37  \brief Merge lines/boundaries
38 
39  At least two lines need to be given.
40 
41  \param Map pointer to Map_info
42  \param List list of selected lines
43 
44  \return number of merged lines
45  \return -1 on error
46 */
47 int Vedit_merge_lines(struct Map_info *Map, struct ilist *List)
48 {
49  struct ilist *List_in_box;
50 
51  struct line_pnts *Points1, *Points2, *Points;
52  struct line_cats *Cats1, *Cats2;
53 
54  int line_i, i, j;
55  int line, line1, type1, line2;
56  int do_merge;
57 
58  /* number of lines (original, selected, merged) */
59  int nlines, nlines_merged;
60 
61  nlines_merged = 0;
62 
63  if (List->n_values < 2) {
64  return 0;
65  }
66 
67  G_debug(1, "Vedit_merge_lines(): merging %d lines", List->n_values);
68 
69  Points1 = Vect_new_line_struct();
70  Cats1 = Vect_new_cats_struct();
71  Points2 = Vect_new_line_struct();
72  Cats2 = Vect_new_cats_struct();
73  Points = Vect_new_line_struct();
74 
75  List_in_box = Vect_new_list();
76 
77  nlines = Vect_get_num_lines(Map);
78 
79  /* merge lines */
80  for (line_i = 0; line_i < List->n_values; line_i++) {
81  line1 = List->value[line_i];
82 
83  if (!Vect_line_alive(Map, line1))
84  continue;
85 
86  type1 = Vect_read_line(Map, Points1, Cats1, line1);
87 
88  if (!(type1 & GV_LINES))
89  continue;
90 
91  /* remove duplicate points */
92  Vect_line_prune(Points1);
93 
94  if (Points1->n_points < 2) {
95  G_debug(3, "Vedit_merge_lines(): skipping zero length line");
96  continue;
97  }
98 
99  Vect_reset_line(Points);
100 
101  for (i = 0; i < Points1->n_points; i += Points1->n_points - 1) {
102  Vect_reset_list(List_in_box);
103 
104  /* define searching region */
105  Vect_reset_line(Points2);
106  /*
107  Vect_append_point (Points2, Points1 -> x[i] - thresh,
108  Points1 -> y[i] + thresh, Points1 -> z[i]);
109  Vect_append_point (Points2, Points1 -> x[i] + thresh,
110  Points1 -> y[i] + thresh, Points1 -> z[i]);
111  Vect_append_point (Points2, Points1 -> x[i] + thresh,
112  Points1 -> y[i] - thresh, Points1 -> z[i]);
113  Vect_append_point (Points2, Points1 -> x[i] - thresh,
114  Points1 -> y[i] - thresh, Points1 -> z[i]);
115  */
116  Vect_append_point(Points2, Points1->x[i],
117  Points1->y[i], Points1->z[i]);
118 
119  /*
120  * merge lines only if two lines found in the region
121  * i.e. the current line and an adjacent line
122  */
123  /* NOTE
124  * - this merges two lines also if more than two lines are
125  * found in the region, but only two of these lines are
126  * in the List
127  * - this not only merges lines connected by end points
128  * but also any adjacent line with a mid point identical
129  * to one of the end points of the current line
130  */
131  if (0 < Vect_find_line_list(Map, Points1->x[i], Points1->y[i],
132  Points1->z[i], GV_LINES, 0, 0,
133  NULL, List_in_box)) {
134  do_merge = 1;
135  line2 = -1;
136  for (j = 0; do_merge && j < List_in_box->n_values; j++) {
137  if (List_in_box->value[j] == line1 ||
138  !Vect_line_alive(Map, List_in_box->value[j]))
139  continue;
140 
141  if (Vect_val_in_list(List, List_in_box->value[j])) {
142 
143  Vect_read_line(Map, Points2, Cats2, List_in_box->value[j]);
144  Vect_line_prune(Points2);
145  if (Points2->n_points == 1) {
146  line2 = List_in_box->value[j];
147  do_merge = 1;
148  break;
149  }
150  if (line2 > 0) {
151  /* three lines found
152  * selected lines will be not merged
153  */
154  do_merge = 0;
155  }
156  else {
157  line2 = List_in_box->value[j];
158  }
159  }
160  }
161 
162  if (!do_merge || line2 < 0)
163  continue;
164 
165  Vect_read_line(Map, Points2, Cats2, line2);
166 
167  merge_lines(Points1, Cats1, Points2, Cats2, -1.0, &Points); /* do not use threshold value */
168 
169  G_debug(3, "Vedit_merge_lines(): lines=%d,%d", line1, line2);
170 
171  if (Points->n_points > 0) {
172  if (Vect_delete_line(Map, line2) == -1) {
173  return -1;
174  }
175 
176  if (line2 <= nlines)
177  nlines_merged++;
178  }
179  }
180  } /* for each node */
181 
182  if (Points->n_points > 0) {
183  line = Vect_rewrite_line(Map, line1, type1, Points, Cats1);
184  if (line < 0) {
185  return -1;
186  }
187 
188  if (line1 <= nlines)
189  nlines_merged++;
190 
191  /* update number of lines */
192  G_ilist_add(List, line);
193  }
194  } /* for each line */
195 
196  /* destroy structures */
197  Vect_destroy_line_struct(Points1);
198  Vect_destroy_line_struct(Points2);
199  Vect_destroy_line_struct(Points);
200 
203 
204  return nlines_merged;
205 }
206 
207 static int merge_lines(struct line_pnts *Points1, struct line_cats *Cats1,
208  struct line_pnts *Points2, struct line_cats *Cats2,
209  double thresh, struct line_pnts **Points)
210 {
211  struct line_pnts *ps = *Points;
212  struct line_cats *cs = Cats1;
213 
214  int i, mindistidx;
215  double mindist;
216 
217  /* find mininal distance and its index */
218  mindist = Vedit_get_min_distance(Points1, Points2, 0, /* TODO 3D */
219  &mindistidx);
220 
221  G_debug(3, " merge line ? index: %d, mindist: %g, thresh: %g",
222  mindistidx, mindist, thresh);
223 
224  if (thresh > 0 && mindist > thresh) {
225  return 0;
226  }
227 
228  /* set index and other things */
229  switch (mindistidx) {
230  /* for each mindistidx create new line */
231  case 0:
232  Vect_append_points(ps, Points2, GV_BACKWARD);
233  if (ps->n_points == Points2->n_points)
234  Vect_append_points(ps, Points1, GV_FORWARD);
235  break;
236  case 1:
237  Vect_append_points(ps, Points2, GV_FORWARD);
238  if (ps->n_points == Points2->n_points)
239  Vect_append_points(ps, Points1, GV_FORWARD);
240  break;
241  case 2:
242  if (ps->n_points == 0)
243  Vect_append_points(ps, Points1, GV_FORWARD);
244  Vect_append_points(ps, Points2, GV_FORWARD);
245  break;
246  case 3:
247  if (ps->n_points == 0)
248  Vect_append_points(ps, Points1, GV_FORWARD);
249  Vect_append_points(ps, Points2, GV_BACKWARD);
250  break;
251  default:
252  break;
253  }
254 
255  /* remove duplicate points */
256  Vect_line_prune(ps);
257 
258  /* copy categories if needed */
259  for (i = 0; i < Cats2->n_cats; i++) {
260  Vect_cat_set(cs, Cats2->field[i], Cats2->cat[i]);
261  }
262 
263  return 1;
264 }
int Vect_append_points(struct line_pnts *, const struct line_pnts *, int)
Appends points to the end of a line.
Definition: line.c:337
#define GV_FORWARD
Line direction indicator forward/backward.
Definition: dig_defines.h:178
int Vect_reset_list(struct ilist *)
Reset ilist structure.
struct ps_state ps
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
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)
#define GV_BACKWARD
Definition: dig_defines.h:179
int n_points
Number of points.
Definition: dig_structs.h:1692
int Vect_val_in_list(const struct ilist *, int)
Find a given item in the list.
int n_values
Number of values in the list.
Definition: gis.h:709
int Vect_line_prune(struct line_pnts *)
Remove duplicate points, i.e. zero length segments.
Definition: line.c:281
#define NULL
Definition: ccmath.h:32
double Vedit_get_min_distance(struct line_pnts *, struct line_pnts *, int, int *)
Calculate distances between two lines.
Feature category info.
Definition: dig_structs.h:1702
double * x
Array of X coordinates.
Definition: dig_structs.h:1680
void G_ilist_add(struct ilist *, int)
Add item to ilist.
Definition: ilist.c:77
Feature geometry info - coordinates.
Definition: dig_structs.h:1675
int Vedit_merge_lines(struct Map_info *Map, struct ilist *List)
Merge lines/boundaries.
Definition: merge.c:47
struct line_pnts * Vect_new_line_struct(void)
Creates and initializes a line_pnts structure.
Definition: line.c:45
void Vect_destroy_cats_struct(struct line_cats *)
Frees all memory associated with line_cats structure, including the struct itself.
int n_cats
Number of categories attached to element.
Definition: dig_structs.h:1715
int * cat
Array of categories.
Definition: dig_structs.h:1711
int Vect_append_point(struct line_pnts *, double, double, double)
Appends one point to the end of a line.
Definition: line.c:149
Vector map info.
Definition: dig_structs.h:1259
double * y
Array of Y coordinates.
Definition: dig_structs.h:1684
struct ilist * Vect_new_list(void)
Creates and initializes a struct ilist.
int Vect_delete_line(struct Map_info *, off_t)
Delete existing feature (topological level required)
struct line_cats * Vect_new_cats_struct(void)
Creates and initializes line_cats structure.
int Vect_line_alive(const struct Map_info *, int)
Check if feature is alive or dead (topological level required)
double * z
Array of Z coordinates.
Definition: dig_structs.h:1688
List of integers.
Definition: gis.h:700
int * field
Array of layers (fields)
Definition: dig_structs.h:1707
int * value
Array of values.
Definition: gis.h:705
#define GV_LINES
Definition: dig_defines.h:192
int Vect_find_line_list(struct Map_info *, double, double, double, int, double, int, const struct ilist *, struct ilist *)
Find the nearest line(s).
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
int Vect_read_line(const struct Map_info *, struct line_pnts *, struct line_cats *, int)
Read vector feature (topological level required)
int G_debug(int, const char *,...) __attribute__((format(printf
struct line_cats * Cats2
void Vect_reset_line(struct line_pnts *)
Reset line.
Definition: line.c:130
int Vect_cat_set(struct line_cats *, int, int)
Add new field/cat to category structure if doesn&#39;t exist yet.