GRASS GIS 7 Programmer's Manual  7.5.svn(2018)-r72846
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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  G_verbose_message(_("%d boundaries merged"), merged);
241  G_verbose_message(_("%d new boundaries"), newl);
242 
243  if (new_lines)
244  *new_lines = newl;
245 
246  Vect_destroy_line_struct(Points);
248  Vect_destroy_line_struct(MPoints);
250  Vect_destroy_list(List);
251 
252  return merged;
253 }
#define GV_FORWARD
Line direction indicator forward/backward.
Definition: dig_defines.h:178
void Vect_destroy_list(struct ilist *list)
Frees all memory associated with a struct ilist, including the struct itself.
void G_verbose_message(const char *msg,...)
Print a message to stderr but only if module is in verbose mode.
Definition: gis/error.c:109
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
int Vect_get_node_n_lines(const struct Map_info *Map, int node)
Get number of lines for node.
Definition: level_two.c:384
#define GV_BACKWARD
Definition: dig_defines.h:179
struct line_pnts * Vect_new_line_struct()
Creates and initializes a line_pnts structure.
Definition: line.c:45
off_t Vect_write_line(struct Map_info *Map, int type, const struct line_pnts *points, const struct line_cats *cats)
Writes a new feature.
struct ilist * Vect_new_list(void)
Creates and initializes a struct ilist.
int n_points
Number of points.
Definition: dig_structs.h:1692
int Vect_line_alive(const struct Map_info *Map, int line)
Check if feature is alive or dead (topological level required)
int n_values
Number of values in the list.
Definition: gis.h:676
void Vect_destroy_line_struct(struct line_pnts *p)
Frees all memory associated with a line_pnts structure, including the structure itself.
Definition: line.c:77
void Vect_destroy_cats_struct(struct line_cats *p)
Frees all memory associated with line_cats structure, including the struct itself.
#define NULL
Definition: ccmath.h:32
int Vect_delete_line(struct Map_info *Map, off_t line)
Delete existing feature (topological level required)
Feature category info.
Definition: dig_structs.h:1702
int Vect_append_points(struct line_pnts *Points, const struct line_pnts *APoints, int direction)
Appends points to the end of a line.
Definition: line.c:337
char type
Line type.
Definition: dig_structs.h:1586
Feature geometry info - coordinates.
Definition: dig_structs.h:1675
Basic topology-related info.
Definition: dig_structs.h:784
int Vect_get_node_line(const struct Map_info *Map, int node, int line)
Get line id for node line index.
Definition: level_two.c:401
int n_cats
Number of categories attached to element.
Definition: dig_structs.h:1715
int G_debug(int level, const char *msg,...)
Print debugging message.
Definition: debug.c:65
int * cat
Array of categories.
Definition: dig_structs.h:1711
int Vect_reset_list(struct ilist *list)
Reset ilist structure.
struct Plus_head plus
Plus info (topology, version, ...)
Definition: dig_structs.h:1286
void G_percent(long n, long d, int s)
Print percent complete messages.
Definition: percent.c:62
Vector map info.
Definition: dig_structs.h:1259
int Vect_get_line_nodes(const struct Map_info *Map, int line, int *n1, int *n2)
Get line nodes.
Definition: level_two.c:307
struct line_cats * Vect_new_cats_struct()
Creates and initializes line_cats structure.
plus_t Vect_get_num_lines(const struct Map_info *Map)
Fetch number of features (points, lines, boundaries, centroids) in vector map.
Definition: level_two.c:74
#define _(str)
Definition: glocale.h:13
List of integers.
Definition: gis.h:667
int Vect_read_line(const struct Map_info *Map, struct line_pnts *line_p, struct line_cats *line_c, int line)
Read vector feature (topological level required)
void Vect_reset_line(struct line_pnts *Points)
Reset line.
Definition: line.c:130
int * field
Array of layers (fields)
Definition: dig_structs.h:1707
int * value
Array of values.
Definition: gis.h:672
#define GV_LINES
Definition: dig_defines.h:192
void G_ilist_add(struct ilist *list, int val)
Add item to ilist.
Definition: ilist.c:77
void G_warning(const char *msg,...)
Print a warning message to stderr.
Definition: gis/error.c:204