00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #include <stdlib.h>
00021 #include <grass/Vect.h>
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049 int
00050 dig_build_area_with_line ( struct Plus_head *plus,
00051 plus_t first_line,
00052 int side,
00053 plus_t **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;
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
00067
00068 Line = plus->Line[first_line];
00069 node = Line->N1;
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) {
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;
00084 }
00085 array[0] = first_line;
00086 prev_line = -first_line;
00087
00088
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);
00096
00097
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
00105 if (first_line == next_line) {
00106
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
00118
00119 if (prev_line == next_line)
00120 {
00121 G_debug (3, "Dead_end:");
00122 return (0);
00123 }
00124
00125
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);
00131 }
00132
00133
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
00150
00151
00152
00153
00154
00155
00156
00157
00158 int
00159 dig_add_area (struct Plus_head *plus,
00160 int n_lines,
00161 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
00171
00172 if ( plus->n_areas >= plus->alloc_areas ) {
00173 if ( dig_alloc_areas(plus,1000) == -1 )
00174 return -1;
00175 }
00176
00177
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) {
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
00226
00227
00228
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 ) {
00243 G_debug (3, "isle already registered in area" );
00244 return 0;
00245 }
00246 }
00247
00248 if ( Area->alloc_isles <= Area->n_isles )
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
00259
00260
00261
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
00293
00294
00295
00296
00297
00298
00299
00300
00301
00302 int
00303 dig_del_area (struct Plus_head *plus, int area ) {
00304 int i, line;
00305
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
00321
00322 for (i = 0; i < Area->n_lines; i++) {
00323 line = Area->lines[i];
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
00335
00336
00337
00338
00339
00340
00341
00342 }
00343
00344
00345
00346
00347
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
00360
00361
00362
00363
00364
00365
00366
00367
00368
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
00376 Isle->area = 0;
00377 }
00378 }
00379
00380
00381 plus->Area[area] = NULL;
00382 return 1;
00383 }
00384
00385
00386
00387
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
00408
00409
00410
00411
00412
00413
00414
00415 int
00416 dig_angle_next_line (
00417 struct Plus_head *plus,
00418 plus_t current_line,
00419
00420 int side,
00421 int type)
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
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;
00451
00452 G_debug (3, " current position = %d", next );
00453 while (1) {
00454 if (side == GV_RIGHT) {
00455 if (next == Node->n_lines - 1)
00456 next = 0;
00457 else
00458 next++;
00459 } else {
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. ) {
00468 G_debug (3, " point/degenerated -> skip" );
00469 if ( Node->lines[next] == current_line )
00470 break;
00471 else
00472 continue;
00473 }
00474
00475 line = abs ( Node->lines[next] );
00476 Line = plus->Line[line];
00477
00478 if ( Line->type & type ) {
00479 G_debug (3, " this one" );
00480 return ( Node->lines[next] );
00481 }
00482
00483
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
00492
00493
00494
00495
00496
00497
00498
00499
00500 int
00501 dig_node_angle_check (
00502 struct Plus_head *plus,
00503 plus_t line,
00504
00505 int type)
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
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
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;
00538 }
00539
00540
00541
00542
00543
00544
00545
00546
00547
00548
00549
00550 int
00551 dig_add_isle (struct Plus_head *plus,
00552 int n_lines,
00553 plus_t *lines )
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
00563
00564 if ( plus->n_isles >= plus->alloc_isles ) {
00565 if ( dig_alloc_isles(plus,1000) == -1 )
00566 return -1;
00567 }
00568
00569
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) {
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
00625
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
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
00657 for (i = 0; i < Isle->n_lines; i++) {
00658 line = Isle->lines[i];
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
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
00675
00676 plus->Isle[isle] = NULL;
00677
00678 return 1;
00679 }
00680