---

gugr_bool.cpp

Go to the documentation of this file.

/* LIBGUL - Geometry Utility Library
 * Copyright (C) 1998-1999 Norbert Irmer
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

#include "stdafx.h"

#include <iostream>

#include "gul_types.h"
#include "guar_exact.h"
#include "gugr_basics.h"
#include "gugr_planesweep.h"
#include "gugr_contour.h"
#include "guma_sorting.h"
#include "guge_normalize.h"
#include "gul_io.h"
#include "gul_std.h"
#include "gugr_io.h"

#include "gugr_bool.h"

namespace gugr {

using guma::heapsort;
using guma::BinarySearch;
using guge::CalcBoundingBoxE;
using guge::UpdateBoundingBoxE;
using gul::dump_vector;
using std::cout;

void CT_DoAboveEdge( 
          graph_edge *e, 
          graph_vertex *v,   
          contour_node **pCA,
          contour_node **pCB )
{
  RefMap<void> *Mout,*Min,*M;
  RefMap<void>::Node mn;
  contour_node *CA,*CB,*C,*Cout,*Cin;

  CA = *pCA;
  CB = *pCB;

  if( e->v[0] == v )
  {
    Mout = (RefMap<void> *)e->f[1].p;
    Min = (RefMap<void> *)e->f[0].p;
  }
  else
  {
    Mout = (RefMap<void> *)e->f[0].p;
    Min = (RefMap<void> *)e->f[1].p;
  }

  Cout = Cin = 0;

  M = Mout;
  mn = M->First();
  while( !mn.IsEmpty() )  // because of the first planesweep edge/side 
  {                       // pairs can have only one owner contour
    if( mn.key() ) { Cout = (contour_node *)mn.key(); break; }
    mn = M->Successor( mn );
  }
 
  M = Min;
  mn = M->First();
  while( !mn.IsEmpty() )
  {
    if( mn.key() ) { Cin = (contour_node *)mn.key(); break; }
    mn = M->Successor( mn );
  }

  C = Cout;        
  if( !C ) return; // ignore help lines of other contours

  if( C != CA )
  {
    CA->Insert( C );
    CA = C;
  }
  else
    CA = CA->parent;

  C = Cin;        
  if( C != CA )
  {
    CA->Insert( C );
    CA = C;
  }
  else
    CA = CA->parent;

  *pCA = CA;
  *pCB = CB;
}

void CT_DoBelowEdge( 
          graph_edge *e, 
          graph_vertex *v,   
          contour_node **pCA,
          contour_node **pCB )
{
  RefMap<void> *Mout,*Min,*M;
  RefMap<void>::Node mn;
  contour_node *CA,*CB,*C,*Cout,*Cin;

  CA = *pCA;
  CB = *pCB;

  if( e->v[0] == v )
  {
    Mout = (RefMap<void> *)e->f[0].p;
    Min = (RefMap<void> *)e->f[1].p;
  }
  else
  {
    Mout = (RefMap<void> *)e->f[1].p;
    Min = (RefMap<void> *)e->f[0].p;
  }

  Cout = Cin = 0;

  M = Mout;
  mn = M->First();
  while( !mn.IsEmpty() )  // because of the first planesweep edge/side 
  {                       // pairs can have only one owner contour
    if( mn.key() ) { Cout = (contour_node *)mn.key(); break; }
    mn = M->Successor( mn );
  }
 
  M = Min;
  mn = M->First();
  while( !mn.IsEmpty() )
  {
    if( mn.key() ) { Cin = (contour_node *)mn.key(); break; }
    mn = M->Successor( mn );
  }

  C = Cout;        
  if( !C ) return; // ignore help lines of other contours

  if( C != CB )
  {
    CB->Insert( C );
    CB = C;
  }
  else
    CB = CB->parent;

  C = Cin;        
  if( C != CB )
  {
    CB->Insert( C );
    CB = C;
  }
  else
    CB = CB->parent;

  *pCA = CA;
  *pCB = CB;
}

void ContainmentTree( 
         List< ListNode<segment> >& insegs,
         const rational& far_maxx, const rational& far_maxy,
         gul::List<contour_node>& contours, contour_node& universe )
{
  graph_edge_list E;
  graph_vertex_list V;
  List< ListNode<segment> > segs;
  contour_node *cn;
  graph_edge *e;
  int end,side,n,i;
  graph_edge **TE;
  ListNode<graph_edge *> *en;
  contour_node *CA,*CB;
  RefMap<void>::Node mn;
  Ptr<void *> edges;
  int nEdges;
  List<ListNode<gul::polyline<point2<rational> > > > testC;

  IntersectSegments( insegs, &E, &V, false );

  // cout << dump_graph(&V,&E);

  FindContours(E,V,far_maxx,far_maxy,segs,contours);

  // cout << dump_graph(&V,&E);
  // cout << dump_segs(&segs);

  E.DeleteElems();
  V.DeleteElems();
  
  // travert the help lines and build the containment tree

  IntersectSegments( segs, &E, &V, false );

  // cout << dump_graph(&V,&E);

  TE = (graph_edge **)alloca(sizeof(graph_edge *)*E.nElems);
  edges.reserve_pool(E.nElems);

  for( cn = contours.First(); cn != 0; cn = cn->next )    // travert contours
  {
    CA = &universe; // current open contour above (or right) of help line
    CB = &universe; // current open contour below (or left) of help line

    if( !cn->hseg ) continue;

    // dump_segment(cn->hseg,cout);

    en = cn->hseg->e.First();
    if( en ) 
    {
      e = en->el;

      if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
        end = 1;
      else
        end = 0;
      side = !end;
    }

    while( en )
    {
      en = en->next;      
      if( !en ) break;  // the last edge is a special case

      n = EdgeCycle( e, e->v[end], TE ); 

      for( i = 1; TE[i] != en->el; i++ ) // edges above help line (or left of 
      {                                  // vertical  help line)
        CT_DoAboveEdge( TE[i], e->v[end], &CA, &CB );
      }

      for( i = n-1; TE[i] != en->el; i-- ) // edges below help line (or right of 
      {                                    // vertical help line)
        CT_DoBelowEdge( TE[i], e->v[end], &CA, &CB );
      }

      e = en->el;  // next edge
    }
    // last edge, its endpoint lies on the segment of the contour which
    // shall be classified. it is sufficient to do the classification
    // with one of the edges of these segment

    nEdges = cn->seg->e.nElems;
    for( en = cn->seg->e.First(), i=0; en != 0; en = en->next, i++ )
      edges[i] = en->el;
    heapsort( nEdges, edges );

    n = EdgeCycle( e, e->v[end], TE ); 

    for( i = 1; ; i++ ) // edges above help line until edge on segment reached
    {      
      CT_DoAboveEdge( TE[i], e->v[end], &CA, &CB );

      if( BinarySearch( (void *)TE[i], nEdges, edges ) >= 0 )
        break;
    }

    for( i = n-1; ; i-- ) // edges below help line until edge on segment reached
    {      
      CT_DoBelowEdge( TE[i], e->v[end], &CA, &CB );

      if( BinarySearch( (void *)TE[i], nEdges, edges ) >= 0 )
        break;
    }
  }

  // cleanup
  ISDeleteOwnerMaps(E);

  /*
  int j;
  cn = contours.First();
  j = 0;
  while( cn )
  {
    j++;
    cout << "CONTOUR #" << j << " (" << (void *)cn << ")\n";
    cout << dump_vector<void*>(cn->nOwners, cn->owners);
    for( i = 0; i < cn->nVerts; i++ )
      cout << "(" << cn->verts[i].v() << "), ";
    cout << "\n";
    cn = cn->next;
  }
  */

  // cout << "containment tree\n";
  // universe.dump(0);
}

void IntersectionSubTree( contour_node *C, int oset, int InA, int InB,
                 List<ListNode<gul::polyline<point2<rational> > > >& pl )
{
  ListNode<gul::polyline<point2<rational> > > *pln;
  gul::ptr_int_union UA,UB;
  gul::RefMap<void>::Node cn;
  bool store;

  UA.set_i(InA);
  UB.set_i(InB);
  store = false;

  if( oset == (InA|InB) )
  {
    if( C->hasOwner(UA.p) )
      oset ^= InA;

    if( C->hasOwner(UB.p) )
      oset ^= InB;

    if( oset != (InA|InB) )
      store = true;
  }
  else
  {
    if( C->hasOwner(UA.p) )
      oset ^= InA;

    if( C->hasOwner(UB.p) )
      oset ^= InB;

    if( oset == (InA|InB) )
      store = true;
  }

  if( store )    
  {
    pln = new ListNode<gul::polyline<point2<rational> > >();
    C->get_polyline_joined( pln->el );
    pl.Append(pln);
  }

  // travert children
  cn = C->childs.First();
  while( !cn.IsEmpty() )
  {
    IntersectionSubTree( (contour_node *)cn.key(), oset, InA, InB, pl );
    cn = C->childs.Successor( cn );
  }
}



void UnionSubTree( contour_node *C, int oset, int OutA, int OutB,
                List<ListNode<gul::polyline<point2<rational> > > >& pl )
{
  ListNode<gul::polyline<point2<rational> > > *pln;
  gul::ptr_int_union UA,UB;
  gul::RefMap<void>::Node cn;
  bool store;

  UA.set_i(OutA);
  UB.set_i(OutB);
  store = false;

  if( (oset & (OutA|OutB)) != 0 )
  {
    if( C->hasOwner(UA.p) )
      oset ^= OutA;

    if( C->hasOwner(UB.p) )
      oset ^= OutB;

    if( (oset & (OutA|OutB)) == 0 )
      store = true;
  }
  else
  {
    if( C->hasOwner(UA.p) )
      oset ^= OutA;

    if( C->hasOwner(UB.p) )
      oset ^= OutB;

    if( (oset & (OutA|OutB)) != 0  )
      store = true;
  }

  if( store )    
  {
    pln = new ListNode<gul::polyline<point2<rational> > >();
    C->get_polyline_joined( pln->el );
    pl.Append(pln);
  }

  // travert children
  cn = C->childs.First();
  while( !cn.IsEmpty() )
  {
    UnionSubTree( (contour_node *)cn.key(), oset, OutA, OutB, pl );
    cn = C->childs.Successor( cn );
  }
}

void DifferenceSubTree( contour_node *C, int oset, int InA, int OutB,
                 List<ListNode<gul::polyline<point2<rational> > > >& pl )
{
  ListNode<gul::polyline<point2<rational> > > *pln;
  gul::ptr_int_union UA,UB;
  gul::RefMap<void>::Node cn;
  bool store;

  UA.set_i(InA);
  UB.set_i(OutB);
  store = false;

  if( oset == InA )
  {
    if( C->hasOwner(UA.p) )
      oset ^= InA;

    if( C->hasOwner(UB.p) )
      oset ^= OutB;

    if( oset != InA )
      store = true;
  }
  else
  {
    if( C->hasOwner(UA.p) )
      oset ^= InA;

    if( C->hasOwner(UB.p) )
      oset ^= OutB;

    if( oset == InA )
      store = true;
  }

  if( store )    
  {
    pln = new ListNode<gul::polyline<point2<rational> > >();
    C->get_polyline_joined( pln->el );
    pl.Append(pln);
  }

  // travert children
  cn = C->childs.First();
  while( !cn.IsEmpty() )
  {
    DifferenceSubTree( (contour_node *)cn.key(), oset, InA, OutB, pl );
    cn = C->childs.Successor( cn );
  }
}

/*---------------------------------------------------------------------
  calculates the intersection of two polygons
----------------------------------------------------------------------*/
GULAPI void DoIntersection( 
          List< ListNode<polyline> >& PA, 
          List< ListNode<polyline> >& PB,
          const rational& far_x,
          const rational& far_y,
          List<ListNode<gul::polyline<point2<rational> > > >& C )
{
  const int OutA = 1;
  const int InA = 2;
  const int OutB = 4;
  const int InB = 8;
  graph_edge_list E;
  graph_vertex_list V;
  segment_list S,Stmp; 
  List<contour_node> contours;
  contour_node universe(0);  // pseudo contour which contains everything

  // get the segments of both polygons and mark them with
  // InA,OutA,InB,OutB 
  OddEvenRule( PA, far_x, far_y, InA, OutA, E, V, S );
  OddEvenRule( PB, far_x, far_y, InB, OutB, E, V, Stmp );
  S += Stmp;

  // find all contours and build their containment tree
  ContainmentTree( S, far_x, far_y, contours, universe );
  // universe.dump(0);

  IntersectionSubTree( &universe, 0, InA, InB, C );
}

/*---------------------------------------------------------------------
  calculates the union of two polygons
----------------------------------------------------------------------*/
GULAPI void DoUnion( 
          List< ListNode<polyline> >& PA, 
          List< ListNode<polyline> >& PB,
          const rational& far_x,
          const rational& far_y,
          List<ListNode<gul::polyline<point2<rational> > > >& C )
{
  const int OutA = 1;
  const int InA = 2;
  const int OutB = 4;
  const int InB = 8;
  graph_edge_list E;
  graph_vertex_list V;
  segment_list S,Stmp; 
  List<contour_node> contours;
  contour_node universe(0);  // pseudo contour which contains everything

  // get the segments of both polygons and mark them with
  // InA,OutA,InB,OutB 
  OddEvenRule( PA, far_x, far_y, InA, OutA, E, V, S );
  OddEvenRule( PB, far_x, far_y, InB, OutB, E, V, Stmp );
  S += Stmp;

  // find all contours and build their containment tree
  ContainmentTree( S, far_x, far_y, contours, universe );
  // universe.dump(0);

  UnionSubTree( &universe, 0, OutA, OutB, C );
}

/*---------------------------------------------------------------------
  calculates the difference of two polygons
----------------------------------------------------------------------*/
GULAPI void DoDifference( 
          List< ListNode<polyline> >& PA, 
          List< ListNode<polyline> >& PB,
          const rational& far_x,
          const rational& far_y,
          List<ListNode<gul::polyline<point2<rational> > > >& C )
{
  const int OutA = 1;
  const int InA = 2;
  const int OutB = 4;
  const int InB = 8;
  graph_edge_list E;
  graph_vertex_list V;
  segment_list S,Stmp; 
  List<contour_node> contours;
  contour_node universe(0);  // pseudo contour which contains everything

  // get the segments of both polygons and mark them with
  // InA,OutA,InB,OutB 
  OddEvenRule( PA, far_x, far_y, InA, OutA, E, V, S );
  OddEvenRule( PB, far_x, far_y, InB, OutB, E, V, Stmp );
  S += Stmp;

  // find all contours and build their containment tree
  ContainmentTree( S, far_x, far_y, contours, universe );
  // universe.dump(0);

  DifferenceSubTree( &universe, 0, InA, OutB, C );
}

/*---------------------------------------------------------------
  convert polylines with floating-point points into polylines with
  rational points
----------------------------------------------------------------*/  
template< class T >
GULAPI void ConvertToRationalPolys(  
      List< ListNode< gul::polyline<point2<T> > > >& A,
      List< ListNode< gul::polyline<point2<T> > > >& B,
      T *ret_minx,
      T *ret_miny,
      T *ret_scale,
      rational *ret_far_x,  // far away
      rational *ret_far_y,
      List< ListNode<gugr::polyline> >& PA,
      List< ListNode<gugr::polyline> >& PB )
{
  T minx,maxx,miny,maxy;
  T dx,dy,scale,scalei;
  ListNode< gugr::polyline > *pn;
  ListNode< gul::polyline<point2<T> > > *c;
  unsigned long *cbuf = 
    (unsigned long *)alloca(gul::rtr<T>::mantissa_length());

  c = A.First();
  CalcBoundingBoxE( c->el.n, c->el.P, minx, maxx, miny, maxy );
  c = c->next;
  while( c )
  {
    UpdateBoundingBoxE( c->el.n, c->el.P, minx, maxx, miny, maxy );
    c = c->next;
  }
  c = B.First();
  while( c )
  {
    UpdateBoundingBoxE( c->el.n, c->el.P, minx, maxx, miny, maxy );
    c = c->next;
  }

  dx = maxx - minx;
  dy = maxy - miny;
  scale = dx > dy ? dx : dy;
  minx -= scale;
  miny -= scale;
  scalei = (T)1/scale;

  c = A.First();
  while( c )
  {
    pn = new ListNode<gugr::polyline>();
    PA.Append( pn );
    pn->el.init( c->el.n, c->el.P, minx, miny, scalei ); 
    c = c->next;
  }
  c = B.First();
  while( c )
  {
    pn = new ListNode<gugr::polyline>();
    PB.Append( pn );
    pn->el.init( c->el.n, c->el.P, minx, miny, scalei ); 
    c = c->next;
  }

  *ret_minx = minx;
  *ret_miny = miny;
  *ret_scale = scale;
  *ret_far_y = *ret_far_x = rational(coord2int((T)2,cbuf),cbuf) +
                            rational(ULong(0x100000));
}
// template instantiation
template GULAPI void ConvertToRationalPolys(  
      List< ListNode< gul::polyline<point2<float> > > >& A,
      List< ListNode< gul::polyline<point2<float> > > >& B,
      float *ret_minx,
      float *ret_miny,
      float *ret_scale,
      rational *ret_far_x,  // far away
      rational *ret_far_y,
      List< ListNode<gugr::polyline> >& PA,
      List< ListNode<gugr::polyline> >& PB );
template GULAPI void ConvertToRationalPolys(  
      List< ListNode< gul::polyline<point2<double> > > >& A,
      List< ListNode< gul::polyline<point2<double> > > >& B,
      double *ret_minx,
      double *ret_miny,
      double *ret_scale,
      rational *ret_far_x,  // far away
      rational *ret_far_y,
      List< ListNode<gugr::polyline> >& PA,
      List< ListNode<gugr::polyline> >& PB );


/*---------------------------------------------------------------
  convert a polyline with rational points into a polyline with
  floating-point points
----------------------------------------------------------------*/  
template< class T >
GULAPI void ConvertToFloatPoly(
      List< ListNode<gul::polyline<point2<rational> > > >& inA,
      T minx,
      T miny,
      T scale,
      List< ListNode<gul::polyline<point2<T> > > >& outA )
{
  ListNode<gul::polyline<point2<rational> > > *c;
  ListNode<gul::polyline<point2<T> > > *fc;
  Interval ix,iy;
  T x,y;
  int i;

  c = inA.First();
  while( c )
  {
    fc = new ListNode<gul::polyline<point2<T> > >;
    fc->el.P.reserve_pool(c->el.n);
    fc->el.n = c->el.n;
    outA.Append(fc);

    for( i = 0; i < c->el.n; i++ )
    {
      ix = c->el.P[i].x.get_bounds();
      iy = c->el.P[i].y.get_bounds();
      x = (T)((ix.m_low+ix.m_high)/2.0);
      y = (T)((iy.m_low+iy.m_high)/2.0);
      x = gugr::cnv2coord(x)*scale + minx; 
      y = gugr::cnv2coord(y)*scale + miny; 
      fc->el.P[i].x = x;
      fc->el.P[i].y = y;
    }
    c = c->next;
  }
}
// template instantiation
template GULAPI void ConvertToFloatPoly(
      List< ListNode<gul::polyline<point2<rational> > > >& inA,
      float minx,
      float miny,
      float scale,
      List< ListNode<gul::polyline<point2<float> > > >& outA );
template GULAPI void ConvertToFloatPoly(
      List< ListNode<gul::polyline<point2<rational> > > >& inA,
      double minx,
      double miny,
      double scale,
      List< ListNode<gul::polyline<point2<double> > > >& outA );


}

---