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 
00061     G_debug(3, "dig_build_area_with_line(): first_line = %d, side = %d",
00062             first_line, side);
00063 
00064     /* First check if line is not degenerated (degenerated lines have angle -9) 
00065      *  Following degenerated lines are skip by dig_angle_next_line() */
00066     Line = plus->Line[first_line];
00067     node = Line->N1;            /* to check one is enough, because if degenerated N1 == N2 */
00068     if (dig_node_line_angle(plus, node, first_line) == -9.) {
00069         G_debug(3, "First line degenerated");
00070         return (0);
00071     }
00072 
00073     if (array_size == 0) {      /* first time */
00074         array_size = 1000;
00075         array = (plus_t *) dig__falloc(array_size, sizeof(plus_t));
00076         if (array == NULL)
00077             return (dig_out_of_memory());
00078     }
00079 
00080     if (side == GV_LEFT) {
00081         first_line = -first_line;       /* start at node1, reverse direction */
00082     }
00083     array[0] = first_line;
00084     prev_line = -first_line;    /* start at node2 for direct and node1 for
00085                                    reverse direction */
00086     /* angle of first line */
00087     n_lines = 1;
00088     while (1) {
00089         next_line =
00090             dig_angle_next_line(plus, prev_line, GV_RIGHT, GV_BOUNDARY);
00091         G_debug(3, "next_line = %d", next_line);
00092 
00093         if (next_line == 0)
00094             return (-1);        /* Not found */
00095 
00096         /* Check if adjacent lines do not have the same angle */
00097         if (!dig_node_angle_check(plus, next_line, GV_BOUNDARY)) {
00098             G_debug(3,
00099                     "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             G_debug(3, "Dead_end:");
00121             return (0);         /* dead end */
00122         }
00123 
00124         /* III. Unclosed ?, I would say started from free end */
00125         for (i = 0; i < n_lines; i++)
00126             if (abs(next_line) == abs(array[i])) {
00127                 G_debug(3, "Unclosed area:");
00128                 return (0);     /* ran into a different area */
00129             }
00130 
00131         /* otherwise keep going */
00132         if (n_lines >= array_size) {
00133             p = dig__frealloc(array, array_size + 100, sizeof(plus_t),
00134                               array_size);
00135             if (p == NULL)
00136                 return (dig_out_of_memory());
00137             array = (plus_t *) p;
00138             array_size += 100;
00139         }
00140         array[n_lines++] = next_line;
00141         prev_line = -next_line;
00142     }
00143 
00144     return 0;
00145 }
00146 
00161 int dig_add_area(struct Plus_head *plus, int n_lines, plus_t * lines)
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)
00182         return -1;
00183 
00184     if (dig_area_alloc_line(Area, n_lines) == -1)
00185         return -1;
00186 
00187     for (i = 0; i < n_lines; i++) {
00188         line = lines[i];
00189         Area->lines[i] = line;
00190         Line = plus->Line[abs(line)];
00191         if (plus->do_uplist)
00192             dig_line_add_updated(plus, abs(line));
00193         if (line < 0) {         /* revers direction -> area on left */
00194             if (Line->left != 0) {
00195                 G_warning(_("Line %d already has area/isle %d to left"), line,
00196                           Line->left);
00197                 return -1;
00198             }
00199 
00200             G_debug(3, "  Line %d left set to %d.", line, area);
00201             Line->left = area;
00202         }
00203         else {
00204             if (Line->right != 0) {
00205                 G_warning(_("Line %d already has area/isle %d to right"),
00206                           line, Line->right);
00207                 return -1;
00208             }
00209 
00210             G_debug(3, "  Line %d right set to %d.", line, area);
00211             Line->right = area;
00212         }
00213         dig_line_get_box(plus, abs(line), &box);
00214         if (i == 0)
00215             dig_box_copy(&abox, &box);
00216         else
00217             dig_box_extend(&abox, &box);
00218     }
00219     Area->n_lines = n_lines;
00220     Area->centroid = 0;
00221 
00222     plus->Area[area] = Area;
00223     dig_area_set_box(plus, area, &abox);
00224 
00225     dig_spidx_add_area(plus, area, &abox);
00226 
00227     plus->n_areas++;
00228 
00229     return (area);
00230 }
00231 
00241 int dig_area_add_isle(struct Plus_head *plus, int area, int isle)
00242 {
00243     int i;
00244     P_AREA *Area;
00245 
00246     G_debug(3, "dig_area_add_isle(): area = %d isle = %d", area, isle);
00247 
00248     Area = plus->Area[area];
00249     if (Area == NULL)
00250         G_fatal_error("Attempt to add isle to dead area");
00251 
00252     for (i = 0; i < Area->n_isles; i++) {
00253         if (Area->isles[i] == isle) {   /* Already exist */
00254             G_debug(3, "isle already registered in area");
00255             return 0;
00256         }
00257     }
00258 
00259     if (Area->alloc_isles <= Area->n_isles)     /* array is full */
00260         dig_area_alloc_isle(Area, 1);
00261 
00262     Area->isles[Area->n_isles] = isle;
00263     Area->n_isles++;
00264     G_debug(3, "  -> n_isles = %d", Area->n_isles);
00265 
00266     return 0;
00267 }
00268 
00278 int dig_area_del_isle(struct Plus_head *plus, int area, int isle)
00279 {
00280     int i, mv;
00281     P_AREA *Area;
00282 
00283     G_debug(3, "dig_area_del_isle(): area = %d isle = %d", area, isle);
00284 
00285     Area = plus->Area[area];
00286     if (Area == NULL)
00287         G_fatal_error(_("Attempt to delete isle from dead area"));
00288 
00289     mv = 0;
00290     for (i = 0; i < Area->n_isles; i++) {
00291         if (mv) {
00292             Area->isles[i - 1] = Area->isles[i];
00293         }
00294         else {
00295             if (Area->isles[i] == isle)
00296                 mv = 1;
00297         }
00298     }
00299 
00300     if (mv) {
00301         Area->n_isles--;
00302     }
00303     else {
00304         G_fatal_error(_("Attempt to delete not registered isle %d from area %d"),
00305                       isle, area);
00306     }
00307 
00308     return 0;
00309 }
00310 
00329 int dig_del_area(struct Plus_head *plus, int area)
00330 {
00331     int i, line;
00332 
00333     /* int    isle, area_out; */
00334     P_AREA *Area;
00335     P_LINE *Line;
00336     P_ISLE *Isle;
00337 
00338     G_debug(3, "dig_del_area() area =  %d", area);
00339     Area = plus->Area[area];
00340 
00341     if (Area == NULL) {
00342         G_warning(_("Attempt to delete dead area"));
00343         return 0;
00344     }
00345 
00346     dig_spidx_del_area(plus, area);
00347 
00348     /* Set area for all lines to 0 */
00349     /* isle = 0; */
00350     for (i = 0; i < Area->n_lines; i++) {
00351         line = Area->lines[i];  /* >0 = clockwise -> right, <0 = counterclockwise ->left */
00352         Line = plus->Line[abs(line)];
00353         if (plus->do_uplist)
00354             dig_line_add_updated(plus, abs(line));
00355         if (line > 0) {
00356             G_debug(3, "  Set line %d right side to 0", line);
00357             Line->right = 0;
00358         }
00359         else {
00360             G_debug(3, "  Set line %d left side to 0", line);
00361             Line->left = 0;
00362         }
00363 
00364         /* Find the isle this area is part of (used late below) */
00365         /*
00366            if ( line > 0 ) {
00367            if ( Line->left < 0 ) isle = Line->left; 
00368            } else {
00369            if ( Line->right < 0 ) isle = Line->right; 
00370            }
00371          */
00372     }
00373 
00374     /* Unset area information of centroid */
00375     /* TODO: duplicate centroids have also area information ->
00376      *        1) do not save such info
00377      *        2) find all by box and reset info */
00378     line = Area->centroid;
00379     if (line > 0) {
00380         Line = plus->Line[line];
00381         if (!Line) {
00382             G_warning(_("Dead centroid %d registered for area (bug in the vector library)"),
00383                       line);
00384         }
00385         else {
00386             Line->left = 0;
00387             if (plus->do_uplist)
00388                 dig_line_add_updated(plus, line);
00389         }
00390     }
00391 
00392     /* Find the area this area is within */
00393     /*
00394        area_out = 0;
00395        if ( isle > 0 ) { 
00396        Isle =  plus->Isle[abs(isle)];
00397        area_out = Isle->area;
00398        }
00399      */
00400 
00401     /* Reset information about area outside for isles within this area */
00402     G_debug(3, "  n_isles = %d", Area->n_isles);
00403     for (i = 0; i < Area->n_isles; i++) {
00404         Isle = plus->Isle[Area->isles[i]];
00405         if (Isle == NULL) {
00406             G_fatal_error(_("Attempt to delete area %d info from dead isle %d"),
00407                           area, Area->isles[i]);
00408         }
00409         else {
00410             /* Isle->area = area_out; */
00411             Isle->area = 0;
00412         }
00413     }
00414 
00415     /* TODO: free structures */
00416     plus->Area[area] = NULL;
00417     return 1;
00418 }
00419 
00429 int dig_area_set_box(struct Plus_head *plus, plus_t area, BOUND_BOX * Box)
00430 {
00431     P_AREA *Area;
00432 
00433     Area = plus->Area[area];
00434 
00435     Area->N = Box->N;
00436     Area->S = Box->S;
00437     Area->E = Box->E;
00438     Area->W = Box->W;
00439     Area->T = Box->T;
00440     Area->B = Box->B;
00441 
00442     return (1);
00443 }
00444 
00445 
00461 int
00462 dig_angle_next_line(struct Plus_head *plus, plus_t current_line, int side,
00463                     int type)
00464 {
00465     int i, next;
00466     int current;
00467     int line;
00468     plus_t node;
00469     P_NODE *Node;
00470     P_LINE *Line;
00471 
00472     G_debug(3, "dig__angle_next_line: line = %d, side = %d, type = %d",
00473             current_line, side, type);
00474 
00475     Line = plus->Line[abs(current_line)];
00476     if (current_line > 0)
00477         node = Line->N1;
00478     else
00479         node = Line->N2;
00480 
00481     G_debug(3, " node = %d", node);
00482 
00483     Node = plus->Node[node];
00484     G_debug(3, "  n_lines = %d", Node->n_lines);
00485     for (i = 0; i < Node->n_lines; i++) {
00486         G_debug(3, "  i = %d line = %d angle = %f", i, Node->lines[i],
00487                 Node->angles[i]);
00488     }
00489 
00490     /* first find index for that line */
00491     next = -1;
00492     for (current = 0; current < Node->n_lines; current++) {
00493         if (Node->lines[current] == current_line)
00494             next = current;
00495     }
00496     if (next == -1)
00497         return 0;               /* not found */
00498 
00499     G_debug(3, "  current position = %d", next);
00500     while (1) {
00501         if (side == GV_RIGHT) { /* go up (greater angle) */
00502             if (next == Node->n_lines - 1)
00503                 next = 0;
00504             else
00505                 next++;
00506         }
00507         else {                  /* go down (smaller angle) */
00508             if (next == 0)
00509                 next = Node->n_lines - 1;
00510             else
00511                 next--;
00512         }
00513         G_debug(3, "  next = %d line = %d angle = %f", next,
00514                 Node->lines[next], Node->angles[next]);
00515 
00516         if (Node->angles[next] == -9.) {        /* skip points and degenerated */
00517             G_debug(3, "  point/degenerated -> skip");
00518             if (Node->lines[next] == current_line)
00519                 break;          /* Yes, that may happen if input line is degenerated and isolated and this breaks loop */
00520             else
00521                 continue;
00522         }
00523 
00524         line = abs(Node->lines[next]);
00525         Line = plus->Line[line];
00526 
00527         if (Line->type & type) {        /* line found */
00528             G_debug(3, "  this one");
00529             return (Node->lines[next]);
00530         }
00531 
00532         /* input line reached, this must be last, because current_line may be correct return value (dangle) */
00533         if (Node->lines[next] == current_line)
00534             break;
00535     }
00536     G_debug(3, "  Line NOT found at node %d", (int)node);
00537     return 0;
00538 }
00539 
00554 int dig_node_angle_check(struct Plus_head *plus, plus_t line, int type)
00555 {
00556     int next, prev;
00557     float angle1, angle2;
00558     plus_t node;
00559     P_LINE *Line;
00560 
00561     G_debug(3, "dig_node_angle_check: line = %d, type = %d", line, type);
00562 
00563     Line = plus->Line[abs(line)];
00564 
00565     if (line > 0)
00566         node = Line->N1;
00567     else
00568         node = Line->N2;
00569 
00570     angle1 = dig_node_line_angle(plus, node, line);
00571 
00572     /* Next */
00573     next = dig_angle_next_line(plus, line, GV_RIGHT, type);
00574     angle2 = dig_node_line_angle(plus, node, next);
00575     if (angle1 == angle2) {
00576         G_debug(3,
00577                 "  The line to the right has the same angle: node = %d, line = %d",
00578                 node, next);
00579         return 0;
00580     }
00581 
00582     /* Previous */
00583     prev = dig_angle_next_line(plus, line, GV_LEFT, type);
00584     angle2 = dig_node_line_angle(plus, node, prev);
00585     if (angle1 == angle2) {
00586         G_debug(3,
00587                 "  The line to the left has the same angle: node = %d, line = %d",
00588                 node, next);
00589         return 0;
00590     }
00591 
00592     return 1;                   /* OK */
00593 }
00594 
00610 int dig_add_isle(struct Plus_head *plus, int n_lines, plus_t * lines)
00611 {
00612     register int i;
00613     register int isle, line;
00614     P_ISLE *Isle;
00615     P_LINE *Line;
00616     BOUND_BOX box, abox;
00617 
00618     G_debug(3, "dig_add_isle():");
00619     /* First look if we have space in array of pointers to isles
00620      *  and reallocate if necessary */
00621     if (plus->n_isles >= plus->alloc_isles) {   /* array is full */
00622         if (dig_alloc_isles(plus, 1000) == -1)
00623             return -1;
00624     }
00625 
00626     /* allocate isle structure */
00627     isle = plus->n_isles + 1;
00628     Isle = dig_alloc_isle();
00629     if (Isle == NULL)
00630         return -1;
00631 
00632     if ((dig_isle_alloc_line(Isle, n_lines)) == -1)
00633         return -1;
00634 
00635     Isle->area = 0;
00636 
00637     Isle->N = 0;
00638     Isle->S = 0;
00639     Isle->E = 0;
00640     Isle->W = 0;
00641 
00642     for (i = 0; i < n_lines; i++) {
00643         line = lines[i];
00644         G_debug(3, " i = %d line = %d", i, line);
00645         Isle->lines[i] = line;
00646         Line = plus->Line[abs(line)];
00647         if (plus->do_uplist)
00648             dig_line_add_updated(plus, abs(line));
00649         if (line < 0) {         /* revers direction -> isle on left */
00650             if (Line->left != 0) {
00651                 G_warning(_("Line %d already has area/isle %d to left"), line,
00652                           Line->left);
00653                 return -1;
00654             }
00655             Line->left = -isle;
00656         }
00657         else {
00658             if (Line->right != 0) {
00659                 G_warning(_("Line %d already has area/isle %d to left"), line,
00660                           Line->right);
00661                 return -1;
00662             }
00663 
00664             Line->right = -isle;
00665         }
00666         dig_line_get_box(plus, abs(line), &box);
00667         if (i == 0)
00668             dig_box_copy(&abox, &box);
00669         else
00670             dig_box_extend(&abox, &box);
00671     }
00672 
00673     Isle->n_lines = n_lines;
00674 
00675     plus->Isle[isle] = Isle;
00676 
00677     dig_isle_set_box(plus, isle, &abox);
00678 
00679     dig_spidx_add_isle(plus, isle, &abox);
00680 
00681     plus->n_isles++;
00682 
00683     return (isle);
00684 }
00685 
00686 
00696 int dig_isle_set_box(struct Plus_head *plus, plus_t isle, BOUND_BOX * Box)
00697 {
00698     P_ISLE *Isle;
00699 
00700     Isle = plus->Isle[isle];
00701 
00702     Isle->N = Box->N;
00703     Isle->S = Box->S;
00704     Isle->E = Box->E;
00705     Isle->W = Box->W;
00706     Isle->T = Box->T;
00707     Isle->B = Box->B;
00708 
00709     return (1);
00710 }
00711 
00722 int dig_del_isle(struct Plus_head *plus, int isle)
00723 {
00724     int i, line;
00725     P_LINE *Line;
00726     P_ISLE *Isle;
00727 
00728     G_debug(3, "dig_del_isle() isle =  %d", isle);
00729     Isle = plus->Isle[isle];
00730 
00731     dig_spidx_del_isle(plus, isle);
00732 
00733     /* Set area for all lines to 0 */
00734     for (i = 0; i < Isle->n_lines; i++) {
00735         line = Isle->lines[i];  /* >0 = clockwise -> right, <0 = counterclockwise ->left */
00736         Line = plus->Line[abs(line)];
00737         if (plus->do_uplist)
00738             dig_line_add_updated(plus, abs(line));
00739         if (line > 0)
00740             Line->right = 0;
00741         else
00742             Line->left = 0;
00743     }
00744 
00745     /* Delete reference from area it is within */
00746     G_debug(3, "  area outside isle = %d", Isle->area);
00747     if (Isle->area > 0) {
00748         if (plus->Area[Isle->area] == NULL) {
00749             G_fatal_error(_("Attempt to delete isle %d info from dead area %d"),
00750                           isle, Isle->area);
00751         }
00752         else {
00753             dig_area_del_isle(plus, Isle->area, isle);
00754         }
00755     }
00756 
00757     /* TODO: free structures */
00758 
00759     plus->Isle[isle] = NULL;
00760 
00761     return 1;
00762 }

Generated on Sat Oct 24 03:25:20 2009 for GRASS Programmer's Manual by  doxygen 1.6.1