GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-535c39c9fc
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 
79 int Vect_merge_lines(struct Map_info *Map, int type, int *new_lines,
80  struct Map_info *Err)
81 {
82  int line, nlines, i, first, last, next_line, curr_line;
83  int merged = 0, newl = 0;
84  int next_node, direction, node_n_lines, ltype, lines_type;
85  struct Plus_head *Plus;
86  struct ilist *List;
87  struct line_pnts *MPoints, *Points;
88  struct line_cats *MCats, *Cats;
89  struct P_line *Line;
90 
91  type &= GV_LINES;
92 
93  if (!(type & GV_LINES)) {
94  G_warning("Merging is done with lines or boundaries only, not with "
95  "other types");
96  return 0;
97  }
98 
99  Plus = &(Map->plus);
100  nlines = Vect_get_num_lines(Map);
101 
102  Points = Vect_new_line_struct();
103  Cats = Vect_new_cats_struct();
104  MPoints = Vect_new_line_struct();
105  MCats = Vect_new_cats_struct();
106  List = Vect_new_list();
107 
108  for (line = 1; line <= nlines; line++) {
109  G_percent(line, nlines, 2);
110 
111  if (!Vect_line_alive(Map, line))
112  continue;
113 
114  Line = Plus->Line[line];
115  ltype = Line->type;
116 
117  if (!(ltype & type))
118  continue;
119 
120  Vect_read_line(Map, NULL, MCats, line);
121 
122  /* special cases:
123  * - loop back to start boundary via several other boundaries
124  * - one boundary forming closed loop
125  * - node with 3 entries but only 2 boundaries, one of them connecting
126  * twice, the other one must then be topologically incorrect (a bridge)
127  * in case of boundary */
128 
129  /* go backward as long as there is only one other line/boundary at the
130  * current node */
131  G_debug(3, "go backward");
132  Vect_get_line_nodes(Map, line, &next_node, NULL);
133 
134  first = -line;
135  while (1) {
136  node_n_lines = Vect_get_node_n_lines(Map, next_node);
137  /* count lines/boundaries at this node */
138  lines_type = 0;
139  next_line = first;
140  for (i = 0; i < node_n_lines; i++) {
141  curr_line = Vect_get_node_line(Map, next_node, i);
142  if ((Plus->Line[abs(curr_line)]->type & GV_LINES))
143  lines_type++;
144  if (Plus->Line[abs(curr_line)]->type == ltype) {
145  if (abs(curr_line) != abs(first)) {
146  Vect_read_line(Map, NULL, Cats, abs(curr_line));
147 
148  /* categories must be identical */
149  if (compare_cats(MCats, Cats) == 0)
150  next_line = curr_line;
151  }
152  }
153  }
154  if (lines_type == 2 && abs(next_line) != abs(first) &&
155  abs(next_line) != line) {
156  first = next_line;
157 
158  if (first < 0) {
159  Vect_get_line_nodes(Map, -first, &next_node, NULL);
160  }
161  else {
162  Vect_get_line_nodes(Map, first, NULL, &next_node);
163  }
164  }
165  else
166  break;
167  }
168 
169  /* go forward as long as there is only one other line/boundary at the
170  * current node */
171  G_debug(3, "go forward");
172 
173  /* reverse direction */
174  last = -first;
175 
176  if (last < 0) {
177  Vect_get_line_nodes(Map, -last, &next_node, NULL);
178  }
179  else {
180  Vect_get_line_nodes(Map, last, NULL, &next_node);
181  }
182 
183  Vect_reset_list(List);
184  while (1) {
185  G_ilist_add(List, last);
186  node_n_lines = Vect_get_node_n_lines(Map, next_node);
187  lines_type = 0;
188  next_line = last;
189  for (i = 0; i < node_n_lines; i++) {
190  curr_line = Vect_get_node_line(Map, next_node, i);
191  if ((Plus->Line[abs(curr_line)]->type & GV_LINES))
192  lines_type++;
193  if (Plus->Line[abs(curr_line)]->type == ltype) {
194  if (abs(curr_line) != abs(last)) {
195  Vect_read_line(Map, NULL, Cats, abs(curr_line));
196 
197  if (compare_cats(MCats, Cats) == 0)
198  next_line = curr_line;
199  }
200  }
201  }
202 
203  if (lines_type == 2 && abs(next_line) != abs(last) &&
204  abs(next_line) != abs(first)) {
205  last = next_line;
206 
207  if (last < 0) {
208  Vect_get_line_nodes(Map, -last, &next_node, NULL);
209  }
210  else {
211  Vect_get_line_nodes(Map, last, NULL, &next_node);
212  }
213  }
214  else
215  break;
216  }
217 
218  /* merge lines */
219  if (List->n_values > 1) {
220  G_debug(3, "merge %d lines", List->n_values);
221  Vect_reset_line(MPoints);
222 
223  for (i = 0; i < List->n_values; i++) {
224  Vect_reset_line(Points);
225  Vect_read_line(Map, Points, Cats, abs(List->value[i]));
226  direction = (List->value[i] < 0 ? GV_BACKWARD : GV_FORWARD);
227  Vect_append_points(MPoints, Points, direction);
228  MPoints->n_points--;
229  if (Err) {
230  /* write out lines/boundaries to be merged */
231  Vect_write_line(Err, ltype, Points, Cats);
232  }
233  Vect_delete_line(Map, abs(List->value[i]));
234  }
235  MPoints->n_points++;
236  Vect_write_line(Map, ltype, MPoints, MCats);
237  merged += List->n_values;
238  newl++;
239  }
240 
241  /* nlines = Vect_get_num_lines(Map); */
242  }
243 
244  if (type == GV_LINE) {
245  G_verbose_message(_("%d lines merged"), merged);
246  G_verbose_message(_("%d new lines"), newl);
247  }
248  else if (type == GV_BOUNDARY) {
249  G_verbose_message(_("%d boundaries merged"), merged);
250  G_verbose_message(_("%d new boundaries"), newl);
251  }
252  else {
253  G_verbose_message(_("%d lines and boundaries merged"), merged);
254  G_verbose_message(_("%d new lines and boundaries"), newl);
255  }
256 
257  if (new_lines)
258  *new_lines = newl;
259 
260  Vect_destroy_line_struct(Points);
262  Vect_destroy_line_struct(MPoints);
264  Vect_destroy_list(List);
265 
266  return merged;
267 }
#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:303
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:380
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:396
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:79
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:706
int n_values
Number of values in the list.
Definition: gis.h:714
int * value
Array of values.
Definition: gis.h:710
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