GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
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 NULL
73  \param new_lines pointer to where number of new lines/boundaries is stored or NULL
74 
75  \return number of merged lines/boundaries
76  */
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
94  ("Merging is done with lines or boundaries only, not with 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 twice,
125  * the other one must then be topologically incorrect (a bridge) in case of boundary */
126 
127  /* go backward as long as there is only one other line/boundary at the current node */
128  G_debug(3, "go backward");
129  Vect_get_line_nodes(Map, line, &next_node, NULL);
130 
131  first = -line;
132  while (1) {
133  node_n_lines = Vect_get_node_n_lines(Map, next_node);
134  /* count lines/boundaries at this node */
135  lines_type = 0;
136  next_line = first;
137  for (i = 0; i < node_n_lines; i++) {
138  curr_line = Vect_get_node_line(Map, next_node, i);
139  if ((Plus->Line[abs(curr_line)]->type & GV_LINES))
140  lines_type++;
141  if (Plus->Line[abs(curr_line)]->type == ltype) {
142  if (abs(curr_line) != abs(first)) {
143  Vect_read_line(Map, NULL, Cats, abs(curr_line));
144 
145  /* catgories must be identical */
146  if (compare_cats(MCats, Cats) == 0)
147  next_line = curr_line;
148  }
149  }
150  }
151  if (lines_type == 2 && abs(next_line) != abs(first) &&
152  abs(next_line) != line) {
153  first = next_line;
154 
155  if (first < 0) {
156  Vect_get_line_nodes(Map, -first, &next_node, NULL);
157  }
158  else {
159  Vect_get_line_nodes(Map, first, NULL, &next_node);
160  }
161  }
162  else
163  break;
164  }
165 
166  /* go forward as long as there is only one other line/boundary at the current node */
167  G_debug(3, "go forward");
168 
169  /* reverse direction */
170  last = -first;
171 
172  if (last < 0) {
173  Vect_get_line_nodes(Map, -last, &next_node, NULL);
174  }
175  else {
176  Vect_get_line_nodes(Map, last, NULL, &next_node);
177  }
178 
179  Vect_reset_list(List);
180  while (1) {
181  G_ilist_add(List, last);
182  node_n_lines = Vect_get_node_n_lines(Map, next_node);
183  lines_type = 0;
184  next_line = last;
185  for (i = 0; i < node_n_lines; i++) {
186  curr_line = Vect_get_node_line(Map, next_node, i);
187  if ((Plus->Line[abs(curr_line)]->type & GV_LINES))
188  lines_type++;
189  if (Plus->Line[abs(curr_line)]->type == ltype) {
190  if (abs(curr_line) != abs(last)) {
191  Vect_read_line(Map, NULL, Cats, abs(curr_line));
192 
193  if (compare_cats(MCats, Cats) == 0)
194  next_line = curr_line;
195  }
196  }
197  }
198 
199  if (lines_type == 2 && abs(next_line) != abs(last) &&
200  abs(next_line) != abs(first)) {
201  last = next_line;
202 
203  if (last < 0) {
204  Vect_get_line_nodes(Map, -last, &next_node, NULL);
205  }
206  else {
207  Vect_get_line_nodes(Map, last, NULL, &next_node);
208  }
209  }
210  else
211  break;
212  }
213 
214  /* merge lines */
215  if (List->n_values > 1) {
216  G_debug(3, "merge %d lines", List->n_values);
217  Vect_reset_line(MPoints);
218 
219  for (i = 0; i < List->n_values; i++) {
220  Vect_reset_line(Points);
221  Vect_read_line(Map, Points, Cats, abs(List->value[i]));
222  direction = (List->value[i] < 0 ? GV_BACKWARD : GV_FORWARD);
223  Vect_append_points(MPoints, Points, direction);
224  MPoints->n_points--;
225  if (Err) {
226  /* write out lines/boundaries to be merged */
227  Vect_write_line(Err, ltype, Points, Cats);
228  }
229  Vect_delete_line(Map, abs(List->value[i]));
230  }
231  MPoints->n_points++;
232  Vect_write_line(Map, ltype, MPoints, MCats);
233  merged += List->n_values;
234  newl++;
235  }
236 
237  /* nlines = Vect_get_num_lines(Map); */
238  }
239 
240  if (type == GV_LINE) {
241  G_verbose_message(_("%d lines merged"), merged);
242  G_verbose_message(_("%d new lines"), newl);
243  }
244  else if (type == GV_BOUNDARY) {
245  G_verbose_message(_("%d boundaries merged"), merged);
246  G_verbose_message(_("%d new boundaries"), newl);
247  }
248  else {
249  G_verbose_message(_("%d lines and boundaries merged"), merged);
250  G_verbose_message(_("%d new lines and boundaries"), newl);
251  }
252 
253  if (new_lines)
254  *new_lines = newl;
255 
256  Vect_destroy_line_struct(Points);
258  Vect_destroy_line_struct(MPoints);
260  Vect_destroy_list(List);
261 
262  return merged;
263 }
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.
Vector geometry.
Definition: dig_structs.h:1574
struct P_line ** Line
Array of vector geometries.
Definition: dig_structs.h:887
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
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
#define GV_BACKWARD
Definition: dig_defines.h:179
int n_points
Number of points.
Definition: dig_structs.h:1692
int n_values
Number of values in the list.
Definition: gis.h:709
#define NULL
Definition: ccmath.h:32
int Vect_get_node_n_lines(const struct Map_info *, int)
Get number of lines for node.
Definition: level_two.c:384
Feature category info.
Definition: dig_structs.h:1702
#define GV_LINE
Definition: dig_defines.h:183
char type
Line type.
Definition: dig_structs.h:1586
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 Vect_get_node_line(const struct Map_info *, int, int)
Get line id for node line index.
Definition: level_two.c:401
Basic topology-related info.
Definition: dig_structs.h:784
void Vect_destroy_list(struct ilist *)
Frees all memory associated with a struct ilist, including the struct itself.
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
off_t Vect_write_line(struct Map_info *, int, const struct line_pnts *, const struct line_cats *)
Writes a new feature.
#define GV_BOUNDARY
Definition: dig_defines.h:184
struct Plus_head plus
Plus info (topology, version, ...)
Definition: dig_structs.h:1286
int Vect_get_line_nodes(const struct Map_info *, int, int *, int *)
Get line nodes.
Definition: level_two.c:307
void G_percent(long, long, int)
Print percent complete messages.
Definition: percent.c:62
Vector map info.
Definition: dig_structs.h:1259
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.
void G_warning(const char *,...) __attribute__((format(printf
int Vect_line_alive(const struct Map_info *, int)
Check if feature is alive or dead (topological level required)
#define _(str)
Definition: glocale.h:10
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
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
void void G_verbose_message(const char *,...) __attribute__((format(printf
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
void Vect_reset_line(struct line_pnts *)
Reset line.
Definition: line.c:130