GRASS GIS 8 Programmer's Manual  8.2.2dev(2023)-3d2c704037
bridges.c
Go to the documentation of this file.
1 /*!
2  \file lib/vector/Vlib/bridges.c
3 
4  \brief Vector library - clean geometry (bridges)
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 Radim Blazek
16  */
17 
18 #include <stdlib.h>
19 #include <grass/vector.h>
20 #include <grass/rbtree.h>
21 #include <grass/glocale.h>
22 
23 static int cmp_int(const void *a, const void *b)
24 {
25  const int *ai = a;
26  const int *bi = b;
27 
28  return (*ai < *bi ? -1 : (*ai > *bi));
29 }
30 
31 static void remove_bridges(struct Map_info *Map, int chtype, struct Map_info *Err,
32  int *lrm, int *brm);
33 
34 /*!
35  \brief Remove bridges from vector map.
36 
37  Remove bridges (type boundary) connecting areas to islands or 2
38  islands. Islands and areas must be already clean, i.e. without
39  dangles. Bridge may be formed by more lines. Optionally deleted
40  bridges are written to error map. Input map must be opened on
41  level 2 for update at least on level GV_BUILD_BASE
42 
43  \param Map input map where bridges are deleted
44  \param Err vector map where deleted bridges are written or NULL
45  \param lines_removed number of lines removed
46  \param bridges_removed Err number of bridges removed
47 */
48 void Vect_remove_bridges(struct Map_info *Map, struct Map_info *Err,
49  int *lines_removed, int *bridges_removed)
50 {
51  remove_bridges(Map, 0, Err, lines_removed, bridges_removed);
52 }
53 
54 /*!
55  \brief Change type of bridges in vector map.
56 
57  Change the type of bridges (type boundary) connecting areas to
58  islands or 2 islands. Islands and areas must be already clean,
59  i.e. without dangles. Bridge may be formed by more lines.
60  Optionally changed bridges are written to error map. Input map
61  must be opened on level 2 for update at least on level
62  GV_BUILD_BASE.
63 
64  \param Map input map where bridges are changed
65  \param Err vector map where changed bridges are written or NULL
66  \param lines_changed number of lines changed
67  \param bridges_changed Err number of bridges changed
68 */
69 void Vect_chtype_bridges(struct Map_info *Map, struct Map_info *Err,
70  int *lines_changed, int *bridges_changed)
71 {
72  remove_bridges(Map, 1, Err, lines_changed, bridges_changed);
73 }
74 
75 /*
76  Called by Vect_remove_bridges() and Vect_chtype_bridges():
77  chtype = 0 -> works like Vect_remove_bridges()
78  chtype = 1 -> works like Vect_chtype_bridges()
79 
80  Algorithm: Go thorough all lines,
81  if both sides of the line have left and side 0 (candidate) do this check:
82  follow adjacent lines in one direction (nearest to the right at the end node),
83  if we reach this line again without dangle in the way, but with this line
84  traversed from other side it is a bridge.
85 
86  List of all lines in chain is created during the cycle.
87  */
88 void remove_bridges(struct Map_info *Map, int chtype, struct Map_info *Err,
89  int *lrm, int *brm)
90 {
91  int type, nlines, line, *bline;
92  int left, right, node1, node2, current_line, next_line, abs_line;
93  int bridges_removed = 0; /* number of removed bridges */
94  int lines_removed = 0; /* number of lines removed */
95  struct Plus_head *Plus;
96  struct line_pnts *Points;
97  struct line_cats *Cats;
98  struct RB_TREE *CycleTree, *BridgeTree;
99  struct RB_TRAV trav;
100 
101  int dangle, other_side;
102 
103  Plus = &(Map->plus);
104 
105  Points = Vect_new_line_struct();
106  Cats = Vect_new_cats_struct();
107 
108  CycleTree = rbtree_create(cmp_int, sizeof(int));
109  BridgeTree = rbtree_create(cmp_int, sizeof(int));
110 
111  nlines = Vect_get_num_lines(Map);
112 
113  G_debug(1, "nlines = %d", nlines);
114 
115  for (line = 1; line <= nlines; line++) {
116  G_percent(line, nlines, 1);
117  if (!Vect_line_alive(Map, line))
118  continue;
119 
120  type = Vect_read_line(Map, NULL, NULL, line);
121  if (!(type & GV_BOUNDARY))
122  continue;
123 
124  Vect_get_line_areas(Map, line, &left, &right);
125 
126  if (left != 0 || right != 0)
127  continue; /* Cannot be bridge */
128 
129  G_debug(2, "line %d - bridge candidate", line);
130 
131  Vect_get_line_nodes(Map, line, &node1, &node2);
132 
133  if (abs(node1) == abs(node2))
134  continue; /* either zero length or loop -> cannot be a bridge */
135 
136  current_line = -line; /* we start with negative (go forward, node2 ) */
137 
138  G_debug(3, "current line: %d", line);
139  dangle = 0;
140  other_side = 0;
141  rbtree_clear(CycleTree);
142  rbtree_clear(BridgeTree);
143 
144  while (1) {
145  next_line =
146  dig_angle_next_line(Plus, current_line, GV_RIGHT,
147  GV_BOUNDARY, NULL);
148  abs_line = abs(next_line);
149 
150  /* Add this line to the list */
151  if (rbtree_find(CycleTree, (void *)&abs_line)) {
152  if (!rbtree_find(BridgeTree, (void *)&abs_line)) {
153  rbtree_insert(BridgeTree, (void *)&abs_line);
154  }
155  }
156  else {
157  rbtree_insert(CycleTree, (void *)&abs_line);
158  }
159 
160  if (abs(next_line) == abs(current_line)) {
161  G_debug(4, " dangle -> no bridge");
162  dangle = 1;
163  break;
164  }
165  if (abs(next_line) == line) { /* start line reached */
166  /* which side */
167  if (next_line < 0) { /* other side (connected by node 2) */
168  G_debug(5, " other side reached");
169  other_side = 1;
170  }
171  else { /* start side */
172  break;
173  }
174  }
175 
176  current_line = -next_line; /* change the sign to look at the next node in following cycle */
177  }
178 
179  if (!dangle && other_side) {
180  G_debug(3, " line %d is part of bridge chain", line);
181 
182  rbtree_init_trav(&trav, BridgeTree);
183  /* for (i = 0; i < BridgeList->n_values; i++) { */
184  while ((bline = rbtree_traverse(&trav))) {
185  Vect_read_line(Map, Points, Cats, *bline);
186 
187  if (Err) {
188  Vect_write_line(Err, GV_BOUNDARY, Points, Cats);
189  }
190 
191  if (!chtype)
192  Vect_delete_line(Map, *bline);
193  else
194  Vect_rewrite_line(Map, *bline, GV_LINE,
195  Points, Cats);
196 
197  lines_removed++;
198  }
199  bridges_removed++;
200  }
201  }
202 
203  Vect_destroy_line_struct(Points);
205  rbtree_destroy(CycleTree);
206  rbtree_destroy(BridgeTree);
207 
208  if (lrm)
209  *lrm = lines_removed;
210  if (brm)
211  *brm = bridges_removed;
212 
213  G_verbose_message(_("Removed lines: %d"), lines_removed);
214  G_verbose_message(_("Removed bridges: %d"), bridges_removed);
215 }
void rbtree_clear(struct RB_TREE *)
Definition: rbtree.c:490
void Vect_chtype_bridges(struct Map_info *Map, struct Map_info *Err, int *lines_changed, int *bridges_changed)
Change type of bridges in vector map.
Definition: bridges.c:69
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)
void * rbtree_find(struct RB_TREE *, const void *)
Definition: rbtree.c:243
int rbtree_init_trav(struct RB_TRAV *, struct RB_TREE *)
Definition: rbtree.c:264
struct RB_TREE * rbtree_create(rb_compare_fn *, size_t)
Definition: rbtree.c:50
Definition: rbtree.h:93
#define NULL
Definition: ccmath.h:32
Definition: rbtree.h:85
Feature category info.
Definition: dig_structs.h:1702
#define GV_LINE
Definition: dig_defines.h:183
int dig_angle_next_line(struct Plus_head *, plus_t, int, int, float *)
Find line number of next angle to follow a line.
Definition: plus_area.c:466
Feature geometry info - coordinates.
Definition: dig_structs.h:1675
Basic topology-related info.
Definition: dig_structs.h:784
double b
Definition: r_raster.c:39
int rbtree_insert(struct RB_TREE *, void *)
Definition: rbtree.c:74
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.
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
void Vect_remove_bridges(struct Map_info *Map, struct Map_info *Err, int *lines_removed, int *bridges_removed)
Remove bridges from vector map.
Definition: bridges.c:48
struct Plus_head plus
Plus info (topology, version, ...)
Definition: dig_structs.h:1286
void * rbtree_traverse(struct RB_TRAV *)
Definition: rbtree.c:281
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
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)
#define GV_RIGHT
Definition: dig_defines.h:175
#define _(str)
Definition: glocale.h:10
void rbtree_destroy(struct RB_TREE *)
Definition: rbtree.c:520
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
int Vect_get_line_areas(const struct Map_info *, int, int *, int *)
Get area id on the left and right side of the boundary.
Definition: level_two.c:350