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 <iostream>
00023
00024 #include "gul_types.h"
00025 #include "guar_exact.h"
00026 #include "gugr_basics.h"
00027 #include "gugr_planesweep.h"
00028 #include "gugr_contour.h"
00029 #include "guma_sorting.h"
00030 #include "guge_normalize.h"
00031 #include "gul_io.h"
00032 #include "gul_std.h"
00033 #include "gugr_io.h"
00034
00035 #include "gugr_bool.h"
00036
00037 namespace gugr {
00038
00039 using guma::heapsort;
00040 using guma::BinarySearch;
00041 using guge::CalcBoundingBoxE;
00042 using guge::UpdateBoundingBoxE;
00043 using gul::dump_vector;
00044 using std::cout;
00045
00046 void CT_DoAboveEdge(
00047 graph_edge *e,
00048 graph_vertex *v,
00049 contour_node **pCA,
00050 contour_node **pCB )
00051 {
00052 RefMap<void> *Mout,*Min,*M;
00053 RefMap<void>::Node mn;
00054 contour_node *CA,*CB,*C,*Cout,*Cin;
00055
00056 CA = *pCA;
00057 CB = *pCB;
00058
00059 if( e->v[0] == v )
00060 {
00061 Mout = (RefMap<void> *)e->f[1].p;
00062 Min = (RefMap<void> *)e->f[0].p;
00063 }
00064 else
00065 {
00066 Mout = (RefMap<void> *)e->f[0].p;
00067 Min = (RefMap<void> *)e->f[1].p;
00068 }
00069
00070 Cout = Cin = 0;
00071
00072 M = Mout;
00073 mn = M->First();
00074 while( !mn.IsEmpty() )
00075 {
00076 if( mn.key() ) { Cout = (contour_node *)mn.key(); break; }
00077 mn = M->Successor( mn );
00078 }
00079
00080 M = Min;
00081 mn = M->First();
00082 while( !mn.IsEmpty() )
00083 {
00084 if( mn.key() ) { Cin = (contour_node *)mn.key(); break; }
00085 mn = M->Successor( mn );
00086 }
00087
00088 C = Cout;
00089 if( !C ) return;
00090
00091 if( C != CA )
00092 {
00093 CA->Insert( C );
00094 CA = C;
00095 }
00096 else
00097 CA = CA->parent;
00098
00099 C = Cin;
00100 if( C != CA )
00101 {
00102 CA->Insert( C );
00103 CA = C;
00104 }
00105 else
00106 CA = CA->parent;
00107
00108 *pCA = CA;
00109 *pCB = CB;
00110 }
00111
00112 void CT_DoBelowEdge(
00113 graph_edge *e,
00114 graph_vertex *v,
00115 contour_node **pCA,
00116 contour_node **pCB )
00117 {
00118 RefMap<void> *Mout,*Min,*M;
00119 RefMap<void>::Node mn;
00120 contour_node *CA,*CB,*C,*Cout,*Cin;
00121
00122 CA = *pCA;
00123 CB = *pCB;
00124
00125 if( e->v[0] == v )
00126 {
00127 Mout = (RefMap<void> *)e->f[0].p;
00128 Min = (RefMap<void> *)e->f[1].p;
00129 }
00130 else
00131 {
00132 Mout = (RefMap<void> *)e->f[1].p;
00133 Min = (RefMap<void> *)e->f[0].p;
00134 }
00135
00136 Cout = Cin = 0;
00137
00138 M = Mout;
00139 mn = M->First();
00140 while( !mn.IsEmpty() )
00141 {
00142 if( mn.key() ) { Cout = (contour_node *)mn.key(); break; }
00143 mn = M->Successor( mn );
00144 }
00145
00146 M = Min;
00147 mn = M->First();
00148 while( !mn.IsEmpty() )
00149 {
00150 if( mn.key() ) { Cin = (contour_node *)mn.key(); break; }
00151 mn = M->Successor( mn );
00152 }
00153
00154 C = Cout;
00155 if( !C ) return;
00156
00157 if( C != CB )
00158 {
00159 CB->Insert( C );
00160 CB = C;
00161 }
00162 else
00163 CB = CB->parent;
00164
00165 C = Cin;
00166 if( C != CB )
00167 {
00168 CB->Insert( C );
00169 CB = C;
00170 }
00171 else
00172 CB = CB->parent;
00173
00174 *pCA = CA;
00175 *pCB = CB;
00176 }
00177
00178 void ContainmentTree(
00179 List< ListNode<segment> >& insegs,
00180 const rational& far_maxx, const rational& far_maxy,
00181 gul::List<contour_node>& contours, contour_node& universe )
00182 {
00183 graph_edge_list E;
00184 graph_vertex_list V;
00185 List< ListNode<segment> > segs;
00186 contour_node *cn;
00187 graph_edge *e;
00188 int end,side,n,i;
00189 graph_edge **TE;
00190 ListNode<graph_edge *> *en;
00191 contour_node *CA,*CB;
00192 RefMap<void>::Node mn;
00193 Ptr<void *> edges;
00194 int nEdges;
00195 List<ListNode<gul::polyline<point2<rational> > > > testC;
00196
00197 IntersectSegments( insegs, &E, &V, false );
00198
00199
00200
00201 FindContours(E,V,far_maxx,far_maxy,segs,contours);
00202
00203
00204
00205
00206 E.DeleteElems();
00207 V.DeleteElems();
00208
00209
00210
00211 IntersectSegments( segs, &E, &V, false );
00212
00213
00214
00215 TE = (graph_edge **)alloca(sizeof(graph_edge *)*E.nElems);
00216 edges.reserve_pool(E.nElems);
00217
00218 for( cn = contours.First(); cn != 0; cn = cn->next )
00219 {
00220 CA = &universe;
00221 CB = &universe;
00222
00223 if( !cn->hseg ) continue;
00224
00225
00226
00227 en = cn->hseg->e.First();
00228 if( en )
00229 {
00230 e = en->el;
00231
00232 if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
00233 end = 1;
00234 else
00235 end = 0;
00236 side = !end;
00237 }
00238
00239 while( en )
00240 {
00241 en = en->next;
00242 if( !en ) break;
00243
00244 n = EdgeCycle( e, e->v[end], TE );
00245
00246 for( i = 1; TE[i] != en->el; i++ )
00247 {
00248 CT_DoAboveEdge( TE[i], e->v[end], &CA, &CB );
00249 }
00250
00251 for( i = n-1; TE[i] != en->el; i-- )
00252 {
00253 CT_DoBelowEdge( TE[i], e->v[end], &CA, &CB );
00254 }
00255
00256 e = en->el;
00257 }
00258
00259
00260
00261
00262 nEdges = cn->seg->e.nElems;
00263 for( en = cn->seg->e.First(), i=0; en != 0; en = en->next, i++ )
00264 edges[i] = en->el;
00265 heapsort( nEdges, edges );
00266
00267 n = EdgeCycle( e, e->v[end], TE );
00268
00269 for( i = 1; ; i++ )
00270 {
00271 CT_DoAboveEdge( TE[i], e->v[end], &CA, &CB );
00272
00273 if( BinarySearch( (void *)TE[i], nEdges, edges ) >= 0 )
00274 break;
00275 }
00276
00277 for( i = n-1; ; i-- )
00278 {
00279 CT_DoBelowEdge( TE[i], e->v[end], &CA, &CB );
00280
00281 if( BinarySearch( (void *)TE[i], nEdges, edges ) >= 0 )
00282 break;
00283 }
00284 }
00285
00286
00287 ISDeleteOwnerMaps(E);
00288
00289
00290
00291
00292
00293
00294
00295
00296
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307 }
00308
00309 void IntersectionSubTree( contour_node *C, int oset, int InA, int InB,
00310 List<ListNode<gul::polyline<point2<rational> > > >& pl )
00311 {
00312 ListNode<gul::polyline<point2<rational> > > *pln;
00313 gul::ptr_int_union UA,UB;
00314 gul::RefMap<void>::Node cn;
00315 bool store;
00316
00317 UA.set_i(InA);
00318 UB.set_i(InB);
00319 store = false;
00320
00321 if( oset == (InA|InB) )
00322 {
00323 if( C->hasOwner(UA.p) )
00324 oset ^= InA;
00325
00326 if( C->hasOwner(UB.p) )
00327 oset ^= InB;
00328
00329 if( oset != (InA|InB) )
00330 store = true;
00331 }
00332 else
00333 {
00334 if( C->hasOwner(UA.p) )
00335 oset ^= InA;
00336
00337 if( C->hasOwner(UB.p) )
00338 oset ^= InB;
00339
00340 if( oset == (InA|InB) )
00341 store = true;
00342 }
00343
00344 if( store )
00345 {
00346 pln = new ListNode<gul::polyline<point2<rational> > >();
00347 C->get_polyline_joined( pln->el );
00348 pl.Append(pln);
00349 }
00350
00351
00352 cn = C->childs.First();
00353 while( !cn.IsEmpty() )
00354 {
00355 IntersectionSubTree( (contour_node *)cn.key(), oset, InA, InB, pl );
00356 cn = C->childs.Successor( cn );
00357 }
00358 }
00359
00360
00361
00362 void UnionSubTree( contour_node *C, int oset, int OutA, int OutB,
00363 List<ListNode<gul::polyline<point2<rational> > > >& pl )
00364 {
00365 ListNode<gul::polyline<point2<rational> > > *pln;
00366 gul::ptr_int_union UA,UB;
00367 gul::RefMap<void>::Node cn;
00368 bool store;
00369
00370 UA.set_i(OutA);
00371 UB.set_i(OutB);
00372 store = false;
00373
00374 if( (oset & (OutA|OutB)) != 0 )
00375 {
00376 if( C->hasOwner(UA.p) )
00377 oset ^= OutA;
00378
00379 if( C->hasOwner(UB.p) )
00380 oset ^= OutB;
00381
00382 if( (oset & (OutA|OutB)) == 0 )
00383 store = true;
00384 }
00385 else
00386 {
00387 if( C->hasOwner(UA.p) )
00388 oset ^= OutA;
00389
00390 if( C->hasOwner(UB.p) )
00391 oset ^= OutB;
00392
00393 if( (oset & (OutA|OutB)) != 0 )
00394 store = true;
00395 }
00396
00397 if( store )
00398 {
00399 pln = new ListNode<gul::polyline<point2<rational> > >();
00400 C->get_polyline_joined( pln->el );
00401 pl.Append(pln);
00402 }
00403
00404
00405 cn = C->childs.First();
00406 while( !cn.IsEmpty() )
00407 {
00408 UnionSubTree( (contour_node *)cn.key(), oset, OutA, OutB, pl );
00409 cn = C->childs.Successor( cn );
00410 }
00411 }
00412
00413 void DifferenceSubTree( contour_node *C, int oset, int InA, int OutB,
00414 List<ListNode<gul::polyline<point2<rational> > > >& pl )
00415 {
00416 ListNode<gul::polyline<point2<rational> > > *pln;
00417 gul::ptr_int_union UA,UB;
00418 gul::RefMap<void>::Node cn;
00419 bool store;
00420
00421 UA.set_i(InA);
00422 UB.set_i(OutB);
00423 store = false;
00424
00425 if( oset == InA )
00426 {
00427 if( C->hasOwner(UA.p) )
00428 oset ^= InA;
00429
00430 if( C->hasOwner(UB.p) )
00431 oset ^= OutB;
00432
00433 if( oset != InA )
00434 store = true;
00435 }
00436 else
00437 {
00438 if( C->hasOwner(UA.p) )
00439 oset ^= InA;
00440
00441 if( C->hasOwner(UB.p) )
00442 oset ^= OutB;
00443
00444 if( oset == InA )
00445 store = true;
00446 }
00447
00448 if( store )
00449 {
00450 pln = new ListNode<gul::polyline<point2<rational> > >();
00451 C->get_polyline_joined( pln->el );
00452 pl.Append(pln);
00453 }
00454
00455
00456 cn = C->childs.First();
00457 while( !cn.IsEmpty() )
00458 {
00459 DifferenceSubTree( (contour_node *)cn.key(), oset, InA, OutB, pl );
00460 cn = C->childs.Successor( cn );
00461 }
00462 }
00463
00464
00465
00466
00467 GULAPI void DoIntersection(
00468 List< ListNode<polyline> >& PA,
00469 List< ListNode<polyline> >& PB,
00470 const rational& far_x,
00471 const rational& far_y,
00472 List<ListNode<gul::polyline<point2<rational> > > >& C )
00473 {
00474 const int OutA = 1;
00475 const int InA = 2;
00476 const int OutB = 4;
00477 const int InB = 8;
00478 graph_edge_list E;
00479 graph_vertex_list V;
00480 segment_list S,Stmp;
00481 List<contour_node> contours;
00482 contour_node universe(0);
00483
00484
00485
00486 OddEvenRule( PA, far_x, far_y, InA, OutA, E, V, S );
00487 OddEvenRule( PB, far_x, far_y, InB, OutB, E, V, Stmp );
00488 S += Stmp;
00489
00490
00491 ContainmentTree( S, far_x, far_y, contours, universe );
00492
00493
00494 IntersectionSubTree( &universe, 0, InA, InB, C );
00495 }
00496
00497
00498
00499
00500 GULAPI void DoUnion(
00501 List< ListNode<polyline> >& PA,
00502 List< ListNode<polyline> >& PB,
00503 const rational& far_x,
00504 const rational& far_y,
00505 List<ListNode<gul::polyline<point2<rational> > > >& C )
00506 {
00507 const int OutA = 1;
00508 const int InA = 2;
00509 const int OutB = 4;
00510 const int InB = 8;
00511 graph_edge_list E;
00512 graph_vertex_list V;
00513 segment_list S,Stmp;
00514 List<contour_node> contours;
00515 contour_node universe(0);
00516
00517
00518
00519 OddEvenRule( PA, far_x, far_y, InA, OutA, E, V, S );
00520 OddEvenRule( PB, far_x, far_y, InB, OutB, E, V, Stmp );
00521 S += Stmp;
00522
00523
00524 ContainmentTree( S, far_x, far_y, contours, universe );
00525
00526
00527 UnionSubTree( &universe, 0, OutA, OutB, C );
00528 }
00529
00530
00531
00532
00533 GULAPI void DoDifference(
00534 List< ListNode<polyline> >& PA,
00535 List< ListNode<polyline> >& PB,
00536 const rational& far_x,
00537 const rational& far_y,
00538 List<ListNode<gul::polyline<point2<rational> > > >& C )
00539 {
00540 const int OutA = 1;
00541 const int InA = 2;
00542 const int OutB = 4;
00543 const int InB = 8;
00544 graph_edge_list E;
00545 graph_vertex_list V;
00546 segment_list S,Stmp;
00547 List<contour_node> contours;
00548 contour_node universe(0);
00549
00550
00551
00552 OddEvenRule( PA, far_x, far_y, InA, OutA, E, V, S );
00553 OddEvenRule( PB, far_x, far_y, InB, OutB, E, V, Stmp );
00554 S += Stmp;
00555
00556
00557 ContainmentTree( S, far_x, far_y, contours, universe );
00558
00559
00560 DifferenceSubTree( &universe, 0, InA, OutB, C );
00561 }
00562
00563
00564
00565
00566
00567 template< class T >
00568 GULAPI void ConvertToRationalPolys(
00569 List< ListNode< gul::polyline<point2<T> > > >& A,
00570 List< ListNode< gul::polyline<point2<T> > > >& B,
00571 T *ret_minx,
00572 T *ret_miny,
00573 T *ret_scale,
00574 rational *ret_far_x,
00575 rational *ret_far_y,
00576 List< ListNode<gugr::polyline> >& PA,
00577 List< ListNode<gugr::polyline> >& PB )
00578 {
00579 T minx,maxx,miny,maxy;
00580 T dx,dy,scale,scalei;
00581 ListNode< gugr::polyline > *pn;
00582 ListNode< gul::polyline<point2<T> > > *c;
00583 unsigned long *cbuf =
00584 (unsigned long *)alloca(gul::rtr<T>::mantissa_length());
00585
00586 c = A.First();
00587 CalcBoundingBoxE( c->el.n, c->el.P, minx, maxx, miny, maxy );
00588 c = c->next;
00589 while( c )
00590 {
00591 UpdateBoundingBoxE( c->el.n, c->el.P, minx, maxx, miny, maxy );
00592 c = c->next;
00593 }
00594 c = B.First();
00595 while( c )
00596 {
00597 UpdateBoundingBoxE( c->el.n, c->el.P, minx, maxx, miny, maxy );
00598 c = c->next;
00599 }
00600
00601 dx = maxx - minx;
00602 dy = maxy - miny;
00603 scale = dx > dy ? dx : dy;
00604 minx -= scale;
00605 miny -= scale;
00606 scalei = (T)1/scale;
00607
00608 c = A.First();
00609 while( c )
00610 {
00611 pn = new ListNode<gugr::polyline>();
00612 PA.Append( pn );
00613 pn->el.init( c->el.n, c->el.P, minx, miny, scalei );
00614 c = c->next;
00615 }
00616 c = B.First();
00617 while( c )
00618 {
00619 pn = new ListNode<gugr::polyline>();
00620 PB.Append( pn );
00621 pn->el.init( c->el.n, c->el.P, minx, miny, scalei );
00622 c = c->next;
00623 }
00624
00625 *ret_minx = minx;
00626 *ret_miny = miny;
00627 *ret_scale = scale;
00628 *ret_far_y = *ret_far_x = rational(coord2int((T)2,cbuf),cbuf) +
00629 rational(ULong(0x100000));
00630 }
00631
00632 template GULAPI void ConvertToRationalPolys(
00633 List< ListNode< gul::polyline<point2<float> > > >& A,
00634 List< ListNode< gul::polyline<point2<float> > > >& B,
00635 float *ret_minx,
00636 float *ret_miny,
00637 float *ret_scale,
00638 rational *ret_far_x,
00639 rational *ret_far_y,
00640 List< ListNode<gugr::polyline> >& PA,
00641 List< ListNode<gugr::polyline> >& PB );
00642 template GULAPI void ConvertToRationalPolys(
00643 List< ListNode< gul::polyline<point2<double> > > >& A,
00644 List< ListNode< gul::polyline<point2<double> > > >& B,
00645 double *ret_minx,
00646 double *ret_miny,
00647 double *ret_scale,
00648 rational *ret_far_x,
00649 rational *ret_far_y,
00650 List< ListNode<gugr::polyline> >& PA,
00651 List< ListNode<gugr::polyline> >& PB );
00652
00653
00654
00655
00656
00657
00658 template< class T >
00659 GULAPI void ConvertToFloatPoly(
00660 List< ListNode<gul::polyline<point2<rational> > > >& inA,
00661 T minx,
00662 T miny,
00663 T scale,
00664 List< ListNode<gul::polyline<point2<T> > > >& outA )
00665 {
00666 ListNode<gul::polyline<point2<rational> > > *c;
00667 ListNode<gul::polyline<point2<T> > > *fc;
00668 Interval ix,iy;
00669 T x,y;
00670 int i;
00671
00672 c = inA.First();
00673 while( c )
00674 {
00675 fc = new ListNode<gul::polyline<point2<T> > >;
00676 fc->el.P.reserve_pool(c->el.n);
00677 fc->el.n = c->el.n;
00678 outA.Append(fc);
00679
00680 for( i = 0; i < c->el.n; i++ )
00681 {
00682 ix = c->el.P[i].x.get_bounds();
00683 iy = c->el.P[i].y.get_bounds();
00684 x = (T)((ix.m_low+ix.m_high)/2.0);
00685 y = (T)((iy.m_low+iy.m_high)/2.0);
00686 x = gugr::cnv2coord(x)*scale + minx;
00687 y = gugr::cnv2coord(y)*scale + miny;
00688 fc->el.P[i].x = x;
00689 fc->el.P[i].y = y;
00690 }
00691 c = c->next;
00692 }
00693 }
00694
00695 template GULAPI void ConvertToFloatPoly(
00696 List< ListNode<gul::polyline<point2<rational> > > >& inA,
00697 float minx,
00698 float miny,
00699 float scale,
00700 List< ListNode<gul::polyline<point2<float> > > >& outA );
00701 template GULAPI void ConvertToFloatPoly(
00702 List< ListNode<gul::polyline<point2<rational> > > >& inA,
00703 double minx,
00704 double miny,
00705 double scale,
00706 List< ListNode<gul::polyline<point2<double> > > >& outA );
00707
00708
00709 }