GRASS GIS 8 Programmer's Manual  8.4.0dev(2024)-eff64031f2
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,
32  struct Map_info *Err, 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
83  node), if we reach this line again without dangle in the way, but with this
84  line 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 = dig_angle_next_line(Plus, current_line, GV_RIGHT,
146  GV_BOUNDARY, NULL);
147  abs_line = abs(next_line);
148 
149  /* Add this line to the list */
150  if (rbtree_find(CycleTree, (void *)&abs_line)) {
151  if (!rbtree_find(BridgeTree, (void *)&abs_line)) {
152  rbtree_insert(BridgeTree, (void *)&abs_line);
153  }
154  }
155  else {
156  rbtree_insert(CycleTree, (void *)&abs_line);
157  }
158 
159  if (abs(next_line) == abs(current_line)) {
160  G_debug(4, " dangle -> no bridge");
161  dangle = 1;
162  break;
163  }
164  if (abs(next_line) == line) { /* start line reached */
165  /* which side */
166  if (next_line < 0) { /* other side (connected by node 2) */
167  G_debug(5, " other side reached");
168  other_side = 1;
169  }
170  else { /* start side */
171  break;
172  }
173  }
174 
175  current_line = -next_line; /* change the sign to look at the next
176  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, Points, Cats);
195 
196  lines_removed++;
197  }
198  bridges_removed++;
199  }
200  }
201 
202  Vect_destroy_line_struct(Points);
204  rbtree_destroy(CycleTree);
205  rbtree_destroy(BridgeTree);
206 
207  if (lrm)
208  *lrm = lines_removed;
209  if (brm)
210  *brm = bridges_removed;
211 
212  G_verbose_message(_("Removed lines: %d"), lines_removed);
213  G_verbose_message(_("Removed bridges: %d"), bridges_removed);
214 }
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
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
#define NULL
Definition: ccmath.h:32
void G_percent(long, long, int)
Print percent complete messages.
Definition: percent.c:61
void void G_verbose_message(const char *,...) __attribute__((format(printf
int G_debug(int, const char *,...) __attribute__((format(printf
int rbtree_insert(struct RB_TREE *, void *)
Definition: rbtree.c:73
int rbtree_init_trav(struct RB_TRAV *, struct RB_TREE *)
Definition: rbtree.c:264
void rbtree_clear(struct RB_TREE *)
Definition: rbtree.c:490
void * rbtree_find(struct RB_TREE *, const void *)
Definition: rbtree.c:243
void * rbtree_traverse(struct RB_TRAV *)
Definition: rbtree.c:281
void rbtree_destroy(struct RB_TREE *)
Definition: rbtree.c:520
struct RB_TREE * rbtree_create(rb_compare_fn *, size_t)
Definition: rbtree.c:49
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
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)
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_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)
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
struct line_cats * Vect_new_cats_struct(void)
Creates and initializes line_cats structure.
int Vect_get_line_areas(struct Map_info *, int, int *, int *)
Get area id on the left and right side of the boundary.
Definition: level_two.c:346
#define GV_LINE
Definition: dig_defines.h:184
#define GV_BOUNDARY
Definition: dig_defines.h:185
#define GV_RIGHT
Definition: dig_defines.h:176
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:474
#define _(str)
Definition: glocale.h:10
double b
Definition: r_raster.c:39
Vector map info.
Definition: dig_structs.h:1243
struct Plus_head plus
Plus info (topology, version, ...)
Definition: dig_structs.h:1270
Basic topology-related info.
Definition: dig_structs.h:769
Definition: rbtree.h:92
Definition: rbtree.h:85
Feature category info.
Definition: dig_structs.h:1677
Feature geometry info - coordinates.
Definition: dig_structs.h:1651