GRASS Programmer's Manual 6.4.1(2011)
bridges.c
Go to the documentation of this file.
00001 
00020 #include <stdlib.h>
00021 #include <grass/gis.h>
00022 #include <grass/Vect.h>
00023 #include <grass/glocale.h>
00024 
00025 static void
00026 remove_bridges(struct Map_info *Map, int chtype, struct Map_info *Err);
00027 
00043 void
00044 Vect_remove_bridges(struct Map_info *Map, struct Map_info *Err)
00045 {
00046     remove_bridges(Map, 0, Err);
00047 }
00048 
00064 void
00065 Vect_chtype_bridges(struct Map_info *Map, struct Map_info *Err)
00066 {
00067     remove_bridges(Map, 1, Err);
00068 }
00069 
00070 /* 
00071    Called by Vect_remove_bridges() and Vect_chtype_bridges():
00072    chtype = 0 -> works like Vect_remove_bridges()
00073    chtype = 1 -> works like Vect_chtype_bridges()
00074 
00075    Algorithm: Go thorough all lines, 
00076    if both sides of the line have left and side 0 (candidate) do this check:
00077    follow adjacent lines in one direction (nearest to the right at the end node),
00078    if we reach this line again without dangle in the way, but with this line 
00079    traversed from other side it is a bridge.
00080 
00081    List of all lines in chain is created during the cycle.
00082  */
00083 void
00084 remove_bridges(struct Map_info *Map, int chtype, struct Map_info *Err)
00085 {
00086     int i, type, nlines, line;
00087     int left, right, node1, node2, current_line, next_line;
00088     int bridges_removed = 0;    /* number of removed bridges */
00089     int lines_removed = 0;      /* number of lines removed */
00090     char *lmsg;
00091     struct Plus_head *Plus;
00092     struct line_pnts *Points;
00093     struct line_cats *Cats;
00094     struct ilist *CycleList;
00095     struct ilist *BridgeList;
00096 
00097     int dangle, other_side;
00098 
00099     if (chtype)
00100         lmsg = "changed lines";
00101     else
00102         lmsg = "removed lines";
00103 
00104     Plus = &(Map->plus);
00105 
00106     Points = Vect_new_line_struct();
00107     Cats = Vect_new_cats_struct();
00108     CycleList = Vect_new_list();
00109     BridgeList = Vect_new_list();
00110 
00111     nlines = Vect_get_num_lines(Map);
00112 
00113     G_debug(1, "nlines =  %d", nlines);
00114 
00115     for (line = 1; line <= nlines; line++) {
00116         G_percent(line, nlines, 1);
00117         if (!Vect_line_alive(Map, line))
00118             continue;
00119 
00120         type = Vect_read_line(Map, NULL, NULL, line);
00121         if (!(type & GV_BOUNDARY))
00122             continue;
00123 
00124         Vect_get_line_areas(Map, line, &left, &right);
00125 
00126         if (left != 0 || right != 0)
00127             continue;           /* Cannot be bridge */
00128 
00129         G_debug(2, "line %d - bridge candidate", line);
00130 
00131         Vect_get_line_nodes(Map, line, &node1, &node2);
00132 
00133         if (abs(node1) == abs(node2))
00134             continue;           /* either zero length or loop -> cannot be a bridge */
00135 
00136         current_line = -line;   /* we start with negative (go forward, node2 ) */
00137 
00138         dangle = 0;
00139         other_side = 0;
00140         Vect_reset_list(CycleList);
00141         Vect_reset_list(BridgeList);
00142         while (1) {
00143             next_line =
00144                 dig_angle_next_line(Plus, current_line, GV_RIGHT,
00145                                     GV_BOUNDARY);
00146 
00147             /* Add this line to the list */
00148             if (Vect_val_in_list(CycleList, abs(next_line)))    /* other side -> bridge chain */
00149                 Vect_list_append(BridgeList, abs(next_line));
00150             else
00151                 Vect_list_append(CycleList, abs(next_line));
00152 
00153             if (abs(next_line) == abs(current_line)) {
00154                 G_debug(4, "  dangle -> no bridge");
00155                 dangle = 1;
00156                 break;
00157             }
00158             if (abs(next_line) == line) {       /* start line reached */
00159                 /* which side */
00160                 if (next_line < 0) {    /* other side (connected by node 2) */
00161                     G_debug(5, "  other side reached");
00162                     other_side = 1;
00163                 }
00164                 else {          /* start side */
00165                     break;
00166                 }
00167             }
00168 
00169             current_line = -next_line;  /* change the sign to look at the next node in following cycle */
00170         }
00171 
00172         if (!dangle && other_side) {
00173             G_debug(3, " line %d is part of bridge chain", line);
00174 
00175             for (i = 0; i < BridgeList->n_values; i++) {
00176                 Vect_read_line(Map, Points, Cats, BridgeList->value[i]);
00177 
00178                 if (Err) {
00179                     Vect_write_line(Err, GV_BOUNDARY, Points, Cats);
00180                 }
00181 
00182                 if (!chtype)
00183                     Vect_delete_line(Map, BridgeList->value[i]);
00184                 else
00185                     Vect_rewrite_line(Map, BridgeList->value[i], GV_LINE,
00186                                       Points, Cats);
00187 
00188                 lines_removed++;
00189             }
00190             bridges_removed++;
00191         }
00192     }
00193 }
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines