plus_area.c

Go to the documentation of this file.
00001 /*
00002 * $Id: plus_area.c,v 1.11 2006/02/09 03:08:58 glynn Exp $
00003 *
00004 ****************************************************************************
00005 *
00006 * MODULE:       Vector library 
00007 *               
00008 * AUTHOR(S):    Dave Gerdes, CERL.
00009 *               Update to GRASS 5.7 Radim Blazek.
00010 *
00011 * PURPOSE:      Lower level functions for reading/writing/manipulating vectors.
00012 *
00013 * COPYRIGHT:    (C) 2001 by the GRASS Development Team
00014 *
00015 *               This program is free software under the GNU General Public
00016 *               License (>=v2). Read the file COPYING that comes with GRASS
00017 *               for details.
00018 *
00019 *****************************************************************************/
00020 #include <stdlib.h>
00021 #include <grass/Vect.h>
00022 
00023 /*
00024 ** build_area_with_line ()
00025 ** this is the real guts of build area stuff
00026 **
00027 ** Area is built in clockwise order.
00028 ** Take a given line and start off to the RIGHT/LEFT and try to complete
00029 ** an area. 
00030 ** 
00031 ** Possible Scenarios:
00032 ** I.    path runs into first line.                              : AREA!
00033 ** II.   path runs into a dead end (no other area lines at node) : no area
00034 ** III.  path runs into a previous line that is not 1st line    
00035 **                  or to 1st line but not to start node         : no area
00036 **
00037 ** after we find an area then we call point_in_area to see if the
00038 ** specified point is w/in the area
00039 **
00040 ** old returns  -1:  error   0:  no area    (1:  point in area)
00041 **          -2: island  !!
00042 **
00043 ** returns  -1:  error   
00044 **           0:  no area
00045 **           number  of lines
00046 **
00047 */
00048 
00049 int 
00050 dig_build_area_with_line ( struct Plus_head *plus, 
00051         plus_t first_line, /* always positive */
00052         int side,          /* side of line to build area on */
00053         plus_t **lines)    /* pointer to array of lines */
00054 {
00055   register int i;
00056   int prev_line, next_line;
00057   static plus_t *array;
00058   char *p;
00059   static int array_size;        /* 0 on startup */
00060   int n_lines;
00061   P_LINE *Line;
00062   int node;
00063 
00064   G_debug (3, "dig_build_area_with_line(): first_line = %d, side = %d", first_line, side);
00065   
00066   /* First check if line is not degenerated (degenerated lines have angle -9) 
00067   *  Following degenerated lines are skip by dig_angle_next_line() */
00068   Line = plus->Line[first_line];
00069   node = Line->N1; /* to check one is enough, because if degenerated N1 == N2 */
00070   if ( dig_node_line_angle ( plus, node, first_line ) == -9.) {
00071       G_debug (3, "First line degenerated");
00072       return (0);
00073   }
00074   
00075   if (array_size == 0) {                /* first time */
00076       array_size = 1000;
00077       array = (plus_t *) dig__falloc (array_size, sizeof (plus_t));
00078       if (array == NULL )
00079         return (dig_out_of_memory ());
00080   }
00081   
00082   if (side == GV_LEFT) {
00083       first_line  = -first_line;  /* start at node1, reverse direction */
00084   }
00085   array[0]  =   first_line;
00086   prev_line =  -first_line;  /* start at node2 for direct and node1 for
00087                                 reverse direction */
00088   /* angle of first line */
00089   n_lines = 1;
00090   while (1)
00091     {
00092       next_line = dig_angle_next_line (plus, prev_line, GV_RIGHT, GV_BOUNDARY );
00093       G_debug (3, "next_line = %d", next_line );
00094 
00095       if (next_line == 0) return (-1); /* Not found */
00096 
00097       /* Check if adjacent lines do not have the same angle */
00098       if ( !dig_node_angle_check ( plus, next_line, GV_BOUNDARY) ) {
00099           G_debug (3, "Cannot build area, a neighbour of the line %d has the same angle at the node", 
00100                        next_line );
00101           return 0;
00102       }
00103 
00104       /*  I. Area closed. This also handles the problem w/ 1 single area line */
00105       if (first_line == next_line) {
00106           /* GOT ONE!  fill area struct  and return */
00107           G_debug (3, "Got one! :");
00108 
00109           for (i = 0; i < n_lines; i++) {
00110               G_debug (3, " area line (%d) = %d", i, array[i]);
00111             }
00112 
00113            *lines = array;
00114            return (n_lines);
00115         }
00116 
00117       /* II. Note this is a dead end */
00118       /* ( if prev_line != -first_line so it goes after the previous test) ? */
00119       if (prev_line == next_line)
00120         {
00121           G_debug (3, "Dead_end:");
00122           return (0);           /* dead end */
00123         }
00124 
00125       /* III. Unclosed ?, I would say started from free end */
00126       for (i = 0; i < n_lines; i++)
00127         if (abs (next_line) == abs (array[i]))
00128           {
00129             G_debug (3, "Unclosed area:");
00130             return (0);         /* ran into a different area */
00131           }
00132 
00133       /* otherwise keep going */
00134       if (n_lines >= array_size)
00135         {
00136           p = dig__frealloc (array, array_size + 100, sizeof (plus_t), array_size);
00137           if (p == NULL)
00138             return (dig_out_of_memory ());
00139           array = (plus_t *) p;
00140           array_size += 100;
00141         }
00142       array[n_lines++] = next_line;
00143       prev_line = -next_line;
00144     }
00145 
00146   return 0;
00147 }
00148 
00149 /* dig_add_area
00150 *  Allocate space for new area and create boundary info from array.
00151 *  Then for each line in area, update line (right,left) info.
00152 *
00153 *  Neither islands nor centroids area filled.
00154 *
00155 *  Returns: number of new area
00156 *           -1 error
00157 */
00158 int 
00159 dig_add_area (struct Plus_head *plus, 
00160         int n_lines,       /* number of lines */
00161         plus_t *lines )    /* array of lines, negative for reverse direction */ 
00162 {
00163     register int i;
00164     register int area, line;
00165     P_AREA *Area;
00166     P_LINE *Line;
00167     BOUND_BOX box, abox;
00168 
00169     G_debug (3, "dig_add_area():");
00170     /* First look if we have space in array of pointers to areas
00171     *  and reallocate if necessary */
00172     if ( plus->n_areas >= plus->alloc_areas ) { /* array is full */
00173         if ( dig_alloc_areas(plus,1000) == -1 )
00174             return -1;
00175     }
00176 
00177     /* allocate area structure */
00178     area = plus->n_areas +1;
00179     G_debug (3, "    new area = %d", area);
00180     Area = dig_alloc_area();
00181     if (Area == NULL) return -1;
00182 
00183     if ( dig_area_alloc_line (Area, n_lines) == -1 )
00184         return -1;
00185     
00186     for (i = 0; i < n_lines; i++) {
00187         line = lines[i];
00188         Area->lines[i] = line;  
00189         Line = plus->Line[abs(line)];
00190         if ( plus->do_uplist ) dig_line_add_updated ( plus, abs(line) );
00191         if (line < 0) { /* revers direction -> area on left */
00192             if ( Line->left != 0 ) {
00193                 G_warning ("Line %d already has area/isle %d to left.", line, Line->left);
00194                 return -1;
00195             }
00196             
00197             G_debug (3, "  Line %d left set to %d.", line, area);
00198             Line->left = area;
00199         } else {
00200             if ( Line->right != 0 ) {
00201                 G_warning ("Line %d already has area/isle %d to right.", line, Line->right);
00202                 return -1;
00203             }
00204 
00205             G_debug (3, "  Line %d right set to %d.", line, area);
00206             Line->right = area;
00207         }
00208         dig_line_get_box ( plus, abs(line), &box );
00209         if ( i == 0 ) dig_box_copy (&abox, &box); 
00210         else dig_box_extend (&abox, &box); 
00211     }
00212     Area->n_lines = n_lines;
00213     Area->centroid = 0;
00214   
00215     plus->Area[area] = Area;
00216     dig_area_set_box (plus, area, &abox);
00217     
00218     dig_spidx_add_area ( plus, area, &abox ); 
00219     
00220     plus->n_areas++;
00221   
00222     return (area);
00223 }
00224 
00225 /* dig_area_add_isle()
00226 *  Add isle to area if does not exist yet.
00227 *
00228 *  Returns:
00229 */
00230 int 
00231 dig_area_add_isle (struct Plus_head *plus, int area, int isle)
00232 {
00233     int i;
00234     P_AREA *Area;
00235 
00236     G_debug (3, "dig_area_add_isle(): area = %d isle = %d", area, isle );
00237     
00238     Area = plus->Area[area];
00239     if ( Area == NULL ) G_fatal_error("Attempt to add isle to dead area");
00240     
00241     for ( i = 0; i < Area->n_isles; i++) {
00242         if ( Area->isles[i] == isle ) { /* Already exist */
00243             G_debug (3, "isle already registered in area" ); 
00244             return 0;
00245         }
00246     }
00247     
00248     if ( Area->alloc_isles <= Area->n_isles ) /* array is full */
00249         dig_area_alloc_isle (Area, 1);
00250     
00251     Area->isles[Area->n_isles] = isle;
00252     Area->n_isles++;
00253     G_debug ( 3, "  -> n_isles = %d", Area->n_isles); 
00254     
00255     return 0;
00256 }
00257 
00258 /* dig_area_del_isle()
00259 *  Delete isle from area.
00260 *
00261 *  Returns:
00262 */
00263 int 
00264 dig_area_del_isle (struct Plus_head *plus, int area, int isle)
00265 {
00266     int i, mv;
00267     P_AREA *Area;
00268 
00269     G_debug (3, "dig_area_del_isle(): area = %d isle = %d", area, isle );
00270     
00271     Area = plus->Area[area];
00272     if ( Area == NULL ) G_fatal_error("Attempt to delete isle from dead area");
00273     
00274     mv = 0;
00275     for ( i = 0; i < Area->n_isles; i++ ) {
00276         if ( mv ) {
00277             Area->isles[i-1] = Area->isles[i];
00278         } else {
00279             if ( Area->isles[i] == isle ) mv = 1;
00280         }
00281     }
00282     
00283     if ( mv ) {
00284         Area->n_isles--;
00285     } else {
00286         G_fatal_error("Attempt to delete not registered isle (%d) from area (%d)", isle, area);
00287     }
00288     
00289     return 0;
00290 }
00291 
00292 /* Delete area from topology. 
00293 *  This function deletes area from the topo structure and resets references
00294 *  to this area in lines, isles (within) to 0. 
00295 *  Possible new area is not created by this function, so that
00296 *  old boundaries participating in this area are left without area information
00297 *  even if form new area.
00298 *  Not enabled now: If area is inside other area, area info for islands within 
00299 *                   deleted area is reset to that area outside.
00300 *  (currently area info of isles is set to 0)
00301 */ 
00302 int
00303 dig_del_area (struct Plus_head *plus, int area ) {
00304     int    i, line;
00305     /* int    isle, area_out; */
00306     P_AREA *Area;
00307     P_LINE *Line;
00308     P_ISLE *Isle;
00309 
00310     G_debug (3, "dig_del_area() area =  %d", area);
00311     Area = plus->Area[area];
00312 
00313     if ( Area == NULL ) {
00314         G_warning ("Attempt to delete dead area");
00315         return 0;
00316     }
00317 
00318     dig_spidx_del_area ( plus, area );
00319     
00320     /* Set area for all lines to 0 */
00321     /* isle = 0; */
00322     for (i = 0; i < Area->n_lines; i++) {
00323         line = Area->lines[i]; /* >0 = clockwise -> right, <0 = counterclockwise ->left */
00324         Line = plus->Line[abs(line)];
00325         if ( plus->do_uplist ) dig_line_add_updated ( plus, abs(line) );
00326         if ( line > 0 ) {
00327             G_debug ( 3, "  Set line %d right side to 0", line );
00328             Line->right = 0; 
00329         } else {
00330             G_debug ( 3, "  Set line %d left side to 0", line );
00331             Line->left = 0;
00332         }
00333             
00334         /* Find the isle this area is part of (used late below) */
00335         /*
00336         if ( line > 0 ) {
00337             if ( Line->left < 0 ) isle = Line->left; 
00338         } else {
00339             if ( Line->right < 0 ) isle = Line->right; 
00340         }
00341         */
00342     }
00343     
00344     /* Unset area information of centroid */
00345     /* TODO: duplicate centroids have also area information ->
00346     *        1) do not save such info
00347     *        2) find all by box and reset info */
00348     line = Area->centroid;
00349     if ( line > 0 ) {
00350         Line = plus->Line[line];
00351         if ( !Line ) {
00352             G_warning ( "Dead centroid (%d) registered for area (bug in the library).", line );
00353         } else {
00354             Line->left = 0;           
00355             if ( plus->do_uplist ) dig_line_add_updated ( plus, line );
00356         }
00357     }
00358     
00359     /* Find the area this area is within */
00360     /*
00361     area_out = 0;
00362     if ( isle > 0 ) { 
00363         Isle =  plus->Isle[abs(isle)];
00364         area_out = Isle->area;
00365     }
00366     */
00367     
00368     /* Reset information about area outside for isles within this area */ 
00369     G_debug ( 3, "  n_isles = %d", Area->n_isles );
00370     for (i = 0; i < Area->n_isles; i++) {
00371         Isle =  plus->Isle[Area->isles[i]];
00372         if (  Isle == NULL ) {
00373             G_fatal_error ("Attempt to delete area (%d) info from dead isle (%d)", area, Area->isles[i] );
00374         } else {
00375             /* Isle->area = area_out; */
00376             Isle->area = 0;
00377         }
00378     }
00379             
00380     /* TODO: free structures */
00381     plus->Area[area] = NULL;
00382     return 1;
00383 }
00384 
00385 /* 
00386 *  dig_area_set_box ()
00387 *  Set area bound box
00388 */
00389 int
00390 dig_area_set_box (struct Plus_head *plus, plus_t area, BOUND_BOX *Box ) {
00391     P_AREA *Area;
00392     
00393     Area = plus->Area[area];
00394     
00395     Area->N = Box->N;
00396     Area->S = Box->S;
00397     Area->E = Box->E;
00398     Area->W = Box->W;
00399     Area->T = Box->T;
00400     Area->B = Box->B;
00401 
00402     return (1);
00403 }
00404 
00405 
00406 /* 
00407 ** dig_angle_next_line ()
00408 **   assume that lines are sorted in increasing angle order and angles of points
00409 **   and degenerated lines are set to 9 (ignored).
00410 **
00411 **   Return line number of next angle to follow an line (negative if connected by node2)
00412 **               (number of current line may be return if dangle - this is used in build)
00413 **          0 on error or not found
00414 */
00415 int 
00416 dig_angle_next_line ( 
00417       struct Plus_head *plus,
00418       plus_t current_line,      /* current line number,
00419                                  * negative if request for node 2 */
00420       int side,                 /* GV_RIGHT or GV_LEFT */
00421       int type)                 /* type of line GV_LINE, GV_BOUNDARY or both */
00422 {
00423   int i, next;
00424   int current;
00425   int line;
00426   plus_t node;
00427   P_NODE *Node;
00428   P_LINE *Line;
00429 
00430   G_debug (3, "dig__angle_next_line: line = %d, side = %d, type = %d", current_line, side, type);
00431 
00432   Line = plus->Line[abs(current_line)];
00433   if ( current_line > 0 ) node = Line->N1;
00434   else node = Line->N2; 
00435   
00436   G_debug (3, " node = %d", node);
00437 
00438   Node = plus->Node[node];
00439   G_debug (3, "  n_lines = %d", Node->n_lines );
00440   for ( i = 0; i < Node->n_lines; i++ ) {
00441       G_debug (3, "  i = %d line = %d angle = %f", i, Node->lines[i], Node->angles[i] );
00442   }
00443     
00444   /* first find index for that line */
00445   next = -1;
00446   for (current = 0; current < Node->n_lines; current++) {
00447     if (Node->lines[current] == current_line)
00448       next = current;
00449   }
00450   if ( next == -1 ) return 0;       /* not found */
00451   
00452   G_debug (3, "  current position = %d", next );
00453   while (1) {
00454       if (side == GV_RIGHT) {  /* go up (greater angle) */
00455           if (next == Node->n_lines - 1)
00456             next = 0;
00457           else
00458             next++;
00459       } else {                      /* go down (smaller angle) */
00460           if (next == 0)
00461             next = Node->n_lines - 1;
00462           else
00463             next--;
00464       }
00465       G_debug (3, "  next = %d line = %d angle = %f", next, Node->lines[next], Node->angles[next] );
00466 
00467       if ( Node->angles[next] == -9. ) { /* skip points and degenerated */
00468           G_debug (3, "  point/degenerated -> skip" );
00469           if ( Node->lines[next] == current_line  ) 
00470               break; /* Yes, that may happen if input line is degenerated and isolated and this breaks loop */ 
00471           else 
00472               continue; 
00473       }
00474       
00475       line = abs ( Node->lines[next] );
00476       Line = plus->Line[line];
00477       
00478       if ( Line->type & type ) { /* line found */
00479           G_debug (3, "  this one" );
00480           return ( Node->lines[next] );
00481       }
00482       
00483       /* input line reached, this must be last, because current_line may be correct return value (dangle) */
00484       if ( Node->lines[next] == current_line  ) break; 
00485   }
00486   G_debug (3, "  Line NOT found at node %d", (int) node);
00487   return 0;
00488 }
00489 
00490 /* 
00491 ** dig_node_angle_check ()
00492 **   Checks if angles of adjacent lines differ.
00493 **   Negative line number for end point.
00494 **   assume that lines are sorted in increasing angle order and angles of points
00495 **   and degenerated lines are set to 9 (ignored).
00496 **
00497 **   Return 1 - angles differ
00498 **          0 - angle of a line up or down is identical
00499 */
00500 int 
00501 dig_node_angle_check ( 
00502       struct Plus_head *plus,
00503       plus_t line,              /* current line number,
00504                                  * negative if request for node 2 */
00505       int type)                 /* type of line GV_LINE, GV_BOUNDARY or both */
00506 {
00507   int next, prev;
00508   float  angle1, angle2;
00509   plus_t node;
00510   P_LINE *Line;
00511 
00512   G_debug (3, "dig_node_angle_check: line = %d, type = %d", line, type);
00513 
00514   Line = plus->Line[abs(line)];
00515 
00516   if ( line > 0 ) node = Line->N1;
00517   else node = Line->N2; 
00518   
00519   angle1 = dig_node_line_angle ( plus, node, line );
00520   
00521   /* Next */
00522   next = dig_angle_next_line ( plus, line, GV_RIGHT, type );
00523   angle2 = dig_node_line_angle ( plus, node, next );
00524   if ( angle1 == angle2 ) {
00525       G_debug (3, "  The line to the right has the same angle: node = %d, line = %d", node, next);
00526       return 0;
00527   }
00528   
00529   /* Previous */
00530   prev = dig_angle_next_line ( plus, line, GV_LEFT, type );
00531   angle2 = dig_node_line_angle ( plus, node, prev );
00532   if ( angle1 == angle2 ) {
00533       G_debug (3, "  The line to the left has the same angle: node = %d, line = %d", node, next);
00534       return 0;
00535   }
00536   
00537   return 1; /* OK */
00538 }         
00539           
00540 /* dig_add_isle
00541 *  Allocate space for new island and create boundary info from array.
00542 *  The order of impult lines is expected to be counter clockwise.
00543 *  Then for each line in isle, update line (right,left) info.
00544 *
00545 *  Area number the island is within is not filled.
00546 *
00547 *  Returns: number of new isle
00548 *           -1 error
00549 */
00550 int 
00551 dig_add_isle (struct Plus_head *plus, 
00552         int n_lines,       /* number of lines */
00553         plus_t *lines )    /* array of lines, negative for reverse direction */ 
00554 {
00555     register int i;
00556     register int isle, line;
00557     P_ISLE *Isle;
00558     P_LINE *Line;
00559     BOUND_BOX box, abox;
00560 
00561     G_debug (3, "dig_add_isle():");
00562     /* First look if we have space in array of pointers to isles
00563     *  and reallocate if necessary */
00564     if ( plus->n_isles >= plus->alloc_isles ) { /* array is full */
00565         if ( dig_alloc_isles(plus,1000) == -1 )
00566              return -1;
00567     }
00568 
00569     /* allocate isle structure */
00570     isle = plus->n_isles + 1;
00571     Isle = dig_alloc_isle();
00572     if (Isle == NULL) return -1;
00573 
00574     if ( ( dig_isle_alloc_line (Isle, n_lines) ) == -1 )
00575         return -1;
00576 
00577     Isle->area = 0;
00578 
00579     Isle->N = 0;
00580     Isle->S = 0;
00581     Isle->E = 0;
00582     Isle->W = 0;
00583     
00584     for (i = 0; i < n_lines; i++) {
00585         line = lines[i];
00586         G_debug (3, " i = %d line = %d", i, line);
00587         Isle->lines[i] = line;  
00588         Line = plus->Line[abs(line)];
00589         if ( plus->do_uplist ) dig_line_add_updated ( plus, abs(line) );
00590         if (line < 0) { /* revers direction -> isle on left */
00591             if ( Line->left != 0 ) {
00592                 G_warning ("Line %d already has area/isle %d to left.", line, Line->left);
00593                 return -1;
00594             }
00595             Line->left = -isle;
00596         } else {
00597             if ( Line->right != 0 ) {
00598                 G_warning ("Line %d already has area/isle %d to left.", line, Line->right);
00599                 return -1;
00600             }
00601             
00602             Line->right = -isle;
00603         }
00604         dig_line_get_box ( plus, abs(line), &box );
00605         if ( i == 0 ) dig_box_copy (&abox, &box); 
00606         else dig_box_extend (&abox, &box); 
00607     }
00608 
00609     Isle->n_lines = n_lines;
00610   
00611     plus->Isle[isle] = Isle;
00612     
00613     dig_isle_set_box (plus, isle, &abox);
00614     
00615     dig_spidx_add_isle ( plus, isle, &abox ); 
00616     
00617     plus->n_isles++;
00618   
00619     return (isle);
00620 }
00621 
00622 
00623 /* 
00624 *  dig_isle_set_box ()
00625 *  Set isle bound box
00626 */
00627 int
00628 dig_isle_set_box (struct Plus_head *plus, plus_t isle, BOUND_BOX *Box ) {
00629     P_ISLE *Isle;
00630     
00631     Isle = plus->Isle[isle];
00632     
00633     Isle->N = Box->N;
00634     Isle->S = Box->S;
00635     Isle->E = Box->E;
00636     Isle->W = Box->W;
00637     Isle->T = Box->T;
00638     Isle->B = Box->B;
00639 
00640     return (1);
00641 }
00642 
00643 /* Delete island from topology. Reset references to it in lines and area outside.
00644 */
00645 int
00646 dig_del_isle (struct Plus_head *plus, int isle ) {
00647     int    i, line;
00648     P_LINE *Line;
00649     P_ISLE *Isle;
00650 
00651     G_debug (3, "dig_del_isle() isle =  %d", isle);
00652     Isle = plus->Isle[isle];
00653 
00654     dig_spidx_del_isle ( plus, isle );
00655     
00656     /* Set area for all lines to 0 */
00657     for (i = 0; i < Isle->n_lines; i++) {
00658         line = Isle->lines[i]; /* >0 = clockwise -> right, <0 = counterclockwise ->left */
00659         Line = plus->Line[abs(line)];
00660         if ( plus->do_uplist ) dig_line_add_updated ( plus, abs(line) );
00661         if ( line > 0 ) Line->right = 0; else Line->left = 0;
00662     }
00663 
00664     /* Delete reference from area it is within */
00665     G_debug (3, "  area outside isle = %d", Isle->area);
00666     if ( Isle->area > 0 ) {
00667         if (  plus->Area[Isle->area] == NULL ) {
00668             G_fatal_error ("Attempt to delete isle (%d) info from dead area (%d)", isle, Isle->area );
00669         } else { 
00670             dig_area_del_isle (plus, Isle->area, isle);
00671         }
00672     }
00673     
00674     /* TODO: free structures */
00675 
00676     plus->Isle[isle] = NULL;
00677     
00678     return 1;
00679 }
00680 

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