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         if (!Vect_line_alive(Map, line))
00117             continue;
00118 
00119         type = Vect_read_line(Map, NULL, NULL, line);
00120         if (!(type & GV_BOUNDARY))
00121             continue;
00122 
00123         Vect_get_line_areas(Map, line, &left, &right);
00124 
00125         if (left != 0 || right != 0)
00126             continue;           /* Cannot be bridge */
00127 
00128         G_debug(2, "line %d - bridge candidate", line);
00129 
00130         Vect_get_line_nodes(Map, line, &node1, &node2);
00131 
00132         if (abs(node1) == abs(node2))
00133             continue;           /* either zero length or loop -> cannot be a bridge */
00134 
00135         current_line = -line;   /* we start with negative (go forward, node2 ) */
00136 
00137         dangle = 0;
00138         other_side = 0;
00139         Vect_reset_list(CycleList);
00140         Vect_reset_list(BridgeList);
00141         while (1) {
00142             next_line =
00143                 dig_angle_next_line(Plus, current_line, GV_RIGHT,
00144                                     GV_BOUNDARY);
00145 
00146             /* Add this line to the list */
00147             if (Vect_val_in_list(CycleList, abs(next_line)))    /* other side -> bridge chain */
00148                 Vect_list_append(BridgeList, abs(next_line));
00149             else
00150                 Vect_list_append(CycleList, abs(next_line));
00151 
00152             if (abs(next_line) == abs(current_line)) {
00153                 G_debug(4, "  dangle -> no bridge");
00154                 dangle = 1;
00155                 break;
00156             }
00157             if (abs(next_line) == line) {       /* start line reached */
00158                 /* which side */
00159                 if (next_line < 0) {    /* other side (connected by node 2) */
00160                     G_debug(5, "  other side reached");
00161                     other_side = 1;
00162                 }
00163                 else {          /* start side */
00164                     break;
00165                 }
00166             }
00167 
00168             current_line = -next_line;  /* change the sign to look at the next node in following cycle */
00169         }
00170 
00171         if (!dangle && other_side) {
00172             G_debug(3, " line %d is part of bridge chain", line);
00173 
00174             for (i = 0; i < BridgeList->n_values; i++) {
00175                 Vect_read_line(Map, Points, Cats, BridgeList->value[i]);
00176 
00177                 if (Err) {
00178                     Vect_write_line(Err, GV_BOUNDARY, Points, Cats);
00179                 }
00180 
00181                 if (!chtype)
00182                     Vect_delete_line(Map, BridgeList->value[i]);
00183                 else
00184                     Vect_rewrite_line(Map, BridgeList->value[i], GV_LINE,
00185                                       Points, Cats);
00186 
00187                 lines_removed++;
00188             }
00189             bridges_removed++;
00190         }
00191     }
00192 }