bridges.c

Go to the documentation of this file.
00001 /***************************************************************
00002  *
00003  * MODULE:       vector library
00004  * 
00005  * AUTHOR(S):    Radim Blazek
00006  *               
00007  * PURPOSE:      Clean lines
00008  *               
00009  * COPYRIGHT:    (C) 2001 by the GRASS Development Team
00010  *
00011  *               This program is free software under the 
00012  *               GNU General Public License (>=v2). 
00013  *               Read the file COPYING that comes with GRASS
00014  *               for details.
00015  *
00016  **************************************************************/
00017 #include <stdlib.h> 
00018 #include <grass/gis.h>
00019 #include <grass/Vect.h>
00020 
00021 void
00022 remove_bridges ( struct Map_info *Map, int chtype, struct Map_info *Err, FILE *msgout );
00023     
00039 void
00040 Vect_remove_bridges ( struct Map_info *Map, struct Map_info *Err, FILE *msgout )
00041 {
00042     remove_bridges ( Map, 0, Err, msgout );
00043 }
00044 
00060 void
00061 Vect_chtype_bridges ( struct Map_info *Map, struct Map_info *Err, FILE *msgout )
00062 {
00063     remove_bridges ( Map, 1, Err, msgout );
00064 }
00065 
00066 /* 
00067    Called by Vect_remove_bridges() and Vect_chtype_bridges():
00068    chtype = 0 -> works like Vect_remove_bridges()
00069    chtype = 1 -> works like Vect_chtype_bridges()
00070 
00071    Algorithm: Go thorough all lines, 
00072               if both sides of the line have left and side 0 (candidate) do this check:
00073               follow adjacent lines in one direction (nearest to the right at the end node),
00074               if we reach this line again without dangle in the way, but with this line 
00075               traversed from other side it is a bridge.
00076               
00077               List of all lines in chain is created during the cycle.
00078 
00079 */
00080 void
00081 remove_bridges ( struct Map_info *Map, int chtype, struct Map_info *Err, FILE *msgout )
00082 {
00083     int  i, type, nlines, line;
00084     int  left, right, node1, node2, current_line, next_line;
00085     int  bridges_removed = 0; /* number of removed bridges */
00086     int  lines_removed = 0; /* number of lines removed */
00087     char *lmsg;
00088     struct Plus_head *Plus;
00089     struct line_pnts *Points;
00090     struct line_cats *Cats;
00091     struct ilist *CycleList;
00092     struct ilist *BridgeList;
00093 
00094     int dangle, other_side; 
00095 
00096     if ( chtype )
00097         lmsg = "changed lines";
00098     else
00099         lmsg = "removed lines";
00100 
00101     Plus = &(Map->plus);
00102     
00103     Points = Vect_new_line_struct ();
00104     Cats = Vect_new_cats_struct ();
00105     CycleList = Vect_new_list ();
00106     BridgeList = Vect_new_list ();
00107 
00108     nlines = Vect_get_num_lines (Map);
00109 
00110     G_debug (1, "nlines =  %d", nlines );
00111 
00112     if ( msgout ) fprintf (msgout, "Removed bridges: %5d  %s: %5d",
00113                                     bridges_removed, lmsg, lines_removed );
00114     
00115     for ( line = 1; line <= nlines; line++ ){ 
00116         if ( !Vect_line_alive ( Map, line ) ) continue;
00117 
00118         type = Vect_read_line (Map, NULL, NULL, line);
00119         if ( !(type & GV_BOUNDARY ) ) continue;
00120         
00121         Vect_get_line_areas ( Map, line, &left, &right );
00122 
00123         if ( left != 0 || right != 0 ) continue; /* Cannot be bridge */
00124 
00125         G_debug (2, "line %d - bridge candidate", line );
00126         
00127         Vect_get_line_nodes ( Map, line, &node1, &node2 );
00128 
00129         if ( abs(node1) == abs(node2) ) continue; /* either zero length or loop -> cannot be a bridge */
00130 
00131         current_line = -line; /* we start with negative (go forward, node2 ) */
00132 
00133         dangle = 0;
00134         other_side = 0;
00135         Vect_reset_list ( CycleList );
00136         Vect_reset_list ( BridgeList );
00137         while ( 1 ) {
00138             next_line = dig_angle_next_line ( Plus, current_line, GV_RIGHT, GV_BOUNDARY );
00139 
00140             /* Add this line to the list */
00141             if ( Vect_val_in_list ( CycleList, abs(next_line) ) ) /* other side -> bridge chain */
00142                 Vect_list_append ( BridgeList, abs(next_line) );
00143             else        
00144                 Vect_list_append ( CycleList, abs(next_line) );
00145             
00146             if ( abs(next_line) == abs(current_line) ) {
00147                 G_debug (4, "  dangle -> no bridge" );
00148                 dangle = 1;
00149                 break;
00150             }
00151             if ( abs(next_line) == line ) { /* start line reached */
00152                 /* which side */
00153                 if ( next_line < 0 ) { /* other side (connected by node 2) */
00154                     G_debug (5, "  other side reached" );
00155                     other_side = 1;
00156                 } else { /* start side */
00157                     break;
00158                 }
00159             }
00160             
00161             current_line = -next_line; /* change the sign to look at the next node in following cycle */
00162         }
00163 
00164         if ( !dangle && other_side ) {
00165             G_debug (3, " line %d is part of bridge chain", line );
00166 
00167             for ( i = 0; i < BridgeList->n_values; i++) {
00168                 Vect_read_line (Map, Points, Cats, BridgeList->value[i]);
00169                 
00170                 if ( Err ) {
00171                     Vect_write_line ( Err, GV_BOUNDARY, Points, Cats );
00172                 }
00173                 
00174                 if ( !chtype )
00175                     Vect_delete_line (Map, BridgeList->value[i]);
00176                 else 
00177                     Vect_rewrite_line ( Map, BridgeList->value[i], GV_LINE, Points, Cats);
00178 
00179                 lines_removed++;
00180             }
00181             bridges_removed++;
00182         }
00183 
00184         if ( msgout ) {
00185             fprintf (msgout, "\rRemoved bridges: %5d  %s: %5d",
00186                                         bridges_removed, lmsg, lines_removed );
00187             fflush ( msgout );
00188         }
00189     }
00190     if ( msgout ) {
00191         fprintf (msgout, "\rRemoved bridges: %5d  %s: %5d",
00192                                     bridges_removed, lmsg, lines_removed );
00193         fprintf (msgout, "\n" );
00194     }
00195 }
00196 
00197 

Generated on Sun Apr 6 17:32:44 2008 for GRASS by  doxygen 1.5.5