---

gugr_planesweep.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 "gul_error.h"
#include "guar_exact.h"
#include "guma_sorting.h"
#include "gugr_basics.h"
#include "gugr_planesweep.h"
#include "gul_io.h"
#include "gul_std.h"
#include "gugr_io.h"

namespace gugr {

using gul::ndebug;
/* using gul::Assert; */
using guar::rational;
using gul::ListNodeInfo;
using std::cout;

// #ifndef NDEBUG
#ifdef __BORLANDC__
  template float DumpPS<float>::orgx;
  template float DumpPS<float>::orgy;
  template float DumpPS<float>::scalex;
  template float DumpPS<float>::scaley;
  template double DumpPS<double>::orgx;
  template double DumpPS<double>::orgy;
  template double DumpPS<double>::scalex;
  template double DumpPS<double>::scaley;
#else
  GULAPI float DumpPS<float>::orgx;
  GULAPI float DumpPS<float>::orgy;
  GULAPI float DumpPS<float>::scalex;
  GULAPI float DumpPS<float>::scaley;
  GULAPI double DumpPS<double>::orgx;
  GULAPI double DumpPS<double>::orgy;
  GULAPI double DumpPS<double>::scalex;
  GULAPI double DumpPS<double>::scaley;
#endif
// #endif

int compare_point_to_linerec( point2<rational> *P, linerec *L )
{
  return DetermineOrientation( L->B, L->E, *P );
}
int compare_linerec_to_linerec( linerec *L1, linerec *L2 )
{
  int sign = DetermineOrientation(L2->B, L2->E, L1->B );
  if( sign == 0 )
    sign = DetermineOrientation(L2->B, L2->E, L1->E );
  return sign;
}
int compare_point_to_eventrec( point2<rational> *C, eventrec *E )
{
  int sign = compare( C->x, E->key.x );
  if( sign == 0 ) sign = compare( C->y, E->key.y );
  return sign;
}
int compare_segment_to_linerec( segment *S, linerec *L )
{
  int sign = DetermineOrientation( L->B, L->E, S->B );
  if( sign == 0 ) sign = DetermineOrientation( L->B, L->E, S->E );
  return sign;
}
int hcompare_point_to_intersection( point2<rational> *C, intersection *R )
{
  return compare( C->x, R->I.x );
}
int vcompare_point_to_intersection( point2<rational> *C, intersection *R )
{
  return compare( C->y, R->I.y );
}
int compare_pointer_to_pointer( void *p1, void *p2 )
{
  if( p1 < p2 ) return -1;
  else if( p1 == p2 ) return 0;
  return 1;
}



/*---------------------------------------------------------------------
  Calculates the intersection of two linerecs (not vertical) equal to or right
  from 'xleft'. If one exists, a reference to this intersection is added to
  both linerecs. Furthermore a new intersection event is added to the
  event queue (if intersecion x !=xleft) and a new intersection record is
  added to the list of intersections if the intersection was not recorded before
----------------------------------------------------------------------*/

intersection *intersect( Map<linerec>::Node L1, Map<linerec>::Node L2, 
                         const rational& xleft, Map<eventrec> *EvQ,
                         List<intersection> *Ipts )
{
  const rational& x0 = L1.key()->l.v().x;
  const rational& y0 = L1.key()->l.v().y;
  const rational& dy = L1.key()->l.dy();
  const rational& e  = L1.key()->E.x;
  const rational& X0 = L2.key()->l.v().x;
  const rational& Y0 = L2.key()->l.v().y;
  const rational& DY = L2.key()->l.dy();
  const rational& E  = L2.key()->E.x;
  rational d;
  point2<rational> I;
  int sign,bsign,side1,side2;
  RefMap<intersection>::Node irnode1, irnode2, irnode;
  intersection *i;
  int side;
  Map<eventrec>::Node enode,enode1;
    
  d = DY - dy;
  sign = d.test();
  if( sign == 0 ) return 0;
  
  I.x = (y0 - Y0 + X0*DY - x0*dy) / d;

  bsign = compare( I.x, xleft );
  if( bsign < 0 ) return 0;
  sign = compare( I.x, e );
  if( sign > 0 ) return 0;
  sign = compare( I.x, E );
  if( sign > 0 ) return 0;

  I.y = y0 + (I.x-x0)*dy;

  side1 = L1.key()->I.SearchNode(
                             &I, hcompare_point_to_intersection, &irnode1 );
  side2 = L2.key()->I.SearchNode( 
                             &I, hcompare_point_to_intersection, &irnode2 );
  if( side1 == 0 ) 
    i = irnode1.key();
  else if( side2 == 0 )
    i = irnode2.key();
  else
  {
    i = new intersection( I );
    Ipts->Append(i);
  }

  if( side1 != 0 )
  {
    irnode = L1.key()->I.NewNode(i);
    L1.key()->I.InsertNode( irnode, irnode1, side1 );
  }
  if( side2 != 0 )
  {
    irnode = L2.key()->I.NewNode(i);
    L2.key()->I.InsertNode( irnode, irnode2, side2 );
  }

  if( bsign == 0 ) return i;

  side = EvQ->SearchNode( &I, compare_point_to_eventrec, &enode );
  if( side != 0 )
  {
    enode1 = EvQ->NewNode( I );
    EvQ->InsertNode( enode1, enode, side ); 
    enode = enode1;
  }
  enode.key()->I.Append( new ListNode<linepair>( linepair(L1,L2) ) );    

  return i;
}


intersection *intersect_vert( linerec *vL, Map<linerec>::Node L,
                              List<intersection> *Ipts )
{
  const rational& X0 = L.key()->l.v().x;
  const rational& Y0 = L.key()->l.v().y;
  const rational& DY = L.key()->l.dy();
  const rational& yleft = vL->B.y;
  const rational& yright = vL->E.y;
  const rational& x0 = vL->l.v().x;

  point2<rational> I;
  int sign,side1,side2;
  RefMap<intersection>::Node irnode1, irnode2, irnode;
  intersection *i;
    
  I.y = Y0 + (x0 - X0)*DY;
  
  sign = compare( I.y, yleft );
  if( sign < 0 ) return 0;
  sign = compare( I.y, yright );
  if( sign > 0 ) return 0;
 
  I.x = x0;
  
  side1 = vL->I.SearchNode(
                             &I, vcompare_point_to_intersection, &irnode1 );
  side2 = L.key()->I.SearchNode( 
                             &I, hcompare_point_to_intersection, &irnode2 );
  if( side1 == 0 ) 
    i = irnode1.key();
  else if( side2 == 0 )
    i = irnode2.key();
  else
  {
    i = new intersection( I );
    Ipts->Append(i);
  }

  if( side1 != 0 )
  {
    irnode = vL->I.NewNode(i);
    vL->I.InsertNode( irnode, irnode1, side1 );
  }
  if( side2 != 0 )
  {
    irnode = L.key()->I.NewNode(i);
    L.key()->I.InsertNode( irnode, irnode2, side2 );
  }

  return i;
}

/* --------------------------------------------------------------------
  finally process a (not vertical) linerec. The intersections between
  the segments on this line are calculated. These interesctions and
  intersections with other linerecs are added as vertices and edges
  to a graph and are also logged in lists containing all intersections 
----------------------------------------------------------------------*/

void finish_line( linerec *L, graph_edge_list *E, graph_vertex_list *V, 
                  int maxE, List<intersection> *Ipts, 
                  List<intersectionseg> *Isegs )
{
  ListNode<segment *> *segref = L->S.First();
  segment *seg;
  int side;
  intersection *i,*i1,*i2;
  intersectionseg *is;
  RefMap<intersection>::Node irnode,irnode1;
  Ptr<intersection *> I;
  int nI,j;
  segtree SegTr;
  int left,right,mid,iB,iE,sign,nLf;
  Ptr<segnode *> Lf;
  segnode *snode;
  RefMap<segment>::Node segnod;
  graph_edge *e;
  RefMap<void>::Node leftowner,rightowner,leftowner1,rightowner1;
  RefMap<void> *leftowners,*rightowners;
  List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > > *ownerrecs;
  ListNode< ListNodeInfo< ListNode<graph_edge *> > > *orec;
  ListNode<graph_edge *> *erec;

  while( segref != 0 )
  {
    seg = segref->el;

    /* --- add segment endpoints as intersections --- */

    side = L->I.SearchNode( &seg->B, hcompare_point_to_intersection, 
                            &irnode );
    if( side != 0 )
    {
      i = new intersection( seg->B );
      Ipts->Append(i);

      irnode1 = L->I.NewNode(i);
      L->I.InsertNode( irnode1, irnode, side );
    }

    side = L->I.SearchNode( &seg->E, hcompare_point_to_intersection, 
                            &irnode );
    if( side != 0 )
    {
      i = new intersection( seg->E );
      Ipts->Append(i);

      irnode1 = L->I.NewNode(i);
      L->I.InsertNode( irnode1, irnode, side );
    }    

    segref = segref->next;
  }

  nI = L->I.ConvertToArray( &I );

  SegTr.init( nI, I );

  segref = L->S.First();

  while( segref != 0 )
  {
    seg = segref->el;

    left = 0;
    right = nI;
    mid = (left+right)/2;

    for(;;)
    {  
      sign = compare( seg->B.x, I[mid]->I.x );
      if( sign == 0 )
        break;
      else if( sign < 0 )
      {
        right = mid;
        mid = (left+right)/2;
      }
      else
      {
        left = mid;
        mid = (left+right)/2;
      }
    }
    iB = mid;

    left = 0;
    right = nI;
    mid = (left+right)/2;

    for(;;)
    {  
      sign = compare( seg->E.x, I[mid]->I.x );
      if( sign == 0 )
        break;
      else if( sign < 0 )
      {
        right = mid;
        mid = (left+right)/2;
      }
      else
      {
        left = mid;
        mid = (left+right)/2;
      }
    }
    iE = mid;

    SegTr.insert( iB, iE, seg );

    segref = segref->next;
  }

  nLf = SegTr.leaves_to_array( &Lf );

  for( j = 0; j < nLf; j++ )
  {
    e = new graph_edge;
    E->Append(e);
    
    i1 = SegTr.m_absz[Lf[j]->m_il];
    if( i1->v == 0 )
    {
      i1->v = new graph_vertex( i1->I, 0 );
      V->Append(i1->v);
    }
    i2 = SegTr.m_absz[Lf[j]->m_ir];
    if( i2->v == 0 )
    {
      i2->v = new graph_vertex( i2->I, 0 );
      V->Append(i2->v);
    }
    e->v[0] = i1->v;
    e->v[1] = i2->v;
    e->l = L->l; 

    /* --- set owner lists of intersections --- */

    is = new intersectionseg(e);
    Isegs->Append(is);

    /* initialize sets of owners of left and right side of the edge */

    leftowners = new RefMap<void>;
    rightowners = new RefMap<void>;
    e->f[0].p = leftowners;
    e->f[1].p = rightowners;
    e->reserved[0].set_i(0);
    ownerrecs = new List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > >;
    e->reserved[1].p = ownerrecs;

    snode = Lf[j];
    while( snode )
    {
      segnod = snode->m_segs.First();
 
      while( !segnod.IsEmpty() )
      {
        // increment number of owners by the multiplicity of the segments
        // which contain the edge

        e->reserved[0].i += segnod.key()->m;

        /* add owner to the set of owners of the left side of the edge */

        side = leftowners->SearchNode( (void *)segnod.key()->f[0].p,
                                     compare_pointer_to_pointer, &leftowner );
        if( side != 0 )
        {
          leftowner1 = leftowners->NewNode((void *)segnod.key()->f[0].p);
          leftowners->InsertNode( leftowner1, leftowner, side );
        }

        /* add owner to the set of owners of the right side of the edge */

        side = rightowners->SearchNode( (void *)segnod.key()->f[1].p,
                                     compare_pointer_to_pointer, &rightowner );
        if( side != 0 )
        {
          rightowner1 = rightowners->NewNode((void *)segnod.key()->f[1].p);
          rightowners->InsertNode( rightowner1, rightowner, side );
        }

        /* add edge to the list of edges for the original input segment */

        erec = new ListNode<graph_edge *>(e);
        segnod.key()->e.Append( erec );

        /* add a backpointer to the corresponding edge record in the edge
           list of the input segment; this makes it later possible to remove
           all references to an edge from all input segments */

        orec = new ListNode< ListNodeInfo< ListNode<graph_edge *> > >(
               ListNodeInfo< ListNode<graph_edge *> >(&segnod.key()->e, erec) );
        ownerrecs->Append(orec);

        /* the owner lists of the intersection records are only for debugging */
        /*
        owner = new ListNode<segment *>(segnod.key());
        i1->S.Append(owner);
        owner = new ListNode<segment *>(segnod.key());
        is->S.Append(owner);
        */
        segnod = snode->m_segs.Successor(segnod);
      }
      snode = snode->m_parent;
    }  
    
    OrientEdge( e );
    ConnectEdge( e, maxE );
  }

  /* --- set owner list of endpoint - intersection --- */
  /*
  if( (j=nLf-1) >= 0 )
  {
    snode = Lf[j];
    while( snode )
    {
      segnod = snode->m_segs.First();
      while( !segnod.IsEmpty() )
      {
        owner = new ListNode<segment *>(segnod.key());
        i2->S.Append(owner);
        segnod = snode->m_segs.Successor(segnod);
      }
      snode = snode->m_parent;
    }
  }
  */
}


/* --------------------------------------------------------------------
  finally process a (vertical) linerec. The intersections between
  the segments on this line are calculated. These interesctions and
  intersections with other linerecs are added as vertices and edges
  to a graph and are also logged in lists containing all intersections 
  (special version for vertical linerecs, almost the same as the above
  function)
----------------------------------------------------------------------*/

void finish_vertline( linerec *L, graph_edge_list *E, graph_vertex_list *V, 
                  int maxE, List<intersection> *Ipts, 
                  List<intersectionseg> *Isegs )
{
  ListNode<segment *> *segref = L->S.First();
  segment *seg;
  int side;
  intersection *i,*i1,*i2;
  intersectionseg *is;
  RefMap<intersection>::Node irnode,irnode1;
  Ptr<intersection *> I;
  int nI,j;
  segtree SegTr;
  int left,right,mid,iB,iE,sign,nLf;
  Ptr<segnode *> Lf;
  segnode *snode;
  RefMap<segment>::Node segnod;
  graph_edge *e;
  RefMap<void>::Node leftowner,rightowner,leftowner1,rightowner1;
  RefMap<void> *leftowners,*rightowners;
  List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > > *ownerrecs;
  ListNode< ListNodeInfo< ListNode<graph_edge *> > > *orec;
  ListNode<graph_edge *> *erec;
 
  while( segref != 0 )
  {
    seg = segref->el;

    /* --- add segment endpoints as intersections --- */

    side = L->I.SearchNode( &seg->B, vcompare_point_to_intersection, 
                            &irnode );
    if( side != 0 )
    {
      i = new intersection( seg->B );
      Ipts->Append(i);

      irnode1 = L->I.NewNode(i);
      L->I.InsertNode( irnode1, irnode, side );
    }

    side = L->I.SearchNode( &seg->E, vcompare_point_to_intersection, 
                            &irnode );
    if( side != 0 )
    {
      i = new intersection( seg->E );
      Ipts->Append(i);

      irnode1 = L->I.NewNode(i);
      L->I.InsertNode( irnode1, irnode, side );
    }    

    segref = segref->next;
  }

  nI = L->I.ConvertToArray( &I );

  SegTr.init( nI, I );

  segref = L->S.First();

  while( segref != 0 )
  {
    seg = segref->el;

    left = 0;
    right = nI;
    mid = (left+right)/2;

    for(;;)
    {  
      sign = compare( seg->B.y, I[mid]->I.y );
      if( sign == 0 )
        break;
      else if( sign < 0 )
      {
        right = mid;
        mid = (left+right)/2;
      }
      else
      {
        left = mid;
        mid = (left+right)/2;
      }
    }
    iB = mid;

    left = 0;
    right = nI;
    mid = (left+right)/2;

    for(;;)
    {  
      sign = compare( seg->E.y, I[mid]->I.y );
      if( sign == 0 )
        break;
      else if( sign < 0 )
      {
        right = mid;
        mid = (left+right)/2;
      }
      else
      {
        left = mid;
        mid = (left+right)/2;
      }
    }
    iE = mid;

    SegTr.insert( iB, iE, seg );

    segref = segref->next;
  }

  nLf = SegTr.leaves_to_array( &Lf );

  for( j = 0; j < nLf; j++ )
  {
    e = new graph_edge;
    E->Append(e);
    
    i1 = SegTr.m_absz[Lf[j]->m_il];
    if( i1->v == 0 )
    {
      i1->v = new graph_vertex( i1->I, 0 );
      V->Append(i1->v);
    }
    i2 = SegTr.m_absz[Lf[j]->m_ir];
    if( i2->v == 0 )
    {
      i2->v = new graph_vertex( i2->I, 0 );
      V->Append(i2->v);
    }
    e->v[0] = i1->v;
    e->v[1] = i2->v;
    e->l = L->l; 

    /* --- set owner lists of intersections --- */

    is = new intersectionseg(e);
    Isegs->Append(is);

    /* initialize sets of owners of left and right side of the edge */

    leftowners = new RefMap<void>;
    rightowners = new RefMap<void>;
    e->f[0].p = leftowners;
    e->f[1].p = rightowners;
    e->reserved[0].set_i(0);
    ownerrecs = new List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > >;
    e->reserved[1].p = ownerrecs;

    snode = Lf[j];
    while( snode )
    {
      segnod = snode->m_segs.First();

      while( !segnod.IsEmpty() )
      {
        // increment number of owners by the multiplicity of the segments
        // which contain the edge

        e->reserved[0].i += segnod.key()->m;

        /* add owner to the set of owners of the left side of the edge */

        side = leftowners->SearchNode( (void *)segnod.key()->f[0].p,
                                     compare_pointer_to_pointer, &leftowner );
        if( side != 0 )
        {
          leftowner1 = leftowners->NewNode((void *)segnod.key()->f[0].p );
          leftowners->InsertNode( leftowner1, leftowner, side );
        }

        /* add owner to the set of owners of the right side of the edge */

        side = rightowners->SearchNode( (void *)segnod.key()->f[1].p,
                                     compare_pointer_to_pointer, &rightowner );
        if( side != 0 )
        {
          rightowner1 = rightowners->NewNode((void *)segnod.key()->f[1].p);
          rightowners->InsertNode( rightowner1, rightowner, side );
        }

        /* add edge to the list of edges for the original input segment */

        erec = new ListNode<graph_edge *>(e);
        segnod.key()->e.Append( erec );

        /* add a backpointer to the corresponding edge record in the edge
           list of the input segment; this makes it later possible to remove
           all references to an edge from all input segments */

        orec = new ListNode< ListNodeInfo< ListNode<graph_edge *> > >(
               ListNodeInfo< ListNode<graph_edge *> >(&segnod.key()->e, erec) );
        ownerrecs->Append(orec);

        /* the owner lists of the intersection records are only for debugging */
        /*
        owner = new ListNode<segment *>(segnod.key());
        i1->S.Append(owner);
        owner = new ListNode<segment *>(segnod.key());
        is->S.Append(owner);
        */

        segnod = snode->m_segs.Successor(segnod);
      }
      snode = snode->m_parent;
    }  
    
    OrientEdge( e );
    ConnectEdge( e, maxE );
  }

  /* --- set owner list of endpoint - intersection --- */
  /*
  if( (j=nLf-1) >= 0 )
  {
   snode = Lf[j];
    while( snode )
    {
      segnod = snode->m_segs.First();
      while( !segnod.IsEmpty() )
      {
        owner = new ListNode<segment *>(segnod.key());
        i2->S.Append(owner);
        segnod = snode->m_segs.Successor(segnod);
      }
      snode = snode->m_parent;
    }
  }
  */
}

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

  This function creates a graph with intersections (points and segments) only
  inserted once.

  For both sides of each created edge a set is calculated, which is the union
  of the segment/side owners ("segment.f[0/1]") of all input segments which
  contain this output edge. These sets are stored in the f[0/1] fields of
  the output edges (and the sum of the multiplicities of input segments which 
  contain this edge is stored in the reserved[0] field of the edge)
  The edges of the output graph which form an input segment are stored in
  the "segment.e" list of each input segment.

  So the following data structures are filled in by this function:
  
  segment.e        // list of created edges for this segment
  edge.f[0]        // set of owners of the left side of the edge
  edge.f[1]        // set of owners of the right side of the edge
  edge.reserved[0] // sum of multiplicities of input segments which contain this
                   // edge (used for odd/even winding rule for polygon filling)
  edge.reserved[1] // list of backpointers to the edge records of the input
                   // segments which refer to this edge

  (The pointers to the owner sets in edge.f[0] and edge.f[1] and the
  backpointer list in edge.reserved[1] are casted to int's, so they are not
  automatically freed in the destructor, the caller must do this manually 
  afterwards !!!!!)
----------------------------------------------------------------------*/


void DoIntersectSegments( int nsegs, Map<eventrec>& EvQ, 
                        gugr::graph_edge_list *E, gugr::graph_vertex_list *V )
{
  
  Map<eventrec>::Node enode,evnode,evnode1;
  int side,sign;
  ListNode<segment *> *begseg;
  Map<linerec> SwS;
  segment *seg;
  ListNode<Map<linerec>::Node> *lrefnode,*lstnode;
  Map<linerec>::Node lnode,lnodelo,lnodehi,lnode1,lnode2;
  linerec *vlin = 0, *lin;
  bool addvend,iflag,iexflag,checkneighbors;
  RefMap<intersection>::Node irnode, irnode1;
  intersection *irec;
  ListNode<linepair> *lpnode;
  linepair            lpair;
  List<intersection>     Ipts;
  List<intersectionseg>  Isegs;
  int maxE;
  
  maxE = nsegs*4;

  /*--- loop until event queue empty ---*/

  for(;;)
  {
    enode = EvQ.First();
    if( enode.IsEmpty() ) break;   // queue empty
    
    /*--- process starting vertical segments ---*/
 
    while( enode.key()->BV.nElems > 0 )
    {
      begseg = enode.key()->BV.First(); 
      enode.key()->BV.Remove( begseg );
      
      /*
      cout << "[processing starting vertical line segment]: ";
      DumpPS<float>::dump_segment( begseg->el );
      */

      addvend = false;
      if( vlin == 0 ) 
      {
        vlin = new linerec( begseg->el );
        delete begseg;
        addvend = true;
      }
      else
      {
        vlin->S.Append( begseg );  // add line-segment (using ex. list node)

        sign = compare( begseg->el->E.y, vlin->E.y );
        if( sign > 0 ) 
        {
          vlin->E = begseg->el->E;

          /* remove old vertical-line-end event */

          vlin->endev.key()->EV = 0;

          if( (vlin->endev.key()->IsEmpty()) && 
              (vlin->endev.key() != enode.key()) )
          {
            EvQ.RemoveNode( vlin->endev );
            EvQ.FreeNode( vlin->endev );
          }
          
          addvend = true;
        }
      }
      if( addvend )
      {
        /* add new vertical-line-end event */

        side = EvQ.SearchNode( &vlin->E, compare_point_to_eventrec, &evnode );
        if( side != 0 )
        {
          evnode1 = EvQ.NewNode( vlin->E );
          EvQ.InsertNode( evnode1, evnode, side );
          evnode = evnode1;
        }
        evnode.key()->EV = vlin;    
        vlin->endev = evnode;
      }
    }

    /* check if current event point is a intersection point */

    if( enode.key()->I.nElems > 0 )
      iexflag = true;
    else
      iexflag = false;

    if( iexflag ||
        ((vlin != 0) && (enode.key()->B.nElems > 0)) ||
        ((vlin != 0) && (!enode.key()->E.IsEmpty())) ||
        ((enode.key()->B.nElems > 0) && (!enode.key()->E.IsEmpty())) )
    {
      iflag = true;
      if( iexflag )
      {
        /* get the intersection record from one of two intersecting lines */

        lin = enode.key()->I.First()->el.L1.key();
        side = lin->I.SearchNode( &enode.key()->key, 
                           hcompare_point_to_intersection, &irnode );
        gul::Assert<InternalError>( ndebug || (side == 0) );

        irec = irnode.key();
      }
      else
      {
        /* create a new intersection record */

        irec = new intersection( enode.key()->key );
        Ipts.Append(irec);
      }
    }
    else
      iflag = false;

    /* --- add intersection to vertical line --- */
      
    if( vlin && iflag )
    {
      side = vlin->I.SearchNode(
                      &irec->I, vcompare_point_to_intersection, &irnode1 );
      if( side != 0 )
      {
        irnode = vlin->I.NewNode(irec);
        vlin->I.InsertNode( irnode, irnode1, side );
      }
    }

    /*--- process ending lines ---*/

    lrefnode = enode.key()->E.First(); 
    while( lrefnode != 0 )
    {
      /* first element in list of lines ending in current event point */

      lnode = lrefnode->el;
      lrefnode = lrefnode->next;

      if( iflag )
      {
        /* add intersection record (if not already existing) */

        side = lnode.key()->I.SearchNode( &irec->I, 
                                 hcompare_point_to_intersection, &irnode );
        if( side != 0 )
        {
          irnode1 = lnode.key()->I.NewNode(irec);
          lnode.key()->I.InsertNode( irnode1, irnode, side );
        }
      }

      lnodelo = SwS.Predecessor( lnode );  /* get neighbors in symetric order */
      lnodehi = SwS.Successor( lnode );
    
      SwS.RemoveNode( lnode );     /* remove ending line from symmetric order */

      /* intersect neighbors */ 

      if( !lnodelo.IsEmpty() && !lnodehi.IsEmpty() )
        intersect( lnodelo, lnodehi, enode.key()->key.x, &EvQ, &Ipts );
    }

    /* process intersecting lines */

    while( enode.key()->I.nElems > 0 )
    {
      lpnode = enode.key()->I.First(); 
      enode.key()->I.Remove( lpnode );
      lpair = lpnode->el;
      delete lpnode;       // free list node

      lnode1 = lpair.L1;
      lnode2 = lpair.L2;   
      
      if( !SwS.IsRemoved(lnode1) && !SwS.IsRemoved(lnode2) )
      {
        SwS.RemoveNode( lnode1 );
        SwS.RemoveNode( lnode2 );

        lnode1.key()->B = enode.key()->key;
        lnode2.key()->B = enode.key()->key;

        side = SwS.SearchNode( lnode1.key(), compare_linerec_to_linerec, 
                               &lnode ); 
        gul::Assert<InternalError>(ndebug | (side!=0) );

        SwS.InsertNode(lnode1,lnode,side);  // reinsert

        lnodelo = SwS.Predecessor( lnode1 );  /* get neighbors in order */
        lnodehi = SwS.Successor( lnode1 );

        if( !lnodelo.IsEmpty() )
          intersect( lnodelo, lnode1, enode.key()->key.x, &EvQ, &Ipts );
        if( !lnodehi.IsEmpty() )
          intersect( lnodehi, lnode1, enode.key()->key.x, &EvQ, &Ipts );

        side = SwS.SearchNode( lnode2.key(), compare_linerec_to_linerec, 
                               &lnode ); 
        gul::Assert<InternalError>(ndebug | (side!=0) );

        SwS.InsertNode(lnode2,lnode,side); // reinsert

        lnodelo = SwS.Predecessor( lnode2 );  /* get neighbors in order */
        lnodehi = SwS.Successor( lnode2 );

        if( !lnodelo.IsEmpty() )
          intersect( lnodelo, lnode2, enode.key()->key.x, &EvQ, &Ipts );
        if( !lnodehi.IsEmpty() )
          intersect( lnodehi, lnode2, enode.key()->key.x, &EvQ, &Ipts );
      }
    }

    /* process beginning lines */
    
    while( enode.key()->B.nElems > 0 )
    {
      begseg = enode.key()->B.First(); 
      enode.key()->B.Remove( begseg );
      seg = begseg->el;      
 
      side = SwS.SearchNode( seg, compare_segment_to_linerec, &lnode ); 
      if( side == 0 )  // colinear with existing line
      {
        lnode.key()->S.Append( begseg );  // add line-segment (using list node)

        sign = compare( begseg->el->E.x, lnode.key()->E.x );
        if( sign > 0 ) 
        {
          lnode.key()->E = begseg->el->E;
          
          /* remove old line-end event */

          lnode.key()->endev.key()->E.Remove( lnode.key()->endev_node );
          delete lnode.key()->endev_node;  // delete line-end lstnode

          if( lnode.key()->endev.key()->IsEmpty() )
          {
            EvQ.RemoveNode( lnode.key()->endev );
            EvQ.FreeNode( lnode.key()->endev );
          }
          
          checkneighbors = true;
        }
        else
        {
          checkneighbors = false;
        }
      }
      else
      {
        delete begseg; // delete list node;
        
        lnode1 = SwS.NewNode( seg );
        SwS.InsertNode( lnode1, lnode, side );
        lnode = lnode1;

        checkneighbors = true;
      }  

      if( checkneighbors )
      {      
        lnodelo = SwS.Predecessor( lnode );  /* get neighbors in order */
        lnodehi = SwS.Successor( lnode );

        lstnode = new ListNode< Map<linerec>::Node >(lnode);
        
        side = EvQ.SearchNode( &seg->E, compare_point_to_eventrec, &evnode ); 
        if( side != 0 )
        {
          evnode1 = EvQ.NewNode( seg->E );
          EvQ.InsertNode( evnode1, evnode, side );
          evnode = evnode1;
        }

        evnode.key()->E.Append( lstnode );

        lnode.key()->endev = evnode;
        lnode.key()->endev_node = lstnode;

        if( !lnodelo.IsEmpty() )
          intersect( lnodelo, lnode, enode.key()->key.x, &EvQ, &Ipts );
        if( !lnodehi.IsEmpty() )
          intersect( lnodehi, lnode, enode.key()->key.x, &EvQ, &Ipts );
      }

      if( iflag )
      {
        /* add intersection record (if not already existing) */

        side = lnode.key()->I.SearchNode( &irec->I, 
                                 hcompare_point_to_intersection, &irnode );
        if( side != 0 )
        {
          irnode1 = lnode.key()->I.NewNode(irec);
          lnode.key()->I.InsertNode( irnode1, irnode, side );
        }
      }
    }

    /* --- process end of vertical line --- */
    
    if( enode.key()->EV != 0 )
    {
      /* find linerecs passing between start and end of vertical line */

      if( !SwS.IsEmpty() )
      {
        side = SwS.SearchNode( &enode.key()->EV->B, compare_point_to_linerec, 
                             &lnode );
        if( side > 0 )
          lnode = SwS.Successor( lnode );

        do
        {
          if( !lnode.IsEmpty() )
          {
            irec = intersect_vert( vlin, lnode, &Ipts );
            lnode = SwS.Successor( lnode );
          }
        }
        while( !lnode.IsEmpty() && (irec != 0) );
      }
      
      // cout << "[before finish_vertline]: ";
      // DumpPS<float>::dump_linerec( enode.key()->EV );

      finish_vertline( vlin, E, V, maxE, &Ipts, &Isegs );

      delete vlin;       
      vlin = 0;
    }

    /* --- process finished lines --- */

    while( (lrefnode = enode.key()->E.First()) != 0 )
    {
      enode.key()->E.Remove( lrefnode );
      lnode = lrefnode->el;
      delete lrefnode;

      /*
      cout << "[before finish_line]: ";
      DumpPS<float>::dump_linerec( lnode.key() );
      */
      
      finish_line( lnode.key(), E, V, maxE, &Ipts, &Isegs );
      SwS.FreeNode(lnode);  // already removed, see above
    }

    EvQ.RemoveNode( enode );
    EvQ.FreeNode(enode);
  }

  /*
  gugr::Dump<float>::dump_vertices( V.head );
  gugr::Dump<float>::dump_edges( E.head );
  */

  /*  
  cout << "\nINTERSECTIONS\n";
  cout << "=============\n";
  DumpPS<float>::dump_intersections( Ipts );
  cout << "\n";
  DumpPS<float>::dump_intersectionsegs( Isegs );
  */

  Ipts.DeleteElems();
  Isegs.DeleteElems();
}

}

---