GRASS Programmer's Manual  6.4.2(2012)
plus_area.c
Go to the documentation of this file.
00001 
00017 #include <stdlib.h>
00018 #include <grass/Vect.h>
00019 #include <grass/glocale.h>
00020 
00048 int
00049 dig_build_area_with_line(struct Plus_head *plus, plus_t first_line, int side,
00050                          plus_t ** lines)
00051 {
00052     register int i;
00053     int prev_line, next_line;
00054     static plus_t *array;
00055     char *p;
00056     static int array_size;      /* 0 on startup */
00057     int n_lines;
00058     P_LINE *Line;
00059     int node;
00060     const char *dstr;
00061     int debug_level;
00062 
00063     dstr = G__getenv("DEBUG");
00064 
00065     if (dstr != NULL)
00066         debug_level = atoi(dstr);
00067     else
00068         debug_level = 0;
00069         
00070     G_debug(3, "dig_build_area_with_line(): first_line = %d, side = %d",
00071             first_line, side);
00072 
00073     /* First check if line is not degenerated (degenerated lines have angle -9) 
00074      *  Following degenerated lines are skip by dig_angle_next_line() */
00075     Line = plus->Line[first_line];
00076     node = Line->N1;            /* to check one is enough, because if degenerated N1 == N2 */
00077     if (dig_node_line_angle(plus, node, first_line) == -9.) {
00078         G_debug(3, "First line degenerated");
00079         return (0);
00080     }
00081 
00082     if (array_size == 0) {      /* first time */
00083         array_size = 1000;
00084         array = (plus_t *) dig__falloc(array_size, sizeof(plus_t));
00085         if (array == NULL)
00086             return (dig_out_of_memory());
00087     }
00088 
00089     if (side == GV_LEFT) {
00090         first_line = -first_line;       /* start at node1, reverse direction */
00091     }
00092     array[0] = first_line;
00093     prev_line = -first_line;    /* start at node2 for direct and node1 for
00094                                    reverse direction */
00095     /* angle of first line */
00096     n_lines = 1;
00097     while (1) {
00098         next_line =
00099             dig_angle_next_line(plus, prev_line, GV_RIGHT, GV_BOUNDARY);
00100         G_debug(3, "next_line = %d", next_line);
00101 
00102         if (next_line == 0)
00103             return (-1);        /* Not found */
00104 
00105         /* Check if adjacent lines do not have the same angle */
00106         if (!dig_node_angle_check(plus, next_line, GV_BOUNDARY)) {
00107             G_debug(3,
00108                     "Cannot build area, a neighbour of the line %d has the same angle at the node",
00109                     next_line);
00110             return 0;
00111         }
00112 
00113         /*  I. Area closed. This also handles the problem w/ 1 single area line */
00114         if (first_line == next_line) {
00115             /* GOT ONE!  fill area struct  and return */
00116             G_debug(3, "Got one! :");
00117 
00118             /* avoid loop when not debugging */
00119             if (debug_level > 2) {
00120                 for (i = 0; i < n_lines; i++) {
00121                     G_debug(3, " area line (%d) = %d", i, array[i]);
00122                 }
00123             }
00124 
00125             *lines = array;
00126             return (n_lines);
00127         }
00128 
00129         /* II. Note this is a dead end */
00130         /* ( if prev_line != -first_line so it goes after the previous test) ? */
00131         if (prev_line == next_line) {
00132             G_debug(3, "Dead_end:");
00133             return (0);         /* dead end */
00134         }
00135 
00136         /* III. Unclosed ?, I would say started from free end */
00137         for (i = 0; i < n_lines; i++)
00138             if (abs(next_line) == abs(array[i])) {
00139                 G_debug(3, "Unclosed area:");
00140                 return (0);     /* ran into a different area */
00141             }
00142 
00143         /* otherwise keep going */
00144         if (n_lines >= array_size) {
00145             p = dig__frealloc(array, array_size + 100, sizeof(plus_t),
00146                               array_size);
00147             if (p == NULL)
00148                 return (dig_out_of_memory());
00149             array = (plus_t *) p;
00150             array_size += 100;
00151         }
00152         array[n_lines++] = next_line;
00153         prev_line = -next_line;
00154     }
00155 
00156     return 0;
00157 }
00158 
00173 int dig_add_area(struct Plus_head *plus, int n_lines, plus_t * lines)
00174 {
00175     register int i;
00176     register int area, line;
00177     P_AREA *Area;
00178     P_LINE *Line;
00179     BOUND_BOX box, abox;
00180 
00181     G_debug(3, "dig_add_area():");
00182     /* First look if we have space in array of pointers to areas
00183      *  and reallocate if necessary */
00184     if (plus->n_areas >= plus->alloc_areas) {   /* array is full */
00185         if (dig_alloc_areas(plus, 1000) == -1)
00186             return -1;
00187     }
00188 
00189     /* allocate area structure */
00190     area = plus->n_areas + 1;
00191     G_debug(3, "    new area = %d", area);
00192     Area = dig_alloc_area();
00193     if (Area == NULL)
00194         return -1;
00195 
00196     if (dig_area_alloc_line(Area, n_lines) == -1)
00197         return -1;
00198 
00199     for (i = 0; i < n_lines; i++) {
00200         line = lines[i];
00201         Area->lines[i] = line;
00202         Line = plus->Line[abs(line)];
00203         if (plus->do_uplist)
00204             dig_line_add_updated(plus, abs(line));
00205         if (line < 0) {         /* revers direction -> area on left */
00206             if (Line->left != 0) {
00207                 G_warning(_("Line %d already has area/isle %d to left"), line,
00208                           Line->left);
00209                 return -1;
00210             }
00211 
00212             G_debug(3, "  Line %d left set to %d.", line, area);
00213             Line->left = area;
00214         }
00215         else {
00216             if (Line->right != 0) {
00217                 G_warning(_("Line %d already has area/isle %d to right"),
00218                           line, Line->right);
00219                 return -1;
00220             }
00221 
00222             G_debug(3, "  Line %d right set to %d.", line, area);
00223             Line->right = area;
00224         }
00225         dig_line_get_box(plus, abs(line), &box);
00226         if (i == 0)
00227             dig_box_copy(&abox, &box);
00228         else
00229             dig_box_extend(&abox, &box);
00230     }
00231     Area->n_lines = n_lines;
00232     Area->centroid = 0;
00233 
00234     plus->Area[area] = Area;
00235     dig_area_set_box(plus, area, &abox);
00236 
00237     dig_spidx_add_area(plus, area, &abox);
00238 
00239     plus->n_areas++;
00240 
00241     return (area);
00242 }
00243 
00253 int dig_area_add_isle(struct Plus_head *plus, int area, int isle)
00254 {
00255     int i;
00256     P_AREA *Area;
00257 
00258     G_debug(3, "dig_area_add_isle(): area = %d isle = %d", area, isle);
00259 
00260     Area = plus->Area[area];
00261     if (Area == NULL)
00262         G_fatal_error("Attempt to add isle to dead area");
00263 
00264     for (i = 0; i < Area->n_isles; i++) {
00265         if (Area->isles[i] == isle) {   /* Already exist */
00266             G_debug(3, "isle already registered in area");
00267             return 0;
00268         }
00269     }
00270 
00271     if (Area->alloc_isles <= Area->n_isles)     /* array is full */
00272         dig_area_alloc_isle(Area, 1);
00273 
00274     Area->isles[Area->n_isles] = isle;
00275     Area->n_isles++;
00276     G_debug(3, "  -> n_isles = %d", Area->n_isles);
00277 
00278     return 0;
00279 }
00280 
00290 int dig_area_del_isle(struct Plus_head *plus, int area, int isle)
00291 {
00292     int i, mv;
00293     P_AREA *Area;
00294 
00295     G_debug(3, "dig_area_del_isle(): area = %d isle = %d", area, isle);
00296 
00297     Area = plus->Area[area];
00298     if (Area == NULL)
00299         G_fatal_error(_("Attempt to delete isle from dead area"));
00300 
00301     mv = 0;
00302     for (i = 0; i < Area->n_isles; i++) {
00303         if (mv) {
00304             Area->isles[i - 1] = Area->isles[i];
00305         }
00306         else {
00307             if (Area->isles[i] == isle)
00308                 mv = 1;
00309         }
00310     }
00311 
00312     if (mv) {
00313         Area->n_isles--;
00314     }
00315     else {
00316         G_fatal_error(_("Attempt to delete not registered isle %d from area %d"),
00317                       isle, area);
00318     }
00319 
00320     return 0;
00321 }
00322 
00341 int dig_del_area(struct Plus_head *plus, int area)
00342 {
00343     int i, line;
00344 
00345     /* int    isle, area_out; */
00346     P_AREA *Area;
00347     P_LINE *Line;
00348     P_ISLE *Isle;
00349 
00350     G_debug(3, "dig_del_area() area =  %d", area);
00351     Area = plus->Area[area];
00352 
00353     if (Area == NULL) {
00354         G_warning(_("Attempt to delete dead area"));
00355         return 0;
00356     }
00357 
00358     dig_spidx_del_area(plus, area);
00359 
00360     /* Set area for all lines to 0 */
00361     /* isle = 0; */
00362     for (i = 0; i < Area->n_lines; i++) {
00363         line = Area->lines[i];  /* >0 = clockwise -> right, <0 = counterclockwise ->left */
00364         Line = plus->Line[abs(line)];
00365         if (plus->do_uplist)
00366             dig_line_add_updated(plus, abs(line));
00367         if (line > 0) {
00368             G_debug(3, "  Set line %d right side to 0", line);
00369             Line->right = 0;
00370         }
00371         else {
00372             G_debug(3, "  Set line %d left side to 0", line);
00373             Line->left = 0;
00374         }
00375 
00376         /* Find the isle this area is part of (used late below) */
00377         /*
00378            if ( line > 0 ) {
00379            if ( Line->left < 0 ) isle = Line->left; 
00380            } else {
00381            if ( Line->right < 0 ) isle = Line->right; 
00382            }
00383          */
00384     }
00385 
00386     /* Unset area information of centroid */
00387     /* TODO: duplicate centroids have also area information ->
00388      *        1) do not save such info
00389      *        2) find all by box and reset info */
00390     line = Area->centroid;
00391     if (line > 0) {
00392         Line = plus->Line[line];
00393         if (!Line) {
00394             G_warning(_("Dead centroid %d registered for area (bug in the vector library)"),
00395                       line);
00396         }
00397         else {
00398             Line->left = 0;
00399             if (plus->do_uplist)
00400                 dig_line_add_updated(plus, line);
00401         }
00402     }
00403 
00404     /* Find the area this area is within */
00405     /*
00406        area_out = 0;
00407        if ( isle > 0 ) { 
00408        Isle =  plus->Isle[abs(isle)];
00409        area_out = Isle->area;
00410        }
00411      */
00412 
00413     /* Reset information about area outside for isles within this area */
00414     G_debug(3, "  n_isles = %d", Area->n_isles);
00415     for (i = 0; i < Area->n_isles; i++) {
00416         Isle = plus->Isle[Area->isles[i]];
00417         if (Isle == NULL) {
00418             G_fatal_error(_("Attempt to delete area %d info from dead isle %d"),
00419                           area, Area->isles[i]);
00420         }
00421         else {
00422             /* Isle->area = area_out; */
00423             Isle->area = 0;
00424         }
00425     }
00426 
00427     /* TODO: free structures */
00428     plus->Area[area] = NULL;
00429     return 1;
00430 }
00431 
00441 int dig_area_set_box(struct Plus_head *plus, plus_t area, BOUND_BOX * Box)
00442 {
00443     P_AREA *Area;
00444 
00445     Area = plus->Area[area];
00446 
00447     Area->N = Box->N;
00448     Area->S = Box->S;
00449     Area->E = Box->E;
00450     Area->W = Box->W;
00451     Area->T = Box->T;
00452     Area->B = Box->B;
00453 
00454     return (1);
00455 }
00456 
00457 
00473 int
00474 dig_angle_next_line(struct Plus_head *plus, plus_t current_line, int side,
00475                     int type)
00476 {
00477     int i, next;
00478     int current;
00479     int line;
00480     plus_t node;
00481     P_NODE *Node;
00482     P_LINE *Line;
00483     const char *dstr;
00484     int debug_level;
00485 
00486     dstr = G__getenv("DEBUG");
00487 
00488     if (dstr != NULL)
00489         debug_level = atoi(dstr);
00490     else
00491         debug_level = 0;
00492 
00493     G_debug(3, "dig__angle_next_line: line = %d, side = %d, type = %d",
00494             current_line, side, type);
00495 
00496     Line = plus->Line[abs(current_line)];
00497     if (current_line > 0)
00498         node = Line->N1;
00499     else
00500         node = Line->N2;
00501 
00502     G_debug(3, " node = %d", node);
00503 
00504     Node = plus->Node[node];
00505     G_debug(3, "  n_lines = %d", Node->n_lines);
00506     /* avoid loop when not debugging */
00507     if (debug_level > 2) {
00508         for (i = 0; i < Node->n_lines; i++) {
00509             G_debug(3, "  i = %d line = %d angle = %f", i, Node->lines[i],
00510                     Node->angles[i]);
00511         }
00512     }
00513 
00514     /* first find index for that line */
00515     next = -1;
00516     for (current = 0; current < Node->n_lines; current++) {
00517         if (Node->lines[current] == current_line)
00518             next = current;
00519     }
00520     if (next == -1)
00521         return 0;               /* not found */
00522 
00523     G_debug(3, "  current position = %d", next);
00524     while (1) {
00525         if (side == GV_RIGHT) { /* go up (greater angle) */
00526             if (next == Node->n_lines - 1)
00527                 next = 0;
00528             else
00529                 next++;
00530         }
00531         else {                  /* go down (smaller angle) */
00532             if (next == 0)
00533                 next = Node->n_lines - 1;
00534             else
00535                 next--;
00536         }
00537         G_debug(3, "  next = %d line = %d angle = %f", next,
00538                 Node->lines[next], Node->angles[next]);
00539 
00540         if (Node->angles[next] == -9.) {        /* skip points and degenerated */
00541             G_debug(3, "  point/degenerated -> skip");
00542             if (Node->lines[next] == current_line)
00543                 break;          /* Yes, that may happen if input line is degenerated and isolated and this breaks loop */
00544             else
00545                 continue;
00546         }
00547 
00548         line = abs(Node->lines[next]);
00549         Line = plus->Line[line];
00550 
00551         if (Line->type & type) {        /* line found */
00552             G_debug(3, "  this one");
00553             return (Node->lines[next]);
00554         }
00555 
00556         /* input line reached, this must be last, because current_line may be correct return value (dangle) */
00557         if (Node->lines[next] == current_line)
00558             break;
00559     }
00560     G_debug(3, "  Line NOT found at node %d", (int)node);
00561     return 0;
00562 }
00563 
00578 int dig_node_angle_check(struct Plus_head *plus, plus_t line, int type)
00579 {
00580     int next, prev;
00581     float angle1, angle2;
00582     plus_t node;
00583     P_LINE *Line;
00584 
00585     G_debug(3, "dig_node_angle_check: line = %d, type = %d", line, type);
00586 
00587     Line = plus->Line[abs(line)];
00588 
00589     if (line > 0)
00590         node = Line->N1;
00591     else
00592         node = Line->N2;
00593 
00594     angle1 = dig_node_line_angle(plus, node, line);
00595 
00596     /* Next */
00597     next = dig_angle_next_line(plus, line, GV_RIGHT, type);
00598     angle2 = dig_node_line_angle(plus, node, next);
00599     if (angle1 == angle2) {
00600         G_debug(3,
00601                 "  The line to the right has the same angle: node = %d, line = %d",
00602                 node, next);
00603         return 0;
00604     }
00605 
00606     /* Previous */
00607     prev = dig_angle_next_line(plus, line, GV_LEFT, type);
00608     angle2 = dig_node_line_angle(plus, node, prev);
00609     if (angle1 == angle2) {
00610         G_debug(3,
00611                 "  The line to the left has the same angle: node = %d, line = %d",
00612                 node, next);
00613         return 0;
00614     }
00615 
00616     return 1;                   /* OK */
00617 }
00618 
00634 int dig_add_isle(struct Plus_head *plus, int n_lines, plus_t * lines)
00635 {
00636     register int i;
00637     register int isle, line;
00638     P_ISLE *Isle;
00639     P_LINE *Line;
00640     BOUND_BOX box, abox;
00641 
00642     G_debug(3, "dig_add_isle():");
00643     /* First look if we have space in array of pointers to isles
00644      *  and reallocate if necessary */
00645     if (plus->n_isles >= plus->alloc_isles) {   /* array is full */
00646         if (dig_alloc_isles(plus, 1000) == -1)
00647             return -1;
00648     }
00649 
00650     /* allocate isle structure */
00651     isle = plus->n_isles + 1;
00652     Isle = dig_alloc_isle();
00653     if (Isle == NULL)
00654         return -1;
00655 
00656     if ((dig_isle_alloc_line(Isle, n_lines)) == -1)
00657         return -1;
00658 
00659     Isle->area = 0;
00660 
00661     Isle->N = 0;
00662     Isle->S = 0;
00663     Isle->E = 0;
00664     Isle->W = 0;
00665 
00666     for (i = 0; i < n_lines; i++) {
00667         line = lines[i];
00668         G_debug(3, " i = %d line = %d", i, line);
00669         Isle->lines[i] = line;
00670         Line = plus->Line[abs(line)];
00671         if (plus->do_uplist)
00672             dig_line_add_updated(plus, abs(line));
00673         if (line < 0) {         /* revers direction -> isle on left */
00674             if (Line->left != 0) {
00675                 G_warning(_("Line %d already has area/isle %d to left"), line,
00676                           Line->left);
00677                 return -1;
00678             }
00679             Line->left = -isle;
00680         }
00681         else {
00682             if (Line->right != 0) {
00683                 G_warning(_("Line %d already has area/isle %d to left"), line,
00684                           Line->right);
00685                 return -1;
00686             }
00687 
00688             Line->right = -isle;
00689         }
00690         dig_line_get_box(plus, abs(line), &box);
00691         if (i == 0)
00692             dig_box_copy(&abox, &box);
00693         else
00694             dig_box_extend(&abox, &box);
00695     }
00696 
00697     Isle->n_lines = n_lines;
00698 
00699     plus->Isle[isle] = Isle;
00700 
00701     dig_isle_set_box(plus, isle, &abox);
00702 
00703     dig_spidx_add_isle(plus, isle, &abox);
00704 
00705     plus->n_isles++;
00706 
00707     return (isle);
00708 }
00709 
00710 
00720 int dig_isle_set_box(struct Plus_head *plus, plus_t isle, BOUND_BOX * Box)
00721 {
00722     P_ISLE *Isle;
00723 
00724     Isle = plus->Isle[isle];
00725 
00726     Isle->N = Box->N;
00727     Isle->S = Box->S;
00728     Isle->E = Box->E;
00729     Isle->W = Box->W;
00730     Isle->T = Box->T;
00731     Isle->B = Box->B;
00732 
00733     return (1);
00734 }
00735 
00746 int dig_del_isle(struct Plus_head *plus, int isle)
00747 {
00748     int i, line;
00749     P_LINE *Line;
00750     P_ISLE *Isle;
00751 
00752     G_debug(3, "dig_del_isle() isle =  %d", isle);
00753     Isle = plus->Isle[isle];
00754 
00755     dig_spidx_del_isle(plus, isle);
00756 
00757     /* Set area for all lines to 0 */
00758     for (i = 0; i < Isle->n_lines; i++) {
00759         line = Isle->lines[i];  /* >0 = clockwise -> right, <0 = counterclockwise ->left */
00760         Line = plus->Line[abs(line)];
00761         if (plus->do_uplist)
00762             dig_line_add_updated(plus, abs(line));
00763         if (line > 0)
00764             Line->right = 0;
00765         else
00766             Line->left = 0;
00767     }
00768 
00769     /* Delete reference from area it is within */
00770     G_debug(3, "  area outside isle = %d", Isle->area);
00771     if (Isle->area > 0) {
00772         if (plus->Area[Isle->area] == NULL) {
00773             G_fatal_error(_("Attempt to delete isle %d info from dead area %d"),
00774                           isle, Isle->area);
00775         }
00776         else {
00777             dig_area_del_isle(plus, Isle->area, isle);
00778         }
00779     }
00780 
00781     /* TODO: free structures */
00782 
00783     plus->Isle[isle] = NULL;
00784 
00785     return 1;
00786 }
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines