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

gugr_contour.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 <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   // travert vertices of contour
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];  // use existing line equation
00069     s->f[0].set_i(keyleft);
00070     s->f[1].set_i(keyright);
00071     s->m = 1;            // set multiplicity to 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     // orient the edges as the planesweep algorithm expects them
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   // travert vertices of contour
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];  // use existing line equation
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;            // set multiplicity to 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     // orient the edges as the planesweep algorithm expects them
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 // template instantiation
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];                           // first vertice of contour
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];                            // second vertice of contour
00217   vn = new ListNode<graph_vertex *>(v);
00218   vlist.Append(vn);
00219 
00220   curside = 0;             // begin with the left side of the edge/side pair
00221   owners = (RefMap<void> *)e->f[0].p; // initialize owner set
00222   e->f[0].p = 0;                      // mark this edge/side pair as processed
00223 
00224                   // set owner of corresponding segment to current contour
00225   seg = (segment *)e->reserved[2].p;
00226   if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
00227     seg->f[1].p = cn; // segment orientation different
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     // each edge has a backpointer to a segment for the second planesweep;
00237     // the face fields of these segments are initialized here (the planesweep
00238     // algo uses another edge orientation scheme then the rest of the graph
00239     // functions do !)
00240 
00241     seg = (segment *)e->reserved[2].p;
00242 
00243     if( e->v[0] == v )
00244     {
00245       curside = 0;  // use owners on the left side of the edge
00246       v = e->v[1];
00247 
00248       if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
00249         seg->f[1].p = cn; // segment orientation different
00250       else
00251         seg->f[0].p = cn;
00252     }
00253     else
00254     {
00255       curside = 1; // use owners on the right side of the edge
00256       v = e->v[0];
00257 
00258       if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
00259         seg->f[0].p = cn; // segment orientation different
00260       else
00261         seg->f[1].p = cn;
00262     }
00263 
00264     // add the owners of current edge/side pair to the contour owner set
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 )                     // new owner
00273       {
00274         owner = owners->NewNode( eowner.key() );
00275         owners->InsertNode( owner, parent, side );
00276       }
00277       eowner = eowners->Successor( eowner );
00278     }
00279     delete eowners;       // edge/side owners not needed anymore
00280     e->f[curside].p = 0;  // mark edge/side pair as processed
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   // convert vertex list to array and delete it
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   // convert owner set to array and delete it
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];                           // first vertice of contour
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];                            // second vertice of contour
00352   vn = new ListNode<graph_vertex *>(v);
00353   vlist.Append(vn);
00354 
00355   curside = 1;             // begin with the right side of the edge/side pair
00356   owners = (RefMap<void> *)e->f[1].p; // initialize owner set
00357   e->f[1].p = 0;                      // mark this edge/side pair as processed
00358 
00359                   // set owner of corresponding segment to current contour
00360   seg = (segment *)e->reserved[2].p;
00361   if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
00362     seg->f[0].p = cn; // segment orientation different
00363   else
00364     seg->f[1].p = cn;
00365 
00366   for(;;)
00367   {
00368     n = EdgeCycle( e, v, TE ); 
00369     e = TE[1];
00370 
00371     // each edge has a backpointer to a segment for the second planesweep;
00372     // the face fields of these segments are initialized here (the planesweep
00373     // algo uses another edge orientation scheme then the rest of the graph
00374     // functions too !)
00375 
00376     seg = (segment *)e->reserved[2].p;
00377 
00378     if( e->v[0] == v )
00379     {
00380       curside = 1;  // use owners on the right side of the edge
00381       v = e->v[1];
00382 
00383       if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
00384         seg->f[0].p = cn; // segment orientation different
00385       else
00386         seg->f[1].p = cn;
00387     }
00388     else
00389     {
00390       curside = 0; // use owners on the left side of the edge
00391       v = e->v[0];
00392 
00393       if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
00394         seg->f[1].p = cn; // segment orientation different
00395       else
00396         seg->f[0].p = cn;
00397     }
00398     // add the owners of current edge/side pair to the contour owner set
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 )                     // new owner
00407       {
00408         owner = owners->NewNode( eowner.key() );
00409         owners->InsertNode( owner, parent, side );
00410       }
00411       eowner = eowners->Successor( eowner );
00412     }
00413     delete eowners;       // edge/side owners not needed anymore
00414     e->f[curside].p = 0;  // mark edge/side pair as processed
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   // convert vertex list to array and delete it
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   // convert owner set to array and delete it
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   Finds all contours in a graph. It also constructs segment for
00465   each graph edge and also a help line for each contour, which can be
00466   used to apply the odd even rule or to build a containment tree 
00467 
00468   (remarks: 
00469 
00470     This function sets the 'reserved[2]' field of the edges in 'E'. It
00471     will contain a pointer to the segment which is created for this
00472     edge
00473 
00474     This function expects that the 'f[0]' and 'f[1]' fields of the
00475     edges in 'E' contain owner sets for the edge/side pairs (these
00476     owner sets are created by the planesweep algorithm). Each contour,
00477     which is found, gets the union of these owner sets as its own
00478     owner set. After that the 'f[0]' and 'f[1]' fields of the edges
00479     are cleared.
00480     The f[0] and f[1] fields of the created segments will contain 
00481     pointers to the contours to which the corresponding edge/side pairs
00482     belongs
00483 
00484     Each contour will get a pointer to one of its segments, and to the
00485     help line (originating from the middle of this segment) which can be
00486     used to classify this region
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   // reserve a new segment struct for each edge (needed later for the
00504   // classification of the formed regions with the odd/even winding rule)
00505 
00506   e = E.First();
00507   while( e )
00508   {
00509     sn = new ListNode<segment>;
00510     outsegs.Append(sn);
00511 
00512     // orient the segments as the planesweep algorithm expects them
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; // multiplicity of edge (for winding rule)
00526 
00527     e->reserved[2].p = &sn->el;  // back pointer edge -> new segment
00528     e = e->next;
00529   }
00530 
00531   // find the non-intersecting regions
00532 
00533   e = E.First();
00534   laste = 0;
00535   lastseg = 0;
00536 
00537   while( e )
00538   {
00539     /*
00540     cout << "processing edge " << (void *)e << "\n";
00541     */
00542 
00543     if( e->f[0].p )
00544     {
00545       cn = new contour_node(0);  // new contour
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         // construct a help line for each contour for classifying it 
00554         // later with an odd/even winding rule
00555 
00556         hn = new ListNode<segment>;
00557         outsegs.Append(hn);
00558         h = &hn->el;
00559 
00560         if( !e->l.IsHorizontal() )  // horizontal help line
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;  // edge/side pairs belong to no contour
00569           h->l = line( h->E, rational(ULong(1)), rational(ULong(0)) );
00570         }
00571         else    // vertical help line
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;  // edge/side pairs belong to no contour
00580 
00581           h->l = line( h->E, rational(ULong(0)), rational(ULong(1)) );
00582         }   
00583 
00584         cn->hseg = h; // remember the address of the created help line
00585         cn->hseg_firstref = true;
00586 
00587         /*
00588         DumpPS<float>::dump_segment( h );
00589         */
00590 
00591         laste = e;
00592         lastseg = h;
00593       }
00594       else
00595       {
00596         cn->hseg = lastseg; // remember the address of the created help line
00597         cn->hseg_firstref = false;
00598 
00599         /*
00600         DumpPS<float>::dump_segment( lastseg );
00601         */
00602       }
00603     }
00604     
00605     if( e->f[1].p )
00606     {
00607       cn = new contour_node(0);  // new contour
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         // construct a help line for each contour for classifying it 
00616         // later with an odd/even winding rule
00617 
00618         hn = new ListNode<segment>;
00619         outsegs.Append(hn);
00620         h = &hn->el;
00621 
00622         if( !e->l.IsHorizontal() )  // horizontal help line
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;  // edge/side pairs belong to no contour
00631           h->l = line( h->E, rational(ULong(1)), rational(ULong(0)) );
00632         }
00633         else    // vertical help line
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;  // edge/side pairs belong to no contour
00642 
00643           h->l = line( h->E, rational(ULong(0)), rational(ULong(1)) );
00644         }   
00645         cn->hseg = h; // remember the address of the created help line
00646         cn->hseg_firstref = true;
00647 
00648         /*
00649         DumpPS<float>::dump_segment( h );
00650         */
00651 
00652         laste = e;
00653         lastseg = h;
00654       }
00655       else
00656       {
00657         cn->hseg = lastseg; // remember the address of the created help line
00658         cn->hseg_firstref = false;
00659 
00660         /*
00661         DumpPS<float>::dump_segment( lastseg );
00662         */
00663       }
00664     }
00665 
00666     e = e->next;
00667   }
00668 }
00669 
00670 /*------------------------------------------------------------------
00671   Removes unnecessary edges by applying the odd/even winding rule
00672 
00673   (remarks:
00674 
00675    If the edges in 'E' contain backpointers into the edge lists of segments
00676    (segment::e), all references to removed edges will be removed, too.
00677 
00678    For each edge of 'E', which is not removed, a new segment is
00679    created in 'outsegs', but this segment only contains the geometry
00680    of the edge, not a pointer to it (i.e. the 'segment::e' list is
00681    empty for the new segments). The only purpose of this is to be
00682    able to do a planesweep or something else with the cleaned up
00683    graph
00684 
00685    The 'reserved[2]' of the edges from 'E' is used within this function
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   /* ------ second planesweep ------------------------------- */
00716 
00717   /*
00718   cout << "PLANESWEEP\n";
00719   cout << "==========\n";
00720   cout << "INPUT SEGMENTS\n";
00721   for( hn = segs.First(); hn != 0; hn = hn->next )
00722     DumpPS<float>::dump_segment( &hn->el );
00723   */
00724 
00725   IntersectSegments( outsegs, &E2, &V2, false );
00726 
00727   /*
00728   cout << "EDGES AFTER SECOND PLANESWEEP\n";
00729   cout << "============================\n";
00730   DumpPS<float>::dump_edges( E2 );
00731   cout << "\n";
00732   Dump<float>::dump_edges( E2.head );
00733   cout << "\n";
00734   cout.flush();
00735   */
00736 
00737   // travert the help lines to classify the regions as loops or holes
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 )    // travert contours
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;  // special treatment for the last edge
00761 
00762       n = EdgeCycle( e, e->v[end], TE ); 
00763 
00764       for( i = 1; TE[i] != en->el; i++ ) // edges above help line (or left of 
00765       {                                  //   vertical  help line)
00766         m += (int)TE[i]->reserved[0].i; // count the number of intersections
00767       }
00768 
00769       e = en->el;  // next edge
00770     }
00771 
00772     // last edge, its endpoint lies on the segment of the contour which
00773     // shall be classified
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++ ) // edges above help line until edge on segment reached
00783     {      
00784       if( BinarySearch( (void *)TE[i], nEdges, edges ) >= 0 )
00785         break;
00786 
00787       m += (int)TE[i]->reserved[0].i; // count the number of intersections
00788     }
00789 
00790     // if the contour lies on the opposite site of the segment edge add its
00791     // multiplicity too
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; // count the number of intersections
00802     }
00803 
00804     cn->hole = ((m & 1) == 0);
00805   }
00806 
00807   // cleanup 
00808   ISDeleteOwnerMaps(E2);
00809   E2.DeleteElems();
00810   V2.DeleteElems();
00811 
00812   /*
00813   cn = contours.First();
00814   i = 0;
00815   while( cn )
00816   {
00817     i++;
00818     cout << "CONTOUR #" << i << " (" << (void *)cn << ")\n";
00819     cout << "hole = " << cn->hole << "\n";
00820     cout << dump_vector<int>(cn->nOwners, cn->owners);
00821     for( i = 0; i < cn->nVerts; i++ )
00822       Dump<float>::dump_vert( cn->verts[i] );
00823     cn = cn->next;
00824   }
00825   */
00826 
00827   // remove unnecessary edges which have holes or loops on both sides
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       cout << "removing edge " << (void *)e << "\n";
00840       */
00841 
00842       // some dangerous pointer arithmetic to get the segment node address
00843       gul::Assert<InternalError>( ndebug || 
00844                (outsegs.First() == (ListNode<segment> *)&outsegs.First()->el) );
00845       
00846       /*
00847       cout << (void *)esegs.First() << " == " << 
00848               (void *)&esegs.First()->el << "\n";
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       // remove edge from the edge lists of backpointed segments
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();  // will be deleted manually in the following
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       // set the edge side flags. after this the graph is ready for 
00893       // triangulation
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); // segment orientation different
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       // set the side flags of the segments; after this the segment list can be
00918       // used as the input for building the new contours (without the 
00919       // unnecessary edges) and their containment tree for elimination of
00920       // unnecessary contours (like holes within holes)
00921 
00922       seg->f[0].set_i(left);
00923       seg->f[1].set_i(right);
00924       seg->e.DeleteElems(); // these are meaningless since they point into E2
00925 
00926       e = e->next;
00927     }
00928   }
00929 
00930   // cleanup 
00931 
00932   for( cn = contours.First(); cn != 0; cn = cn->next )    // remove help lines
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   cout << "EDGES AFTER REMOVAL\n";
00944   cout << "===================\n";
00945   Dump<float>::dump_edges( E.head );
00946   cout << "\n";
00947 
00948   cout << "SEGMENTS AFTER REMOVAL\n";
00949   cout << "===================\n";
00950   for( hn = esegs.First(); hn != 0; hn = hn->next )
00951     DumpPS<float>::dump_segment( &hn->el );
00952   */
00953 
00954   contours.DeleteElems();
00955 }
00956 
00957 /*------------------------------------------------------------------
00958   Forms a graph from a couple of contours, and removes  unnecessary 
00959   edges in this graph by applying the odd/even winding rule
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();  // clear output lists
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   cout << "PLANESWEEP\n";
00984   cout << "==========\n";
00985   cout << "INPUT SEGMENTS\n";
00986   for( hn = segs.First(); hn != 0; hn = hn->next )
00987     DumpPS<float>::dump_segment( &hn->el );
00988   */
00989 
00990   IntersectSegments( segs, &E, &V, false ); // backpointers are not needed,
00991                                             // since 'segs' is not used
00992 
00993   /*
00994   cout << "EDGES AFTER FIRST PLANESWEEP\n";
00995   cout << "============================\n";
00996   DumpPS<float>::dump_edges( E );
00997   cout << "\n";
00998   Dump<float>::dump_edges( E.head );
00999   cout << "\n";
01000   */
01001 
01002   segs.DeleteElems(); // delete input segments (not needed)
01003 
01004   RemoveUnnecessaryEdges( E, V, far_maxx, far_maxy, key_inside, key_outside, 
01005                           outsegs );
01006 }
01007 
01008 
01009 }
01010 

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