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