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