GRASS 8 Programmer's Manual  8.5.0dev(2025)-d272f2f102
merge_lines.c
Go to the documentation of this file.
1 /*!
2  \file lib/vector/Vlib/merge_lines.c
3 
4  \brief Vector library - clean geometry (merge lines/boundaries)
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
11  GNU General Public License (>=v2).
12  Read the file COPYING that comes with GRASS
13  for details.
14 
15  \author Markus Metz
16  */
17 
18 #include <stdlib.h>
19 #include <math.h>
20 #include <grass/vector.h>
21 #include <grass/glocale.h>
22 
23 /* compare category structures
24  * return 0 identical
25  * return 1 not identical
26  */
27 static int compare_cats(struct line_cats *ACats, struct line_cats *BCats)
28 {
29  int i, j;
30 
31  if (ACats->n_cats == 0 || BCats->n_cats == 0) {
32  if (ACats->n_cats == 0 && BCats->n_cats == 0)
33  return 0;
34 
35  if (ACats->n_cats == 0 && BCats->n_cats > 0)
36  return 1;
37 
38  if (ACats->n_cats > 0 && BCats->n_cats == 0)
39  return 1;
40  }
41 
42  for (i = 0; i < ACats->n_cats; i++) {
43  int found = 0;
44 
45  for (j = 0; j < BCats->n_cats; j++) {
46  if (ACats->cat[i] == BCats->cat[j] &&
47  ACats->field[i] == BCats->field[j]) {
48  found = 1;
49  break;
50  }
51  }
52  if (!found)
53  return 1;
54  }
55 
56  return 0;
57 }
58 
59 /*!
60  \brief Merge lines or boundaries in vector map.
61 
62  Merges lines specified by type in vector map.
63  Useful for generalization and smoothing.
64  Adjacent boundaries are merged as long as topology is maintained.
65  Adjacent lines are merged as long as there are exactly two different
66  lines with identical categories connected at a given node.
67  Zero-length lines need to be removed first.
68  GV_BUILD_BASE as topo build level is sufficient, areas need not be built.
69 
70  \param Map input vector map
71  \param type feature type
72  \param[out] Err vector map where merged lines/boundaries will be written or
73  NULL \param new_lines pointer to where number of new lines/boundaries is
74  stored or NULL
75 
76  \return number of merged lines/boundaries
77  */
78 int Vect_merge_lines(struct Map_info *Map, int type, int *new_lines,
79  struct Map_info *Err)
80 {
81  int line, nlines, i, first, last, next_line, curr_line;
82  int merged = 0, newl = 0;
83  int next_node, direction, node_n_lines, ltype, lines_type;
84  struct Plus_head *Plus;
85  struct ilist *List;
86  struct line_pnts *MPoints, *Points;
87  struct line_cats *MCats, *Cats;
88  struct P_line *Line;
89 
90  type &= GV_LINES;
91 
92  if (!(type & GV_LINES)) {
93  G_warning("Merging is done with lines or boundaries only, not with "
94  "other types");
95  return 0;
96  }
97 
98  Plus = &(Map->plus);
99  nlines = Vect_get_num_lines(Map);
100 
101  Points = Vect_new_line_struct();
102  Cats = Vect_new_cats_struct();
103  MPoints = Vect_new_line_struct();
104  MCats = Vect_new_cats_struct();
105  List = Vect_new_list();
106 
107  for (line = 1; line <= nlines; line++) {
108  G_percent(line, nlines, 2);
109 
110  if (!Vect_line_alive(Map, line))
111  continue;
112 
113  Line = Plus->Line[line];
114  ltype = Line->type;
115 
116  if (!(ltype & type))
117  continue;
118 
119  Vect_read_line(Map, NULL, MCats, line);
120 
121  /* special cases:
122  * - loop back to start boundary via several other boundaries
123  * - one boundary forming closed loop
124  * - node with 3 entries but only 2 boundaries, one of them connecting
125  * twice, the other one must then be topologically incorrect (a bridge)
126  * in case of boundary */
127 
128  /* go backward as long as there is only one other line/boundary at the
129  * current node */
130  G_debug(3, "go backward");
131  Vect_get_line_nodes(Map, line, &next_node, NULL);
132 
133  first = -line;
134  while (1) {
135  node_n_lines = Vect_get_node_n_lines(Map, next_node);
136  /* count lines/boundaries at this node */
137  lines_type = 0;
138  next_line = first;
139  for (i = 0; i < node_n_lines; i++) {
140  curr_line = Vect_get_node_line(Map, next_node, i);
141  if ((Plus->Line[abs(curr_line)]->type & GV_LINES))
142  lines_type++;
143  if (Plus->Line[abs(curr_line)]->type == ltype) {
144  if (abs(curr_line) != abs(first)) {
145  Vect_read_line(Map, NULL, Cats, abs(curr_line));
146 
147  /* categories must be identical */
148  if (compare_cats(MCats, Cats) == 0)
149  next_line = curr_line;
150  }
151  }
152  }
153  if (lines_type == 2 && abs(next_line) != abs(first) &&
154  abs(next_line) != line) {
155  first = next_line;
156 
157  if (first < 0) {
158  Vect_get_line_nodes(Map, -first, &next_node, NULL);
159  }
160  else {
161  Vect_get_line_nodes(Map, first, NULL, &next_node);
162  }
163  }
164  else
165  break;
166  }
167 
168  /* go forward as long as there is only one other line/boundary at the
169  * current node */
170  G_debug(3, "go forward");
171 
172  /* reverse direction */
173  last = -first;
174 
175  if (last < 0) {
176  Vect_get_line_nodes(Map, -last, &next_node, NULL);
177  }
178  else {
179  Vect_get_line_nodes(Map, last, NULL, &next_node);
180  }
181 
182  Vect_reset_list(List);
183  while (1) {
184  G_ilist_add(List, last);
185  node_n_lines = Vect_get_node_n_lines(Map, next_node);
186  lines_type = 0;
187  next_line = last;
188  for (i = 0; i < node_n_lines; i++) {
189  curr_line = Vect_get_node_line(Map, next_node, i);
190  if ((Plus->Line[abs(curr_line)]->type & GV_LINES))
191  lines_type++;
192  if (Plus->Line[abs(curr_line)]->type == ltype) {
193  if (abs(curr_line) != abs(last)) {
194  Vect_read_line(Map, NULL, Cats, abs(curr_line));
195 
196  if (compare_cats(MCats, Cats) == 0)
197  next_line = curr_line;
198  }
199  }
200  }
201 
202  if (lines_type == 2 && abs(next_line) != abs(last) &&
203  abs(next_line) != abs(first)) {
204  last = next_line;
205 
206  if (last < 0) {
207  Vect_get_line_nodes(Map, -last, &next_node, NULL);
208  }
209  else {
210  Vect_get_line_nodes(Map, last, NULL, &next_node);
211  }
212  }
213  else
214  break;
215  }
216 
217  /* merge lines */
218  if (List->n_values > 1) {
219  G_debug(3, "merge %d lines", List->n_values);
220  Vect_reset_line(MPoints);
221 
222  for (i = 0; i < List->n_values; i++) {
223  Vect_reset_line(Points);
224  Vect_read_line(Map, Points, Cats, abs(List->value[i]));
225  direction = (List->value[i] < 0 ? GV_BACKWARD : GV_FORWARD);
226  Vect_append_points(MPoints, Points, direction);
227  MPoints->n_points--;
228  if (Err) {
229  /* write out lines/boundaries to be merged */
230  Vect_write_line(Err, ltype, Points, Cats);
231  }
232  Vect_delete_line(Map, abs(List->value[i]));
233  }
234  MPoints->n_points++;
235  Vect_write_line(Map, ltype, MPoints, MCats);
236  merged += List->n_values;
237  newl++;
238  }
239 
240  /* nlines = Vect_get_num_lines(Map); */
241  }
242 
243  if (type == GV_LINE) {
244  G_verbose_message(_("%d lines merged"), merged);
245  G_verbose_message(_("%d new lines"), newl);
246  }
247  else if (type == GV_BOUNDARY) {
248  G_verbose_message(_("%d boundaries merged"), merged);
249  G_verbose_message(_("%d new boundaries"), newl);
250  }
251  else {
252  G_verbose_message(_("%d lines and boundaries merged"), merged);
253  G_verbose_message(_("%d new lines and boundaries"), newl);
254  }
255 
256  if (new_lines)
257  *new_lines = newl;
258 
259  Vect_destroy_line_struct(Points);
261  Vect_destroy_line_struct(MPoints);
263  Vect_destroy_list(List);
264 
265  return merged;
266 }
#define NULL
Definition: ccmath.h:32
void G_percent(long, long, int)
Print percent complete messages.
Definition: percent.c:61
void G_warning(const char *,...) __attribute__((format(printf
void void G_verbose_message(const char *,...) __attribute__((format(printf
void G_ilist_add(struct ilist *, int)
Add item to ilist.
Definition: ilist.c:78
int G_debug(int, const char *,...) __attribute__((format(printf
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_get_line_nodes(struct Map_info *, int, int *, int *)
Get line nodes.
Definition: level_two.c:304
plus_t Vect_get_num_lines(struct Map_info *)
Fetch number of features (points, lines, boundaries, centroids) in vector map.
Definition: level_two.c:75
void Vect_destroy_list(struct ilist *)
Frees all memory associated with a struct ilist, including the struct itself.
void Vect_destroy_cats_struct(struct line_cats *)
Frees all memory associated with line_cats structure, including the struct itself.
int Vect_read_line(struct Map_info *, struct line_pnts *, struct line_cats *, int)
Read vector feature (topological level required)
struct ilist * Vect_new_list(void)
Creates and initializes a struct ilist.
int Vect_line_alive(struct Map_info *, int)
Check if feature is alive or dead (topological level required)
int Vect_delete_line(struct Map_info *, off_t)
Delete existing feature (topological level required)
off_t Vect_write_line(struct Map_info *, int, const struct line_pnts *, const struct line_cats *)
Writes a new feature.
struct line_pnts * Vect_new_line_struct(void)
Creates and initializes a line_pnts structure.
Definition: line.c:45
int Vect_get_node_n_lines(struct Map_info *, int)
Get number of lines for node.
Definition: level_two.c:381
void Vect_reset_line(struct line_pnts *)
Reset line.
Definition: line.c:129
int Vect_get_node_line(struct Map_info *, int, int)
Get line id for node line index.
Definition: level_two.c:397
struct line_cats * Vect_new_cats_struct(void)
Creates and initializes line_cats structure.
int Vect_reset_list(struct ilist *)
Reset ilist structure.
int Vect_append_points(struct line_pnts *, const struct line_pnts *, int)
Appends points to the end of a line.
Definition: line.c:335
#define GV_LINE
Definition: dig_defines.h:184
#define GV_LINES
Definition: dig_defines.h:193
#define GV_BOUNDARY
Definition: dig_defines.h:185
#define GV_FORWARD
Line direction indicator forward/backward.
Definition: dig_defines.h:179
#define GV_BACKWARD
Definition: dig_defines.h:180
#define _(str)
Definition: glocale.h:10
int Vect_merge_lines(struct Map_info *Map, int type, int *new_lines, struct Map_info *Err)
Merge lines or boundaries in vector map.
Definition: merge_lines.c:78
Vector map info.
Definition: dig_structs.h:1243
struct Plus_head plus
Plus info (topology, version, ...)
Definition: dig_structs.h:1270
Vector geometry.
Definition: dig_structs.h:1553
char type
Line type.
Definition: dig_structs.h:1564
Basic topology-related info.
Definition: dig_structs.h:769
struct P_line ** Line
Array of vector geometries.
Definition: dig_structs.h:871
List of integers.
Definition: gis.h:715
int n_values
Number of values in the list.
Definition: gis.h:723
int * value
Array of values.
Definition: gis.h:719
Feature category info.
Definition: dig_structs.h:1677
int * field
Array of layers (fields)
Definition: dig_structs.h:1681
int * cat
Array of categories.
Definition: dig_structs.h:1685
int n_cats
Number of categories attached to element.
Definition: dig_structs.h:1689
Feature geometry info - coordinates.
Definition: dig_structs.h:1651
int n_points
Number of points.
Definition: dig_structs.h:1667