GRASS Programmer's Manual 6.4.1(2011)
|
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 }