00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #include "stdafx.h"
00021
00022 #include <stdio.h>
00023 #include <iostream>
00024
00025 #include "gul_types.h"
00026 #include "gul_vector.h"
00027 #include "gul_io.h"
00028 #include "guge_normalize.h"
00029 #include "guar_exact.h"
00030 #include "gugr_basics.h"
00031 #include "gugr_planesweep.h"
00032 #include "guma_sorting.h"
00033 #include "gugr_contour.h"
00034 #include "gul_std.h"
00035 #include "gugr_io.h"
00036
00037 namespace gugr {
00038
00039 using gul::Ptr;
00040 using gul::point;
00041 using gul::point2;
00042 using gul::Swap;
00043 using guar::rational;
00044 using guar::ULong;
00045 using gul::dump_vector;
00046 using guma::heapsort;
00047 using guma::BinarySearch;
00048 using gul::ListNodeInfo;
00049 using std::cout;
00050
00051 void AppendContour( polyline *c, int keyleft, int keyright,
00052 List< ListNode<segment> >& segs )
00053 {
00054 int i;
00055 ListNode<segment> *sn;
00056 segment *s;
00057 rational x1,x2,y1,y2;
00058 bool swap;
00059
00060
00061 for( i = 0; i < c->nVerts; i++ )
00062 {
00063 sn = new ListNode<segment>;
00064 segs.Append( sn );
00065
00066 s = &sn->el;
00067
00068 s->l = c->lines[i];
00069 s->f[0].set_i(keyleft);
00070 s->f[1].set_i(keyright);
00071 s->m = 1;
00072
00073 x1 = c->verts[i].x;
00074 y1 = c->verts[i].y;
00075 if( i+1 == c->nVerts )
00076 {
00077 x2 = c->verts[0].x;
00078 y2 = c->verts[0].y;
00079 }
00080 else
00081 {
00082 x2 = c->verts[i+1].x;
00083 y2 = c->verts[i+1].y;
00084 }
00085
00086
00087
00088 if( c->lines[i].IsVertical() )
00089 swap = (compare( y1, y2 ) > 0);
00090 else
00091 swap = (compare( x1, x2 ) > 0);
00092
00093 if( swap )
00094 {
00095 Swap(x1,x2);
00096 Swap(y1,y2);
00097 Swap(s->f[0],s->f[1]);
00098 }
00099
00100 s->B.x = x1;
00101 s->B.y = y1;
00102 s->E.x = x2;
00103 s->E.y = y2;
00104 }
00105 }
00106
00107 template< class EP >
00108 void AppendContourFNT( polyline *c, Ptr<EP>& F, Ptr<EP>& N, Ptr<EP>& T,
00109 int keyleft, int keyright, List< ListNode<segment> >& segs )
00110 {
00111 int i;
00112 ListNode<segment> *sn;
00113 segment *s;
00114 rational x1,x2,y1,y2;
00115 bool swap;
00116 seg_point_info<EP> *spi;
00117
00118
00119 for( i = 0; i < c->nVerts; i++ )
00120 {
00121 sn = new ListNode<segment>;
00122 segs.Append( sn );
00123
00124 s = &sn->el;
00125
00126 s->l = c->lines[i];
00127 s->f[0].set_i(keyleft);
00128 s->f[1].set_i(keyright);
00129 spi = new seg_point_info<EP>;
00130 spi->f = &F[i];
00131 spi->n = &N[i];
00132 spi->t = &T[i];
00133 s->reserved[0] = spi;
00134
00135 s->m = 1;
00136
00137 x1 = c->verts[i].x;
00138 y1 = c->verts[i].y;
00139 if( i+1 == c->nVerts )
00140 {
00141 x2 = c->verts[0].x;
00142 y2 = c->verts[0].y;
00143 spi = new seg_point_info<EP>;
00144 spi->f = &F[0];
00145 spi->n = &N[0];
00146 spi->t = &T[0];
00147 s->reserved[1] = spi;
00148 }
00149 else
00150 {
00151 x2 = c->verts[i+1].x;
00152 y2 = c->verts[i+1].y;
00153 spi = new seg_point_info<EP>;
00154 spi->f = &F[i+1];
00155 spi->n = &N[i+1];
00156 spi->t = &T[i+1];
00157 s->reserved[1] = spi;
00158 }
00159
00160
00161
00162 if( c->lines[i].IsVertical() )
00163 swap = (compare( y1, y2 ) > 0);
00164 else
00165 swap = (compare( x1, x2 ) > 0);
00166
00167 if( swap )
00168 {
00169 Swap(x1,x2);
00170 Swap(y1,y2);
00171 Swap(s->f[0],s->f[1]);
00172 Swap(s->reserved[0],s->reserved[1]);
00173 }
00174
00175 s->B.x = x1;
00176 s->B.y = y1;
00177 s->E.x = x2;
00178 s->E.y = y2;
00179 }
00180 }
00181
00182 template void AppendContourFNT(
00183 polyline *c, Ptr< point<float> >& F, Ptr< point<float> >& N,
00184 Ptr< point<float> >& T,
00185 int keyleft, int keyright, List< ListNode<segment> >& segs );
00186 template void AppendContourFNT(
00187 polyline *c, Ptr< point<double> >& F, Ptr< point<double> >& N,
00188 Ptr< point<double> >& T,
00189 int keyleft, int keyright, List< ListNode<segment> >& segs );
00190
00191
00192
00193 void LeftSideContour( graph_edge *e, graph_edge_list& E, contour_node *cn )
00194 {
00195 graph_edge **TE;
00196 graph_vertex *v0,*v;
00197 List< ListNode<graph_vertex *> > vlist;
00198 List< ListNode<graph_edge *> > elist;
00199 ListNode<graph_vertex *> *vn,*vn_next;
00200 ListNode<graph_edge *> *en,*en_next;
00201 int curside,n,side,nVerts,i;
00202 RefMap<void> *owners,*eowners;
00203 RefMap<void>::Node eowner,parent,owner;
00204 Ptr<vertex> verts;
00205 Ptr<line> lines;
00206 segment *seg;
00207
00208 TE = (graph_edge **)alloca(sizeof(graph_edge *)*E.nElems);
00209
00210 v0 = e->v[0];
00211 vn = new ListNode<graph_vertex *>(v0);
00212 vlist.Append(vn);
00213 en = new ListNode<graph_edge *>(e);
00214 elist.Append(en);
00215
00216 v = e->v[1];
00217 vn = new ListNode<graph_vertex *>(v);
00218 vlist.Append(vn);
00219
00220 curside = 0;
00221 owners = (RefMap<void> *)e->f[0].p;
00222 e->f[0].p = 0;
00223
00224
00225 seg = (segment *)e->reserved[2].p;
00226 if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
00227 seg->f[1].p = cn;
00228 else
00229 seg->f[0].p = cn;
00230
00231 for(;;)
00232 {
00233 n = EdgeCycle( e, v, TE );
00234 e = TE[n-1];
00235
00236
00237
00238
00239
00240
00241 seg = (segment *)e->reserved[2].p;
00242
00243 if( e->v[0] == v )
00244 {
00245 curside = 0;
00246 v = e->v[1];
00247
00248 if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
00249 seg->f[1].p = cn;
00250 else
00251 seg->f[0].p = cn;
00252 }
00253 else
00254 {
00255 curside = 1;
00256 v = e->v[0];
00257
00258 if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
00259 seg->f[0].p = cn;
00260 else
00261 seg->f[1].p = cn;
00262 }
00263
00264
00265
00266 eowners = (RefMap<void> *)e->f[curside].p;
00267 eowner = eowners->First();
00268 while( !eowner.IsEmpty() )
00269 {
00270 side = owners->SearchNode( eowner.key(), compare_pointer_to_pointer,
00271 &parent );
00272 if( side != 0 )
00273 {
00274 owner = owners->NewNode( eowner.key() );
00275 owners->InsertNode( owner, parent, side );
00276 }
00277 eowner = eowners->Successor( eowner );
00278 }
00279 delete eowners;
00280 e->f[curside].p = 0;
00281
00282 en = new ListNode<graph_edge *>(e);
00283 elist.Append(en);
00284
00285 if( v != v0 )
00286 {
00287 vn = new ListNode<graph_vertex *>(v);
00288 vlist.Append(vn);
00289 }
00290 else
00291 break;
00292 }
00293
00294
00295
00296 nVerts = vlist.nElems;
00297 verts.reserve_pool(nVerts);
00298 lines.reserve_pool(nVerts);
00299
00300 vn = vlist.First();
00301 vlist.ReleaseElems();
00302 en = elist.First();
00303 elist.ReleaseElems();
00304
00305 for( i = nVerts-1; i >= 0; i-- )
00306 {
00307 verts[i] = vn->el->v;
00308 vn_next = vn->next;
00309 delete vn;
00310 vn = vn_next;
00311
00312 lines[i] = en->el->l;
00313 en_next = en->next;
00314 delete en;
00315 en = en_next;
00316 }
00317
00318
00319 cn->nOwners = owners->ConvertToArray( &cn->owners );
00320 delete owners;
00321
00322 cn->nVerts = nVerts;
00323 cn->verts = verts;
00324 cn->lines = lines;
00325 return;
00326 }
00327
00328 void RightSideContour( graph_edge *e, graph_edge_list& E, contour_node *cn )
00329 {
00330 graph_edge **TE;
00331 graph_vertex *v0,*v;
00332 List< ListNode<graph_vertex *> > vlist;
00333 List< ListNode<graph_edge *> > elist;
00334 ListNode<graph_vertex *> *vn,*vn_next;
00335 ListNode<graph_edge *> *en,*en_next;
00336 int curside,n,side,nVerts,i;
00337 RefMap<void> *owners,*eowners;
00338 RefMap<void>::Node eowner,parent,owner;
00339 Ptr<vertex> verts;
00340 Ptr<line> lines;
00341 segment *seg;
00342
00343 TE = (graph_edge **)alloca(sizeof(graph_edge *)*E.nElems);
00344
00345 v0 = e->v[0];
00346 vn = new ListNode<graph_vertex *>(v0);
00347 vlist.Append(vn);
00348 en = new ListNode<graph_edge *>(e);
00349 elist.Append(en);
00350
00351 v = e->v[1];
00352 vn = new ListNode<graph_vertex *>(v);
00353 vlist.Append(vn);
00354
00355 curside = 1;
00356 owners = (RefMap<void> *)e->f[1].p;
00357 e->f[1].p = 0;
00358
00359
00360 seg = (segment *)e->reserved[2].p;
00361 if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
00362 seg->f[0].p = cn;
00363 else
00364 seg->f[1].p = cn;
00365
00366 for(;;)
00367 {
00368 n = EdgeCycle( e, v, TE );
00369 e = TE[1];
00370
00371
00372
00373
00374
00375
00376 seg = (segment *)e->reserved[2].p;
00377
00378 if( e->v[0] == v )
00379 {
00380 curside = 1;
00381 v = e->v[1];
00382
00383 if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
00384 seg->f[0].p = cn;
00385 else
00386 seg->f[1].p = cn;
00387 }
00388 else
00389 {
00390 curside = 0;
00391 v = e->v[0];
00392
00393 if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
00394 seg->f[1].p = cn;
00395 else
00396 seg->f[0].p = cn;
00397 }
00398
00399
00400 eowners = (RefMap<void> *)e->f[curside].p;
00401 eowner = eowners->First();
00402 while( !eowner.IsEmpty() )
00403 {
00404 side = owners->SearchNode( eowner.key(), compare_pointer_to_pointer,
00405 &parent );
00406 if( side != 0 )
00407 {
00408 owner = owners->NewNode( eowner.key() );
00409 owners->InsertNode( owner, parent, side );
00410 }
00411 eowner = eowners->Successor( eowner );
00412 }
00413 delete eowners;
00414 e->f[curside].p = 0;
00415
00416 en = new ListNode<graph_edge *>(e);
00417 elist.Append(en);
00418
00419 if( v != v0 )
00420 {
00421 vn = new ListNode<graph_vertex *>(v);
00422 vlist.Append(vn);
00423 }
00424 else
00425 break;
00426 }
00427
00428
00429
00430 nVerts = vlist.nElems;
00431 verts.reserve_pool(nVerts);
00432 lines.reserve_pool(nVerts);
00433
00434 vn = vlist.First();
00435 vlist.ReleaseElems();
00436 en = elist.First();
00437 elist.ReleaseElems();
00438
00439 for( i = nVerts-1; i >= 0; i-- )
00440 {
00441 verts[i] = vn->el->v;
00442 vn_next = vn->next;
00443 delete vn;
00444 vn = vn_next;
00445
00446 lines[i] = en->el->l;
00447 en_next = en->next;
00448 delete en;
00449 en = en_next;
00450 }
00451
00452
00453
00454 cn->nOwners = owners->ConvertToArray( &cn->owners );
00455 delete owners;
00456
00457 cn->nVerts = nVerts;
00458 cn->verts = verts;
00459 cn->lines = lines;
00460 return;
00461 }
00462
00463
00464
00465
00466
00467
00468
00469
00470
00471
00472
00473
00474
00475
00476
00477
00478
00479
00480
00481
00482
00483
00484
00485
00486
00487
00488
00489 void FindContours(
00490 graph_edge_list& E, graph_vertex_list& V,
00491 const rational& far_maxx, const rational& far_maxy,
00492 List< ListNode<segment> >& outsegs,
00493 List<contour_node>& contours )
00494 {
00495 graph_edge *e,*laste;
00496 ListNode<segment> *sn;
00497 contour_node *cn;
00498 ListNode<segment> *hn;
00499 segment *h,*lastseg;
00500
00501 outsegs.DeleteElems();
00502
00503
00504
00505
00506 e = E.First();
00507 while( e )
00508 {
00509 sn = new ListNode<segment>;
00510 outsegs.Append(sn);
00511
00512
00513
00514 if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
00515 {
00516 sn->el.B = e->v[1]->v.v();
00517 sn->el.E = e->v[0]->v.v();
00518 }
00519 else
00520 {
00521 sn->el.B = e->v[0]->v.v();
00522 sn->el.E = e->v[1]->v.v();
00523 }
00524 sn->el.l = e->l;
00525 sn->el.m = e->reserved[0].i;
00526
00527 e->reserved[2].p = &sn->el;
00528 e = e->next;
00529 }
00530
00531
00532
00533 e = E.First();
00534 laste = 0;
00535 lastseg = 0;
00536
00537 while( e )
00538 {
00539
00540
00541
00542
00543 if( e->f[0].p )
00544 {
00545 cn = new contour_node(0);
00546 contours.Append(cn);
00547 cn->seg = (segment *)e->reserved[2].p;
00548
00549 LeftSideContour( e, E, cn );
00550
00551 if( e != laste )
00552 {
00553
00554
00555
00556 hn = new ListNode<segment>;
00557 outsegs.Append(hn);
00558 h = &hn->el;
00559
00560 if( !e->l.IsHorizontal() )
00561 {
00562 h->E.y =
00563 (e->v[0]->v.v().y + e->v[1]->v.v().y)/rational(ULong(2));
00564 h->E.x = far_maxx;
00565
00566 intersect_horiz( h->E.y, e->l, h->B );
00567
00568 h->f[0].p = h->f[1].p = 0;
00569 h->l = line( h->E, rational(ULong(1)), rational(ULong(0)) );
00570 }
00571 else
00572 {
00573 h->E.x =
00574 (e->v[0]->v.v().x + e->v[1]->v.v().x)/rational(ULong(2));
00575 h->E.y = far_maxy;
00576
00577 intersect_vert( h->E.x, e->l, h->B );
00578
00579 h->f[0].p = h->f[1].p = 0;
00580
00581 h->l = line( h->E, rational(ULong(0)), rational(ULong(1)) );
00582 }
00583
00584 cn->hseg = h;
00585 cn->hseg_firstref = true;
00586
00587
00588
00589
00590
00591 laste = e;
00592 lastseg = h;
00593 }
00594 else
00595 {
00596 cn->hseg = lastseg;
00597 cn->hseg_firstref = false;
00598
00599
00600
00601
00602 }
00603 }
00604
00605 if( e->f[1].p )
00606 {
00607 cn = new contour_node(0);
00608 contours.Append(cn);
00609 cn->seg = (segment *)e->reserved[2].p;
00610
00611 RightSideContour( e, E, cn );
00612
00613 if( e != laste )
00614 {
00615
00616
00617
00618 hn = new ListNode<segment>;
00619 outsegs.Append(hn);
00620 h = &hn->el;
00621
00622 if( !e->l.IsHorizontal() )
00623 {
00624 h->E.y =
00625 (e->v[0]->v.v().y + e->v[1]->v.v().y)/rational(ULong(2));
00626 h->E.x = far_maxx;
00627
00628 intersect_horiz( h->E.y, e->l, h->B );
00629
00630 h->f[0].p = h->f[1].p = 0;
00631 h->l = line( h->E, rational(ULong(1)), rational(ULong(0)) );
00632 }
00633 else
00634 {
00635 h->E.x =
00636 (e->v[0]->v.v().x + e->v[1]->v.v().x)/rational(ULong(2));
00637 h->E.y = far_maxy;
00638
00639 intersect_vert( h->E.x, e->l, h->B );
00640
00641 h->f[0].p = h->f[1].p = 0;
00642
00643 h->l = line( h->E, rational(ULong(0)), rational(ULong(1)) );
00644 }
00645 cn->hseg = h;
00646 cn->hseg_firstref = true;
00647
00648
00649
00650
00651
00652 laste = e;
00653 lastseg = h;
00654 }
00655 else
00656 {
00657 cn->hseg = lastseg;
00658 cn->hseg_firstref = false;
00659
00660
00661
00662
00663 }
00664 }
00665
00666 e = e->next;
00667 }
00668 }
00669
00670
00671
00672
00673
00674
00675
00676
00677
00678
00679
00680
00681
00682
00683
00684
00685
00686
00687
00688 void RemoveUnnecessaryEdges(
00689 graph_edge_list& E, graph_vertex_list& V,
00690 const rational& far_maxx, const rational& far_maxy,
00691 int key_inside, int key_outside,
00692 List< ListNode<segment> >& outsegs )
00693 {
00694 gugr::graph_edge_list E2;
00695 gugr::graph_vertex_list V2;
00696 graph_edge *e,*e_next;
00697 ListNode<segment> *sn;
00698 List<contour_node> contours;
00699 contour_node *cn,*C0,*C1;
00700 segment *seg;
00701 int m,i,n,nEdges,side;
00702 bool end;
00703 Ptr<void *> edges;
00704 graph_edge **TE;
00705 ListNode<graph_edge *> *en;
00706 RefMap<void> *M;
00707 RefMap<void>::Node parent;
00708 int left,right,isolated;
00709 List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > > *L;
00710 ListNode< ListNodeInfo< ListNode<graph_edge *> > > *bptr, *bptr_next;
00711
00712
00713 FindContours( E, V, far_maxx, far_maxy, outsegs, contours );
00714
00715
00716
00717
00718
00719
00720
00721
00722
00723
00724
00725 IntersectSegments( outsegs, &E2, &V2, false );
00726
00727
00728
00729
00730
00731
00732
00733
00734
00735
00736
00737
00738
00739 TE = (graph_edge **)alloca(sizeof(graph_edge *)*E2.nElems);
00740 edges.reserve_pool(E2.nElems);
00741
00742 for( cn = contours.First(); cn != 0; cn = cn->next )
00743 {
00744 m = 0;
00745
00746 en = cn->hseg->e.First();
00747 if( en )
00748 {
00749 e = en->el;
00750
00751 if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
00752 end = 1;
00753 else
00754 end = 0;
00755 }
00756
00757 while( en )
00758 {
00759 en = en->next;
00760 if( !en ) break;
00761
00762 n = EdgeCycle( e, e->v[end], TE );
00763
00764 for( i = 1; TE[i] != en->el; i++ )
00765 {
00766 m += (int)TE[i]->reserved[0].i;
00767 }
00768
00769 e = en->el;
00770 }
00771
00772
00773
00774
00775 nEdges = cn->seg->e.nElems;
00776 for( en = cn->seg->e.First(), i=0; en != 0; en = en->next, i++ )
00777 edges[i] = en->el;
00778 heapsort( nEdges, edges );
00779
00780 n = EdgeCycle( e, e->v[end], TE );
00781
00782 for( i = 1; ; i++ )
00783 {
00784 if( BinarySearch( (void *)TE[i], nEdges, edges ) >= 0 )
00785 break;
00786
00787 m += (int)TE[i]->reserved[0].i;
00788 }
00789
00790
00791
00792
00793 if( TE[i]->v[0] == e->v[end] )
00794 M = (RefMap<void> *)TE[i]->f[0].p;
00795 else
00796 M = (RefMap<void> *)TE[i]->f[1].p;
00797
00798 side = M->SearchNode( (void *)cn, compare_pointer_to_pointer, &parent );
00799 if( side == 0 )
00800 {
00801 m += (int)TE[i]->reserved[0].i;
00802 }
00803
00804 cn->hole = ((m & 1) == 0);
00805 }
00806
00807
00808 ISDeleteOwnerMaps(E2);
00809 E2.DeleteElems();
00810 V2.DeleteElems();
00811
00812
00813
00814
00815
00816
00817
00818
00819
00820
00821
00822
00823
00824
00825
00826
00827
00828
00829 e = E.First();
00830 while( e )
00831 {
00832 seg = (segment *)e->reserved[2].p;
00833 C0 = (contour_node *)seg->f[0].p;
00834 C1 = (contour_node *)seg->f[1].p;
00835
00836 if( C0->hole == C1->hole )
00837 {
00838
00839
00840
00841
00842
00843 gul::Assert<InternalError>( ndebug ||
00844 (outsegs.First() == (ListNode<segment> *)&outsegs.First()->el) );
00845
00846
00847
00848
00849
00850
00851 sn = (ListNode<segment> *)seg;
00852 outsegs.Remove( sn );
00853 delete sn;
00854
00855 isolated = DisconnectEdge(e,E.nElems);
00856 if( (isolated & 1) )
00857 {
00858 V.Remove(e->v[0]);
00859 delete e->v[0];
00860 }
00861 if( (isolated & 2) )
00862 {
00863 V.Remove(e->v[1]);
00864 delete e->v[1];
00865 }
00866
00867
00868 if( e->reserved[1].p )
00869 {
00870 L = (List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > > *)
00871 e->reserved[1].p;
00872 bptr = L->First();
00873 L->ReleaseElems();
00874 delete L;
00875
00876 while( bptr )
00877 {
00878 bptr->el.m_L->Remove( bptr->el.m_n );
00879 bptr_next = bptr->next;
00880 delete bptr;
00881 bptr = bptr_next;
00882 }
00883 }
00884
00885 e_next = e->next;
00886 E.Remove(e);
00887 delete e;
00888 e = e_next;
00889 }
00890 else
00891 {
00892
00893
00894
00895 if( C0->hole )
00896 {
00897 left = key_outside;
00898 right = key_inside;
00899 }
00900 else
00901 {
00902 left = key_inside;
00903 right = key_outside;
00904 }
00905
00906 if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
00907 {
00908 e->f[0].set_i(right);
00909 e->f[1].set_i(left);
00910 }
00911 else
00912 {
00913 e->f[0].set_i(left);
00914 e->f[1].set_i(right);
00915 }
00916
00917
00918
00919
00920
00921
00922 seg->f[0].set_i(left);
00923 seg->f[1].set_i(right);
00924 seg->e.DeleteElems();
00925
00926 e = e->next;
00927 }
00928 }
00929
00930
00931
00932 for( cn = contours.First(); cn != 0; cn = cn->next )
00933 {
00934 if( cn->hseg_firstref )
00935 {
00936 sn = (ListNode<segment> *)cn->hseg;
00937 outsegs.Remove( sn );
00938 delete sn;
00939 }
00940 }
00941
00942
00943
00944
00945
00946
00947
00948
00949
00950
00951
00952
00953
00954 contours.DeleteElems();
00955 }
00956
00957
00958
00959
00960
00961 GULAPI void OddEvenRule(
00962 List< ListNode<polyline> >& inC,
00963 const rational& far_maxx, const rational& far_maxy,
00964 int key_inside, int key_outside,
00965 graph_edge_list& E, graph_vertex_list& V,
00966 List< ListNode<segment> >& outsegs )
00967 {
00968 ListNode<polyline> *inc;
00969 List< ListNode<segment> > segs;
00970
00971 E.DeleteElems();
00972 V.DeleteElems();
00973 outsegs.DeleteElems();
00974
00975 inc = inC.First();
00976 while( inc )
00977 {
00978 AppendContour( &inc->el, 1, 2, segs );
00979 inc = inc->next;
00980 }
00981
00982
00983
00984
00985
00986
00987
00988
00989
00990 IntersectSegments( segs, &E, &V, false );
00991
00992
00993
00994
00995
00996
00997
00998
00999
01000
01001
01002 segs.DeleteElems();
01003
01004 RemoveUnnecessaryEdges( E, V, far_maxx, far_maxy, key_inside, key_outside,
01005 outsegs );
01006 }
01007
01008
01009 }
01010