Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members  

gugr_bool.cpp

Go to the documentation of this file.
00001 /* LIBGUL - Geometry Utility Library
00002  * Copyright (C) 1998-1999 Norbert Irmer
00003  *
00004  * This library is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU Library General Public
00006  * License as published by the Free Software Foundation; either
00007  * version 2 of the License, or (at your option) any later version.
00008  *
00009  * This library is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012  * Library General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU Library General Public
00015  * License along with this library; if not, write to the
00016  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
00017  * Boston, MA 02111-1307, USA.
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() )  // because of the first planesweep edge/side 
00075   {                       // pairs can have only one owner contour
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; // ignore help lines of other contours
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() )  // because of the first planesweep edge/side 
00141   {                       // pairs can have only one owner contour
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; // ignore help lines of other contours
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   // cout << dump_graph(&V,&E);
00200 
00201   FindContours(E,V,far_maxx,far_maxy,segs,contours);
00202 
00203   // cout << dump_graph(&V,&E);
00204   // cout << dump_segs(&segs);
00205 
00206   E.DeleteElems();
00207   V.DeleteElems();
00208   
00209   // travert the help lines and build the containment tree
00210 
00211   IntersectSegments( segs, &E, &V, false );
00212 
00213   // cout << dump_graph(&V,&E);
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 )    // travert contours
00219   {
00220     CA = &universe; // current open contour above (or right) of help line
00221     CB = &universe; // current open contour below (or left) of help line
00222 
00223     if( !cn->hseg ) continue;
00224 
00225     // dump_segment(cn->hseg,cout);
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;  // the last edge is a special case
00243 
00244       n = EdgeCycle( e, e->v[end], TE ); 
00245 
00246       for( i = 1; TE[i] != en->el; i++ ) // edges above help line (or left of 
00247       {                                  // vertical  help line)
00248         CT_DoAboveEdge( TE[i], e->v[end], &CA, &CB );
00249       }
00250 
00251       for( i = n-1; TE[i] != en->el; i-- ) // edges below help line (or right of 
00252       {                                    // vertical help line)
00253         CT_DoBelowEdge( TE[i], e->v[end], &CA, &CB );
00254       }
00255 
00256       e = en->el;  // next edge
00257     }
00258     // last edge, its endpoint lies on the segment of the contour which
00259     // shall be classified. it is sufficient to do the classification
00260     // with one of the edges of these segment
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++ ) // edges above help line until edge on segment reached
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-- ) // edges below help line until edge on segment reached
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   // cleanup
00287   ISDeleteOwnerMaps(E);
00288 
00289   /*
00290   int j;
00291   cn = contours.First();
00292   j = 0;
00293   while( cn )
00294   {
00295     j++;
00296     cout << "CONTOUR #" << j << " (" << (void *)cn << ")\n";
00297     cout << dump_vector<void*>(cn->nOwners, cn->owners);
00298     for( i = 0; i < cn->nVerts; i++ )
00299       cout << "(" << cn->verts[i].v() << "), ";
00300     cout << "\n";
00301     cn = cn->next;
00302   }
00303   */
00304 
00305   // cout << "containment tree\n";
00306   // universe.dump(0);
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   // travert children
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   // travert children
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   // travert children
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   calculates the intersection of two polygons
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);  // pseudo contour which contains everything
00483 
00484   // get the segments of both polygons and mark them with
00485   // InA,OutA,InB,OutB 
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   // find all contours and build their containment tree
00491   ContainmentTree( S, far_x, far_y, contours, universe );
00492   // universe.dump(0);
00493 
00494   IntersectionSubTree( &universe, 0, InA, InB, C );
00495 }
00496 
00497 /*---------------------------------------------------------------------
00498   calculates the union of two polygons
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);  // pseudo contour which contains everything
00516 
00517   // get the segments of both polygons and mark them with
00518   // InA,OutA,InB,OutB 
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   // find all contours and build their containment tree
00524   ContainmentTree( S, far_x, far_y, contours, universe );
00525   // universe.dump(0);
00526 
00527   UnionSubTree( &universe, 0, OutA, OutB, C );
00528 }
00529 
00530 /*---------------------------------------------------------------------
00531   calculates the difference of two polygons
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);  // pseudo contour which contains everything
00549 
00550   // get the segments of both polygons and mark them with
00551   // InA,OutA,InB,OutB 
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   // find all contours and build their containment tree
00557   ContainmentTree( S, far_x, far_y, contours, universe );
00558   // universe.dump(0);
00559 
00560   DifferenceSubTree( &universe, 0, InA, OutB, C );
00561 }
00562 
00563 /*---------------------------------------------------------------
00564   convert polylines with floating-point points into polylines with
00565   rational points
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,  // far away
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 // template instantiation
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,  // far away
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,  // far away
00649       rational *ret_far_y,
00650       List< ListNode<gugr::polyline> >& PA,
00651       List< ListNode<gugr::polyline> >& PB );
00652 
00653 
00654 /*---------------------------------------------------------------
00655   convert a polyline with rational points into a polyline with
00656   floating-point points
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 // template instantiation
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 }

Generated on Mon Jan 21 04:17:28 2002 for GUL 0.6 - Geometry Utility Library by doxygen1.2.13.1 written by Dimitri van Heesch, © 1997-2001