---

gugr_planesweep.h

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.
 */

#ifndef GUGR_PLANESWEEP_H
#define GUGR_PLANESWEEP_H

namespace gugr {

using gul::InternalError;
using gul::PoolAllocError;
using gust::PoolAlloc;
using gust::PoolFree;
using gul::Ptr;
using gul::ListNode;
using gul::List;
using gul::Map;
using gul::RefMap;
using guar::rational;
using gul::point2;

/*-----------------------------------------------------------------------
  Structure which describes the input line segments for planesweep algorithm.
  It is used for storing the edges of the output graph which make up this
  segment too !
-----------------------------------------------------------------------*/
struct segment
{
  point2<rational> B;
  point2<rational> E;
  gugr::line  l;
  gul::ptr_int_union  f[2];        // left and right side owners
  int                 m;           // multiplicity
  void               *reserved[2]; // for internal use

  List< ListNode<gugr::graph_edge *> > e; // output graph edges

  segment() { m = 0; }
  ~segment() { e.DeleteElems(); }

  void *operator new( size_t s )
  {
    size_t dummy;
    void *p = PoolAlloc( s, &dummy );
    if( p == NULL ) throw PoolAllocError();
    return(p);
  }
  void operator delete( void *p, size_t s )
  {
    if( p != 0 ) PoolFree( p, s );
  }

  // shouldn't be copied (because of the destructor)
private:
  segment( const segment& other );  
  segment& operator=( const segment& other );
};

typedef gul::List<gul::ListNode<segment> > segment_list;

/*----------------------------------------------------------------------
  Structures for storing intersection points and segments.
  They contain a list of the original line-segments, which
  contain this intersections
----------------------------------------------------------------------*/ 
struct intersection
{
  point2<rational>                   I;
  List< ListNode<segment *> >   S;   
  gugr::graph_vertex           *v;

  intersection( const point2<rational>& a ) : I(a), v(0) { }
  ~intersection() { S.DeleteElems(); }

  intersection       *next; /* for storing all intersections in a list */
  intersection       *prev;

  void *operator new( size_t s )
  {
    size_t dummy;
    void *p = PoolAlloc( s, &dummy );
    if( p == NULL ) throw PoolAllocError();
    return(p);
  }
  void operator delete( void *p, size_t s )
  {
    if( p != 0 ) PoolFree( p, s );
  }

  // musn't be copied (because of the destructor)
private:
  intersection( const intersection& other );  
  intersection& operator=( const intersection& other );

};

struct intersectionseg
{
  List< ListNode<segment *> >   S;
  gugr::graph_edge             *e;

  intersectionseg( gugr::graph_edge *ae ) : e(ae) { }
  ~intersectionseg() { S.DeleteElems(); }

  intersectionseg    *next; /* for storing all intersections in a list */
  intersectionseg    *prev;

  void *operator new( size_t s )
  {
    size_t dummy;
    void *p = PoolAlloc( s, &dummy );
    if( p == NULL ) throw PoolAllocError();
    return(p);
  }
  void operator delete( void *p, size_t s )
  {
    if( p != 0 ) PoolFree( p, s );
  }

  // musn't be copied (because of the destructor)
private:
  intersectionseg( const intersectionseg& other );  
  intersectionseg& operator=( const intersectionseg& other );
};

/*--------------------------------------------------------------------
  Events for Event queue of planesweep algorithm
---------------------------------------------------------------------*/

struct eventrec;

struct linerec  // record for lines formed by one or more overlapping 
{               // line segments
  point2<rational>                     B;
  point2<rational>                     E;
  point2<rational>                     Borg;
  gugr::line                      l;
  Map<eventrec>::Node             endev; 
  ListNode< Map<linerec>::Node > *endev_node;

  List< ListNode<segment *> >     S;
  RefMap<intersection>            I;
  
  linerec( segment *s )
  {
    B = Borg = s->B; E = s->E; l = s->l;
    S.Append(new ListNode<segment *>(s));
  }
  ~linerec()
  {
    S.DeleteElems();
    I.DeleteElems();
  }

  void *operator new( size_t s )
  {
    size_t dummy;
    void *p = PoolAlloc( s, &dummy );
    if( p == NULL ) throw PoolAllocError();
    return(p);
  }
  void operator delete( void *p, size_t s )
  {
    if( p != 0 ) PoolFree( p, s );
  }

  // musn't be copied (because of the destructor)
private:
  linerec( const linerec& other );  
  linerec& operator=( const linerec& other );  
};

struct linepair
{
  Map<linerec>::Node L1;
  Map<linerec>::Node L2;  

  linepair() { }
  linepair(Map<linerec>::Node aL1, Map<linerec>::Node aL2)
  { L1 = aL1; L2 = aL2; }

  void *operator new( size_t s )
  {
    size_t dummy;
    void *p = PoolAlloc( s, &dummy );
    if( p == NULL ) throw PoolAllocError();
    return(p);
  }
  void operator delete( void *p, size_t s )
  {
    if( p != 0 ) PoolFree( p, s );
  }
};

/*----------------------------------------------------------------------
  Event record for planesweep algorithm
----------------------------------------------------------------------*/
struct eventrec
{
  point2<rational> key;
  List< ListNode<segment *> >            BV;
  List< ListNode<segment *> >            B;
  List< ListNode< Map<linerec>::Node > > E;
  List<ListNode<linepair> >              I;
  linerec *                              EV;

  eventrec( const point2<rational>& akey ) { key = akey; EV = 0; }
  ~eventrec()
  {
    BV.DeleteElems();
    B.DeleteElems();
    E.DeleteElems();
    I.DeleteElems();
  }  
  bool IsEmpty()
  {
    return( (BV.nElems == 0) && (B.nElems == 0) && E.IsEmpty() &&
            (I.nElems == 0) && (EV == 0) );
  }
  void *operator new( size_t s )
  {
    size_t dummy;
    void *p = PoolAlloc( s, &dummy );
    if( p == NULL ) throw PoolAllocError();
    return(p);
  }
  void operator delete( void *p, size_t s )
  {
    if( p != 0 ) PoolFree( p, s );
  }

  // musn't be copied (because of the destructor)
private:
  eventrec( const eventrec& other );  
  eventrec& operator=( const eventrec& other );
};

/*----------------------------------------------------------------------
  Tree for storing intervalls with a fixed set of abscissa 
  (Interval Tree, see Preparata/Shamos)
----------------------------------------------------------------------*/

int compare_pointer_to_pointer( void *p1, void *p2 );

struct segnode
{
public:
  int m_il;   // index of left bound of intervall
  int m_ir;   // index of right bound of intervall

  segnode *m_left;
  segnode *m_right;
  segnode *m_parent;

  RefMap<segment> m_segs;     // segments that contain this standard intervall

  segnode( int left, int right, segnode *parent )
  {
    m_il = left;
    m_ir = right;
    
    m_parent = parent;
    
    if( right - left > 1 )
    {
      m_left = new segnode( left, (left + right)/2, this );
      m_right = new segnode( (left + right)/2, right, this );
    }
    else
      m_left = m_right = 0;
  }
  ~segnode()
  {
    delete m_left;
    delete m_right;

    m_segs.DeleteElems();
  }
  void *operator new( size_t s )
  {
    size_t dummy;
    void *p = PoolAlloc( s, &dummy );
    if( p == NULL ) throw PoolAllocError();
    return(p);
  }
  void operator delete( void *p, size_t s )
  {
    if( p != 0 ) PoolFree( p, s );
  }
  void insert( int beg, int end, segment *seg )
  {
    gul::Assert<gul::InternalError>( ndebug || (beg != end) );

    if( (beg <= m_il) && (m_ir <= end) )
    {
      int side;
      RefMap<segment>::Node node,node1;

      side = m_segs.SearchNode( seg, 
             (int (*)(segment *, segment *))compare_pointer_to_pointer, &node );
      if( side == 0 ) throw InternalError();

      node1 = m_segs.NewNode(seg);

      m_segs.InsertNode( node1, node, side );
    } 
    else
    {
      if( beg < (m_il + m_ir)/2 )
        m_left->insert( beg, end, seg );
      if( end > (m_il + m_ir)/2 )
        m_right->insert( beg, end, seg );
    }
  }
  void remove( int beg, int end, segment *seg )
  {
    if( (beg <= m_il) && (m_ir <= end) )
    {
      int side;
      RefMap<segment>::Node node;

      side = m_segs.SearchNode( seg, 
             (int (*)(segment *, segment *))compare_pointer_to_pointer, &node );
      if( side != 0 ) throw InternalError();

      m_segs.RemoveNode( node );
      m_segs.FreeNode( node );
    } 
    else
    {
      if( beg < (m_il + m_ir)/2 )
        m_left->remove( beg, end, seg );
      if( end > (m_il + m_ir)/2 )
        m_right->remove( beg, end, seg );
    }
  }
  void leaves_to_array( int *nL, Ptr<segnode *> *L )
  {
    if( m_left == 0 )
    {
      (*L)[*nL] = this;
      (*nL)++;
    }
    else
    {
      m_left->leaves_to_array( nL, L );
      m_right->leaves_to_array( nL, L );
    }  
    return;
  }
};

struct segtree
{
public:
  int      m_nabsz;
  Ptr<intersection *>   m_absz;
  segnode *m_root;

  segtree( )
  {
    m_nabsz = 0;
    m_root = 0;
  }
  segtree( int nabsz, Ptr<intersection *> abszissa )
  {
    m_nabsz = nabsz;
    m_absz = abszissa;

    m_root = new segnode(0, m_nabsz-1, 0 );
  }
  ~segtree()
  {
    delete m_root;
  }
  void init( int nabsz, Ptr<intersection *> abszissa )
  {
    delete m_root;
    
    m_nabsz = nabsz;
    m_absz = abszissa;

    m_root = new segnode(0, m_nabsz-1, 0 );
  }
  void insert( int beg, int end, segment *seg )
  {
    m_root->insert( beg, end, seg );
  }
  int leaves_to_array( Ptr<segnode *> *L )
  {
    int nL = 0;

    if( m_nabsz > 0 )
    {
      int maxn = (int)(ceil(log((double)m_nabsz)/log(2.0))*2.0) + 2;
      (*L).reserve_pool( maxn );
      if( m_root )
        m_root->leaves_to_array( &nL, L );
    }
    return nL;
  }
};

/*---------------------------------------------------------------------
  Determine all intersections of a set of line segments

  Remarks: This function currently just creates a graph with intersections
  (points and segments) only inserted once.
  This isn't very useful alone, but at least, when used in the NURBS
  trimming code, it avoids crashes when a graph with intersecting trim
  contours is regularized (but the resulting triangulated graph is still
  nonsense, since the face flags of the edges of the overlapping trim
  contours are inconsistent). 

----------------------------------------------------------------------*/

void DoIntersectSegments( int nsegs, Map<eventrec>& EvQ, 
                        gugr::graph_edge_list *E, gugr::graph_vertex_list *V );


// forward reference, needed for inline definition

int compare_point_to_eventrec( point2<rational> *C, eventrec *E );


inline void IntersectSegments( int nsegs, Ptr<segment> segs, 
                        gugr::graph_edge_list *E, gugr::graph_vertex_list *V )
{
  gul::Map<eventrec> EvQ;
  int i,side;
  gul::Map<eventrec>::Node enode,enode1;

  /*
  cout << "PLANESWEEP\n";
  cout << "==========\n";
  cout << "INPUT SEGMENTS\n";
  for( i = 0; i < nsegs; i++ )
    DumpPS<float>::dump_segment( &segs[i] );
  */  

  /*--- initialize event queue with the lines leftmost endpoints ---*/

  for( i = 0; i < nsegs; i++ )
  {
    side = EvQ.SearchNode( &segs[i].B, compare_point_to_eventrec, &enode );
    if( side != 0 )
    {
      enode1 = EvQ.NewNode( segs[i].B );
      EvQ.InsertNode( enode1, enode, side );
      enode = enode1;
    }
    if( segs[i].l.IsVertical() )
      enode.key()->BV.Append( new ListNode<segment *>(&segs[i]) );    
    else
      enode.key()->B.Append( new ListNode<segment *>(&segs[i]) );    
  }

  DoIntersectSegments( nsegs, EvQ, E, V );
}

inline void ISDeleteOwnerMaps( gugr::graph_edge_list &E )
{
  graph_edge *e = E.First(); 

  while( e )
  {
    delete (gul::RefMap<void> *)e->f[0].p;
    e->f[0].p = 0;
    delete (gul::RefMap<void> *)e->f[1].p;
    e->f[1].p = 0;

    e = e->next;
  }
}

inline void ISDeleteBackpointers( gugr::graph_edge_list& E )
{
  graph_edge *e;
  gul::List< gul::ListNode< gul::ListNodeInfo< gul::ListNode<graph_edge *> 
                                                                     > > > *L;

  e = E.First();
  while( e )         // delete backpointer lists
  {
    L = (gul::List< gul::ListNode< gul::ListNodeInfo< 
                  gul::ListNode<graph_edge *> > > > *)e->reserved[1].p;
    L->DeleteElems();
    delete L; 
    e->reserved[1].p = 0;

    e = e->next;
  }
}

/*------------------------------------------------------------------------
  DEBUGGING STUFF
  output functions, just for debugging
------------------------------------------------------------------------*/
// #ifndef NDEBUG
template< class T >
class DumpPS
{
public:
  GULAPI static T orgx,orgy,scalex,scaley; 
public:
  static void set_transformation( T aorgx, T aorgy, T ascalex, T ascaley )
  {
    orgx = aorgx; 
    orgy = aorgy;
    scalex = ascalex;
    scaley = ascaley;
  }
  static void dump_intersection( intersection *i )
  {
    double dx1,dy1;
    T x1,y1;
    ListNode<segment *> *snode;
  
    if( i != NULL )
    {
      i->I.x.dump(dx1);
      i->I.y.dump(dy1);
      x1 = (T)dx1;
      y1 = (T)dy1; 

      x1 = cnv2coord<T>(x1)*scalex + orgx; 
      y1 = cnv2coord<T>(y1)*scaley + orgy;  
      cout << "INTERSECTION POINT\n";
      cout << (void *)i << ": (" <<
              std::setprecision(8) << x1 << ", " << y1 << ")\n";

      cout << "owner segments = {";
      snode = i->S.First();
      if( snode != 0 )
      {
        cout << (void *)snode->el;
        snode = snode->next;
        while( snode != 0 )
        {
          cout << ", " << (void *)snode->el;
          snode = snode->next;
        }
      }  
      cout << "}\n"; 
    }
    std::cout.flush();
  }
  static void dump_intersections( List<intersection>& Ipts )
  {
    intersection *i = Ipts.First();
    while( i != 0 )
    {
//      if( i->S.nElems > 1 )  /* if i is a real intersection */
        dump_intersection(i);
      i = i->next;  
    }
  }
  static void dump_linerec( linerec *L )
  {
    double dx1,dx2,dy1,dy2;
    T x1,x2,y1,y2;
    RefMap<intersection>::Node ir;
    ListNode<segment *> *snode;
    
    cout << "LINEREC\n";    
    L->Borg.x.dump(dx1);
    L->Borg.y.dump(dy1);
    L->E.x.dump(dx2);
    L->E.y.dump(dy2);

    x1 = (T)dx1; x2 = (T)dx2; y1 = (T)dy1; y2 = (T)dy2;
      
    x1 = cnv2coord<T>(x1)*scalex + orgx; 
    x2 = cnv2coord<T>(x2)*scalex + orgx; 
    y1 = cnv2coord<T>(y1)*scaley + orgy; 
    y2 = cnv2coord<T>(y2)*scaley + orgy; 

    cout << std::setprecision(8) << "(" << x1 << ", " << y1 << "), " <<
         "(" << x2 << ", " << y2 << ")\n";
    cout.flush();

    cout << "segments = {";
    snode = L->S.First();
    if( snode )
    {
      cout << (void *)snode->el;
      snode = snode->next;
      while( snode )
      {
        cout << ", " << (void *)snode->el;
        snode = snode->next;
      }
    }  
    cout << "}\n"; 

    ir = L->I.First();
    while( !ir.IsEmpty() )
    {
      dump_intersection( ir.key() );
      ir = L->I.Successor( ir );
    }
  }
  static void dump_segment( segment *S )
  {
    double dx1,dx2,dy1,dy2;
    T x1,x2,y1,y2;

    std::cout << "SEGMENT ";    
    S->B.x.dump(dx1);
    S->B.y.dump(dy1);
    S->E.x.dump(dx2);
    S->E.y.dump(dy2);

    x1 = (T)dx1; x2 = (T)dx2; y1 = (T)dy1; y2 = (T)dy2;
      
    x1 = cnv2coord<T>(x1)*scalex + orgx; 
    x2 = cnv2coord<T>(x2)*scalex + orgx; 
    y1 = cnv2coord<T>(y1)*scaley + orgy; 
    y2 = cnv2coord<T>(y2)*scaley + orgy; 

    std::cout << std::setprecision(8) << (void *)S << 
         ":(" << x1 << ", " << y1 << "), " <<
         "(" << x2 << ", " << y2 << "), L=" << S->f[0].p <<
         ", R=" << S->f[1].p << "\n";
    std::cout.flush();
  }
  static void dump_segments( List<ListNode<segment > >& L )
  {
    ListNode<segment> *sn;
    for( sn = L.First(); sn; sn = sn->next )
      dump_segment(&sn->el);
  }

  static void dump_intersectionseg( intersectionseg *i )
  {
    double dx1,dx2,dy1,dy2;
    T x1,x2,y1,y2;
    ListNode<segment *> *snode;

    cout << "INTERSECTION SEGMENT\n";    
    i->e->v[0]->v.v().m_x.Dump(dx1);
    i->e->v[0]->v.v().m_y.Dump(dy1);
    i->e->v[1]->v.v().m_x.Dump(dx2);
    i->e->v[1]->v.v().m_y.Dump(dy2);

    x1 = (T)dx1; x2 = (T)dx2; y1 = (T)dy1; y2 = (T)dy2;
      
    x1 = cnv2coord<T>(x1)*scalex + orgx; 
    x2 = cnv2coord<T>(x2)*scalex + orgx; 
    y1 = cnv2coord<T>(y1)*scaley + orgy; 
    y2 = cnv2coord<T>(y2)*scaley + orgy; 

    cout << std::setprecision(8) << (void *)i << 
         ": ((" << x1 << ", " << y1 << "), " <<
         "(" << x2 << ", " << y2 << "))\n";

    cout << "owner segments = {";
    snode = i->S.First();
    if( snode != 0 )
    {
      cout << (void *)snode->el;
      snode = snode->next;
      while( snode != 0 )
      {
        cout << ", " << (void *)snode->el;
        snode = snode->next;
      }
    }  
    cout << "}\n"; 

    cout.flush();
  }
  static void dump_intersectionsegs( List<intersectionseg>& Isegs )
  {
    intersectionseg *i = Isegs.First();
    while( i != 0 )
    {
      if( i->S.nElems > 1 )  /* if i is a real intersection */
        dump_intersectionseg(i);
      i = i->next;  
    }
  }

  static void dump_edge( graph_edge *e )
  {
    double dx1,dx2,dy1,dy2;
    T x1,x2,y1,y2;
    RefMap<void> *owners;
    RefMap<void>::Node owner;

    e->v[0]->v.v().m_x.Dump(dx1);
    e->v[0]->v.v().m_y.Dump(dy1);
    e->v[1]->v.v().m_x.Dump(dx2);
    e->v[1]->v.v().m_y.Dump(dy2);

    x1 = (T)dx1; x2 = (T)dx2; y1 = (T)dy1; y2 = (T)dy2;
      
    x1 = cnv2coord<T>(x1)*scalex + orgx; 
    x2 = cnv2coord<T>(x2)*scalex + orgx; 
    y1 = cnv2coord<T>(y1)*scaley + orgy; 
    y2 = cnv2coord<T>(y2)*scaley + orgy; 

    cout << (void *)e << "((" << x1 << "," << y1 << "),(" << x2 << "," << y2 <<
         ")) ";

    cout << "L={";
    owners = (RefMap<void> *)e->f[0];
    owner = owners->First();
    if( !owner.IsEmpty() )
    {
      cout << (void *)owner.key();
      owner = owners->Successor(owner);
      while( !owner.IsEmpty() )
      {
        cout << "," << (void *)owner.key(); 
        owner = owners->Successor(owner);
      }
    }
    cout << "}, R={";
    owners = (RefMap<void> *)e->f[1];
    owner = owners->First();
    if( !owner.IsEmpty() )
    {
      cout << (void *)owner.key();
      owner = owners->Successor(owner);
      while( !owner.IsEmpty() )
      {
        cout << "," << (void *)owner.key(); 
        owner = owners->Successor(owner);
      }
    }
    cout << "}\n";
  }
  static void dump_edges( graph_edge_list& E )
  {
    graph_edge *e = E.First();
    while( e != 0 )
    {
      dump_edge(e);
      e = e->next;  
    }
  }

  static void dump_point( const gul::point2<guar::rational>& P )
  {
    double dx,dy;
    T tx,ty;

    P.x.dump(dx);
    P.y.dump(dy);
  
    tx = (T)dx; 
    ty = (T)dy;
      
    tx = cnv2coord<T>(tx)*scalex + orgx; 
    ty = cnv2coord<T>(ty)*scaley + orgy; 

    std::cout << "(" << tx << ", " << ty << ")\n";
  }

};
// #endif


inline void IntersectSegments( gul::List< gul::ListNode<segment> >& segs, 
                        gugr::graph_edge_list *E, gugr::graph_vertex_list *V,
                        bool need_backpointers )
{
  gul::Map<eventrec> EvQ;
  int side;
  gul::Map<eventrec>::Node enode,enode1;
  segment *s;
  ListNode<segment> *sn;

  /*--- initialize event queue with the lines leftmost endpoints ---*/

  // gugr::DumpPS<float>::dump_segments( segs );

  sn = segs.First();

  while( sn )
  {
    s = &sn->el;

    side = EvQ.SearchNode( &s->B, compare_point_to_eventrec, &enode );
    if( side != 0 )
    {
      enode1 = EvQ.NewNode( s->B );
      EvQ.InsertNode( enode1, enode, side );
      enode = enode1;
    }
    if( s->l.IsVertical() )
      enode.key()->BV.Append( new ListNode<segment *>(s) );    
    else
      enode.key()->B.Append( new ListNode<segment *>(s) );    

    sn = sn->next;
  }

  DoIntersectSegments( segs.nElems, EvQ, E, V );

  if( !need_backpointers )
  {
    ISDeleteBackpointers( *E );
  }
}


}

#endif

---