// Vorosweep - Copyright (C) 2010-2014 T. Mouton
//
// See the LICENSE.txt file for license information. Please report all
// bugs and problems to <thibaud.mouton@gmail.com>.

#include "vorosweep.h"
#include "border.h"

using namespace vorosweep;

void Graph::merge_and_go_right ( SweepEdge *se0, SweepEdge *se1, SweepFacet *right )
{
  dbgprintf ( 2, "--> right border merging\n" );
  // generate new edge
  double ndir[3];
  right->dir2d_to_dir3d ( se0->get_dir2d(), ndir );
  dbgprintf(2, "ndir --> %lf %lf %lf\n", ndir[0], ndir[1], ndir[2]);
  dbgprintf(2, "se1 is init --> %d\n", se1->is_init());

  if ( /*se1->is_init() && */ndir[2] >= 0.0 )
  {
    BorderSweepEdge *bse0 = static_cast<BorderSweepEdge *> ( se0 );
    Border *bo = bse0->get_border();
    Grid1d *bordergrid = bo->get_grid();
    dbgprintf ( 2, "--> creating new edge from edges %p %p with facet %p :\n", se0, se1, right );
    BorderSweepEdge *nse = new BorderSweepEdge ( se1->get_current(), ndir, get_time() );
    nse->set_border ( bo );
//     nse->set_generator ( right->get_generator() );
    nse->update_speeds ( right );
    FrontLine *fl1 = right->get_frontline();
    fl1->update_sweepedge ( se1, nse );
    int bgid = bordergrid->get_index ( nse->get_start()->p );
    Event *ne = econtainer->get();
    ne->init ( nse, bo, nse->get_start()->p, get_time(), Event::NEWBORDEREDGESWITCH, bgid );
    add_event ( ne );
    // add also switch event in grid for facet switch
    int gid = bucketgrid->get_index ( nse->get_start()->p );
    Event *next = next_edgeswitch ( nse, nse->get_start()->p, gid );
    dbgprintf ( 5, "--> next switch event add :\n" );
    add_event ( next );
//     return;
  }
  else
  {
    Front *fr1 = se1->get_front ( 1 );
    SweepEdge *seopp = fr1->get_sweepedge ( 1 );
    se1->merge_current ( seopp, get_time() );
    FrontLine *fl1 = fr1->get_frontline();
    fl1->close_front ( fr1 );
    seopp->set_stopped();
//     return;
  }
}

void Graph::merge_and_go_left ( SweepEdge *se0, SweepEdge *se1, SweepFacet *left )
{
  dbgprintf ( 2, "--> left border merging\n" );
  // generate new edge
  double ndir[3];
  left->dir2d_to_dir3d ( se1->get_dir2d(), ndir );
  dbgprintf(2, "ndir --> %lf %lf %lf\n", ndir[0], ndir[1], ndir[2]);
  dbgprintf(2, "se0 is init --> %d\n", se0->is_init());

  if ( /*se0->is_init() && */ndir[2] >= 0.0 )
  {
    BorderSweepEdge *bse1 = static_cast<BorderSweepEdge *> ( se1 );
    Border *bo = bse1->get_border();
    Grid1d *bordergrid = bo->get_grid();
    dbgprintf ( 2, "--> creating new edge from edges %p %p with facet %p :\n", se0, se1, left );
    BorderSweepEdge *nse = new BorderSweepEdge ( se0->get_current(), ndir, get_time() );
    nse->set_border ( bo );
//     nse->set_generator ( left->get_generator() );
    nse->update_speeds ( left );
    FrontLine *fl0 = left->get_frontline();
    fl0->update_sweepedge ( se0, nse );
    int bgid = bordergrid->get_index ( nse->get_start()->p );
    Event *ne = econtainer->get();
    ne->init ( nse, bo, nse->get_start()->p, get_time(), Event::NEWBORDEREDGESWITCH, bgid );
    add_event ( ne );
    // add also switch event in grid for facet switch
    int gid = bucketgrid->get_index ( nse->get_start()->p );
    Event *next = next_edgeswitch ( nse, nse->get_start()->p, gid );
    dbgprintf ( 5, "--> next switch event add :\n" );
    add_event ( next );
//     return;
  }
  else
  {
    Front *fr0 = se0->get_front ( 0 );
    SweepEdge *seopp = fr0->get_sweepedge ( 0 );
    se0->merge_current ( seopp, get_time() );
    // close the front
    FrontLine *fl0 = fr0->get_frontline();
    fl0->close_front ( fr0 );
    seopp->set_stopped();
//     return;
  }
}

// this function MUST be cleaned !!
int Graph::voronoi_vertex_merge ( SweepEdge *se0, SweepEdge *se1, double *ndir )
{
  // get the other edge
  SweepEdge *edge[2];

  Front *fr0 = se0->get_front ( 0 );
  Front *fr1 = se1->get_front ( 1 );

  edge[0] = fr0->get_sweepedge ( 0 );
  edge[1] = fr1->get_sweepedge ( 1 );

  if ( edge[0] == edge[1] ) // 3 point intersection case
  {
    dbgprintf ( 2, "--> stopping everything (3 edges)\n" );
    fr0->get_frontline()->close_front ( fr0 );
    fr1->get_frontline()->close_front ( fr1 );
    se0->merge_current ( edge[0], get_time() );
    edge[0]->set_stopped();
  }
  else // exotic cases
  {
    dbgprintf ( 2, "msf --> %p %p\n", se0->get_sweepfacet ( 0 ), se1->get_sweepfacet ( 1 ) );
    dbgprintf ( 2, "4 edge cases !!\n" );
    
    // extedge contains the extreme edge that meet at the same point as se0 and se1
    SweepEdge *extedge[2];
    extedge[0] = se0;
    extedge[1] = se1;

#if defined(DURTY)
    ////// THIS IS A DURTY PROCEDURE THAT SHOULD BE REMOVED !!! //////
    double crashpos[2];
    if ( geom::lines2d_intersection ( se0->get_start()->p, edge[0]->get_start()->p, se0->get_dir2d(), edge[0]->get_dir2d(), basic_grid::epsilon, crashpos ) )
    {
      dbgprintf ( 2, "--> found intersection : %lf\n", geom::distance2d ( se0->get_current()->p, crashpos ) );
      if ( geom::distance2d ( se0->get_current()->p, crashpos ) < 1e-12 )
      {
        dbgprintf ( 2, "--> closing another front\n" );
        se0->merge_current ( edge[0], get_time() );
        fr0->get_frontline()->close_front ( fr0 );
        edge[0]->update_current ( get_time() );
        edge[0]->set_stopped();
        extedge[0] = edge[0];
      }
    }
    if ( geom::lines2d_intersection ( se1->get_start()->p, edge[1]->get_start()->p, se1->get_dir2d(), edge[1]->get_dir2d(), basic_grid::epsilon, crashpos ) )
    {
      dbgprintf ( 2, "--> found intersection : %lf\n", geom::distance2d ( se1->get_current()->p, crashpos ) );
      if ( geom::distance2d ( se1->get_current()->p, crashpos ) < 1e-12 )
      {
        dbgprintf ( 2, "--> closing another front\n" );
        se1->merge_current ( edge[1], get_time() );
        fr1->get_frontline()->close_front ( fr1 );
        edge[1]->update_current ( get_time() );
        edge[1]->set_stopped();
        extedge[1] = edge[1];
      }      
    }
    dbgprintf ( 2, "extedge 0 --> %lf %lf dir %lf %lf\n", extedge[0]->get_start()->p[0], extedge[0]->get_start()->p[1], extedge[0]->get_dir2d() [0], extedge[0]->get_dir2d() [1] );
    dbgprintf ( 2, "extedge 1 --> %lf %lf dir %lf %lf\n", extedge[1]->get_start()->p[0], extedge[1]->get_start()->p[1], extedge[1]->get_dir2d() [0], extedge[1]->get_dir2d() [1] );
    ////// END OF THE DURTY PROCEDURE !!! //////
#endif


    // ultimate test --> get the fronts
    Front *fr0 = extedge[0]->get_front ( 0 );
    Front *fr1 = extedge[1]->get_front ( 1 );

    // case we merge 2 front of the same frontline
    if ( fr0 && fr1 && fr0->get_owner() == fr1->get_owner() )
    {
      FrontLine *fl0 = fr0->get_frontline();
      FrontLine *fl1 = fr1->get_frontline();
      
      ASSERT_ERROR(fl0 == fl1, "merging different frontline : %p %p\n", fl0, fl1);
      
      fl0->front_merge ( fr0, fr1 );
    }
    else
    {
      // we create 2 new edges
      new_facet ( se0, se1, ndir );
    }
  }
  return 1;
}

void Graph::new_facet ( SweepEdge *se0, SweepEdge *se1, double *ndir )
{
  se0->print();
  se1->print();

  SweepFacet *sf0 = se0->get_front ( 0 )->get_owner();
  SweepFacet *sf1 = se1->get_front ( 1 )->get_owner();

  sf0->print();
  sf1->print();

  // CounterClockWise
  if ( geom::cross_product2d ( sf1->get_original_sweepedge ( 0 )->get_dir2d(), ndir ) > 0.0 )
  {
    rotation_ccw ( se0, se1 );
  }
  else
  {
    rotation_cw ( se0, se1 );
  }
}

// this routine generate as much as facet as needed to circumvent obstacle
void Graph::rotation_ccw ( SweepEdge *see0, SweepEdge *see1 )
{
  dbgprintf ( 2, "--> COUNTERCLOCKWISE rotation\n" );
  SweepFacet *sf0 = see0->get_front ( 0 )->get_owner();
  SweepFacet *sf1 = see1->get_front ( 1 )->get_owner();
  Convex_generator *cg = sf1->get_generator();

  double time = get_time();
  int gid = bucketgrid->get_index ( see1->get_current()->p );

  double *normal = sf1->get_plane();
  double ndir[3];

  int index = sf1->get_pos();

  SweepEdge *lastse = NULL;
  SweepEdge *se0 = sf1->get_original_sweepedge ( 0 );
  SweepEdge *se1 = sf1->get_original_sweepedge ( 1 );

  // compute direction
  geom::cross_product3d ( sf0->get_plane(), normal, ndir );
  dbgprintf ( 2, "ndir --> %lf %lf %lf\n", ndir[0], ndir[1], ndir[2] );

  if ( geom::cross_product2d ( ndir, se0->get_dir2d() ) < 0.0 || geom::cross_product2d ( se1->get_dir2d(), ndir ) < 0.0 )
  {
    lastse = new SweepEdge ( see1->get_current(), se0->get_dir3d(), time );
    dbgprintf ( 2, "dir edge --> %lf %lf %lf\n",  se0->get_dir3d() [0], se0->get_dir3d() [1], se0->get_dir3d() [2] );
    lastse->update_speeds ( cg->get_next_facet ( index ) );
    lastse->set_init();
  }
  else
  {
    lastse = new SweepEdge ( see1->get_current(), ndir, time );
    dbgprintf ( 2, "dir edge --> %lf %lf %lf\n",  ndir[0], ndir[1], ndir[2] );
    lastse->update_speeds ( sf1 );
  }
  
//   getchar();

//   lastse->set_init();

  // stopping see1
  see1->set_stopped();
  see1->get_front ( 1 )->get_frontline()->update_sweepedge ( see1, lastse );

  // add switch event
  Event *nes = econtainer->get();
  nes->init ( lastse, lastse->get_start()->p, time, Event::NEWEDGESWITCH, gid );
  add_priority_event ( nes );

  dbgprintf ( 2, "init normal --> %lf %lf %lf\n", sf1->get_plane() [0], sf1->get_plane() [1], sf1->get_plane() [2] );

  int count = 0;
  while ( geom::cross_product2d ( ndir, se0->get_dir2d() ) < 0.0 || geom::cross_product2d ( se1->get_dir2d(), ndir ) < 0.0 )
  {
    SweepFacet *nextsf = cg->get_next_facet ( index );
    int nextindex = nextsf->get_pos();
    normal = nextsf->get_plane();
    dbgprintf ( 2, "checking with normal --> %lf %lf %lf\n", normal[0], normal[1], normal[2] );

    geom::cross_product3d ( sf0->get_plane(), normal, ndir );
    dbgprintf ( 2, "ndir --> %lf %lf %lf\n", ndir[0], ndir[1], ndir[2] );

    SweepFacet *nsf = new SweepFacet ( see1->get_current(), normal, nextsf->get_dir3d(), time );
    SweepEdge *nse;

    se0 = nextsf->get_original_sweepedge ( 0 );
    se1 = nextsf->get_original_sweepedge ( 1 );

//     printf ( "dir 0 --> %lf %lf\n", se0->get_dir2d() [0], se0->get_dir2d() [1] );
//     printf ( "dir 1 --> %lf %lf\n", se1->get_dir2d() [0], se1->get_dir2d() [1] );

    if ( geom::cross_product2d ( ndir, se0->get_dir2d() ) < 0.0 || geom::cross_product2d ( se1->get_dir2d(), ndir ) < 0.0 )
      nse = new SweepEdge ( see1->get_current(), se0->get_dir3d(), time );
    else
      nse = new SweepEdge ( see1->get_current(), ndir, time );
    nse->set_init();
    // add switch event
    Event *nes = econtainer->get();
    nes->init ( nse, nse->get_start()->p, time, Event::NEWEDGESWITCH, gid );
    add_priority_event ( nes );

    nsf->set_pos ( nextindex );
    nsf->set_xyspeed ( nextsf->get_xyspeed() );
    nsf->set_generator ( cg );
    cg->add_sweepfacet ( nsf );
    new FrontLine ( nsf, nse, lastse );
    nse->update_speeds ( nsf );

    // add switch event
    Event *nfs = econtainer->get();
    nfs->init ( nsf, nsf->get_start()->p, time, Event::NEWFACETSWITCH, gid );
    add_priority_event ( nfs );

    index = nextindex;
    lastse = nse;
    ASSERT_ERROR(count <= cg->initial_face_size(), "full rotation without stopping\n");
    count++;
  }

  // stopping see1
  see0->set_stopped();
  see0->get_front ( 0 )->get_frontline()->update_sweepedge ( see0, lastse );
}

// this routine generate as much as facet as needed to circumvent obstacle
void Graph::rotation_cw ( SweepEdge *see0, SweepEdge *see1 )
{
  dbgprintf ( 2, "--> CLOCKWISE rotation\n" );
  SweepFacet *sf0 = see0->get_front ( 0 )->get_owner();
  SweepFacet *sf1 = see1->get_front ( 1 )->get_owner();
  Convex_generator *cg = sf0->get_generator();

  double time = get_time();
  int gid = bucketgrid->get_index ( see0->get_current()->p );

  double *normal = sf0->get_plane();
  double ndir[3];

  int index = sf0->get_pos();
  
  SweepEdge *lastse = NULL;
  SweepEdge *se0 = sf0->get_original_sweepedge ( 0 );
  SweepEdge *se1 = sf0->get_original_sweepedge ( 1 );
  
    // compute direction
  geom::cross_product3d ( normal, sf1->get_plane(), ndir );
  dbgprintf ( 2, "ndir --> %lf %lf %lf\n", ndir[0], ndir[1], ndir[2] );
  dbgprintf ( 2, "cross --> %lf %lf\n", geom::cross_product2d ( ndir, se0->get_dir2d() ), geom::cross_product2d ( se1->get_dir2d(), ndir ) );
  
  if ( geom::cross_product2d ( ndir, se0->get_dir2d() ) < 0.0 || geom::cross_product2d ( se1->get_dir2d(), ndir ) < 0.0 )
  {
    lastse = new SweepEdge ( see0->get_current(), se1->get_dir3d(), time );
    dbgprintf ( 2, "dir edge --> %lf %lf %lf\n",  se1->get_dir3d() [0], se1->get_dir3d() [1], se1->get_dir3d() [2] );
    lastse->update_speeds ( cg->get_prev_facet ( index ) );      
    lastse->set_init();
  }
  else
  {
    lastse = new SweepEdge ( see1->get_current(), ndir, time );
    dbgprintf ( 2, "dir edge --> %lf %lf %lf\n",  ndir[0], ndir[1], ndir[2] );
    lastse->update_speeds ( sf0 );
  }
  
//   lastse->set_init();

  // stopping see0
  see0->set_stopped();
  see0->get_front ( 0 )->get_frontline()->update_sweepedge ( see0, lastse );

  // add switch event
  Event *nes = econtainer->get();
  nes->init ( lastse, lastse->get_start()->p, time, Event::NEWEDGESWITCH, gid );
  add_priority_event ( nes );

  dbgprintf ( 2, "init normal --> %lf %lf %lf\n", sf0->get_plane() [0], sf0->get_plane() [1], sf0->get_plane() [2] );
    
  int count = 0;
  while ( geom::cross_product2d ( ndir, se0->get_dir2d() ) < 0.0 || geom::cross_product2d ( se1->get_dir2d(), ndir ) < 0.0 )
  {
    SweepFacet *prevsf = cg->get_prev_facet ( index );
    int previndex = prevsf->get_pos();
    normal = prevsf->get_plane();
    dbgprintf ( 2, "checking with normal --> %lf %lf %lf\n", normal[0], normal[1], normal[2] );

    geom::cross_product3d ( normal, sf1->get_plane(), ndir );
    dbgprintf ( 2, "ndir --> %lf %lf %lf\n", ndir[0], ndir[1], ndir[2] );

    SweepFacet *nsf = new SweepFacet ( see0->get_current(), normal, prevsf->get_dir3d(), time );
    SweepEdge *nse;

    se0 = prevsf->get_original_sweepedge ( 0 );
    se1 = prevsf->get_original_sweepedge ( 1 );

//     printf ( "dir 0 --> %lf %lf\n", se0->get_dir2d() [0], se0->get_dir2d() [1] );
//     printf ( "dir 1 --> %lf %lf\n", se1->get_dir2d() [0], se1->get_dir2d() [1] );

    if ( geom::cross_product2d ( ndir, se0->get_dir2d() ) < 0.0 || geom::cross_product2d ( se1->get_dir2d(), ndir ) < 0.0 )
      nse = new SweepEdge ( see0->get_current(), se1->get_dir3d(), time );
    else
      nse = new SweepEdge ( see0->get_current(), ndir, time );

    nse->set_init();
    // add switch event
    Event *nes = econtainer->get();
    nes->init ( nse, nse->get_start()->p, time, Event::NEWEDGESWITCH, gid );
    add_priority_event ( nes );

    nsf->set_pos ( previndex );
//     printf ( "prev speed --> %lf\n", prevsf->get_xyspeed() );
    nsf->set_xyspeed ( prevsf->get_xyspeed() );
    nsf->set_generator ( cg );
    cg->add_sweepfacet ( nsf );
    new FrontLine ( nsf, lastse, nse );
    nse->update_speeds ( nsf );

    // add switch event
    Event *nfs = econtainer->get();
    nfs->init ( nsf, nsf->get_start()->p, time, Event::NEWFACETSWITCH, gid );
    add_priority_event ( nfs );

    index = previndex;
    lastse = nse;
    ASSERT_ERROR(count <= cg->initial_face_size(), "full rotation without stopping\n");
    count++;
  }

  // stopping see1
  see1->set_stopped();
  see1->get_front ( 1 )->get_frontline()->update_sweepedge ( see1, lastse );
}


// close cells on a single facet
int Graph::enclose_island ( SweepEdge *se0, SweepEdge *se1 )
{
  if ( se1->get_front ( 1 ) && se0->get_sweepfacet ( 0 ) && se0->get_sweepfacet ( 0 ) == se1->get_front ( 1 )->get_sweepedge ( 1 )->get_sweepfacet ( 1 ) )
  {
    dbgprintf ( 1, "simple closing case 0\n" );
    Front *frint0 = se1->get_front ( 0 );
    Front *frint1 = se1->get_front ( 1 );
    if ( frint0 && frint1 )
    {
      FrontLine *flint0 = frint0->get_frontline();
      FrontLine *flint1 = frint1->get_frontline();
      // close the interior fronts
      flint0->close_front ( frint0 );
      flint1->close_front ( frint1 );

      SweepEdge *se2 = frint1->get_sweepedge ( 1 );
      Front *frext0 = se0->get_front ( 0 );
      Front *frext1 = se2->get_front ( 1 );

      se1->merge_current ( se2, get_time() );
      if ( frext0 && frext1 )
      {
        FrontLine *mfl = frext0->get_frontline();
        Front *frn = mfl->front_merge ( frext0, frext1 );
        // generate the new edgecrash
        SweepEdge *frnse0 = frn->get_sweepedge ( 0 );
        SweepEdge *frnse1 = frn->get_sweepedge ( 1 );
        double crashpos[2];
        if ( geom::lines2d_intersection ( frnse0->get_start()->p, frnse1->get_start()->p, frnse0->get_dir2d(), frnse1->get_dir2d(), Graph::epsilon, crashpos ) )
        {
          double crashtime = frnse0->time_to_position ( crashpos );
          int ngid = bucketgrid->get_index ( crashpos );
          Event *ne = econtainer->get();
          ne->init ( frnse0, frnse1, crashpos, crashtime, Event::EDGE_EDGECRASH, ngid );
          add_event ( ne );
        }
        return 1;
      }
    }
  }
  if ( se0->get_front ( 0 ) && se1->get_sweepfacet ( 1 ) && se1->get_sweepfacet ( 1 ) == se0->get_front ( 0 )->get_sweepedge ( 0 )->get_sweepfacet ( 0 ) )
  {
    dbgprintf ( 1, "simple closing case 1\n" );
    Front *frint0 = se0->get_front ( 0 );
    Front *frint1 = se0->get_front ( 1 );
    if ( frint0 && frint1 )
    {
      FrontLine *flint0 = frint0->get_frontline();
      FrontLine *flint1 = frint1->get_frontline();
      // close the interior fronts
      flint0->close_front ( frint0 );
      flint1->close_front ( frint1 );

      SweepEdge *se2 = frint0->get_sweepedge ( 0 );
      Front *frext0 = se2->get_front ( 0 );
      Front *frext1 = se1->get_front ( 1 );

      se0->merge_current ( se2, get_time() );
      if ( frext0 && frext1 )
      {
        FrontLine *mfl = frext0->get_frontline();
        Front *frn = mfl->front_merge ( frext0, frext1 );
        // generate the new edgecrash
        SweepEdge *frnse0 = frn->get_sweepedge ( 0 );
        SweepEdge *frnse1 = frn->get_sweepedge ( 1 );
        double crashpos[2];
        if ( geom::lines2d_intersection ( frnse0->get_start()->p, frnse1->get_start()->p, frnse0->get_dir2d(), frnse1->get_dir2d(), Graph::epsilon, crashpos ) )
        {
          double crashtime = frnse0->time_to_position ( crashpos );
          int ngid = bucketgrid->get_index ( crashpos );
          Event *ne = econtainer->get();
          ne->init ( frnse0, frnse1, crashpos, crashtime, Event::EDGE_EDGECRASH, ngid );
          add_event ( ne );
        }
        return 1;
      }
    }
  }
  return 0;
}

void Graph::simple_newedgeswitch ( SweepEdge *se0, SweepEdge *se1, double *ndir3d, SweepFacet *msf[2] )
{
  dbgprintf ( 2, "--> creating new edge from edges %p %p with facet %p %p :\n", se0, se1, msf[0], msf[1] );
  geom::normalize3d ( ndir3d );
  SweepEdge *nse = new SweepEdge ( se0->get_current(), ndir3d, get_time() );
//   nse->set_initial_sweepfacets ( msf[0], msf[1] );

  nse->update_speeds ( msf[0] );
  FrontLine *fl0 = msf[0]->get_frontline();
  FrontLine *fl1 = msf[1]->get_frontline();

  fl0->update_sweepedge ( se0, nse );
  fl1->update_sweepedge ( se1, nse );

  Event *ne = econtainer->get();
  ne->init ( nse, nse->get_start()->p, get_time(), Event::NEWEDGESWITCH, se0->get_last_gid() );
  add_priority_event ( ne );
}

// we assume that sweepedges are sorted
void Graph::merge ( SweepEdge *se0, SweepEdge *se1 )
{
  dbgprintf ( 2, "merging edge %lf %lf and %lf %lf at %lf %lf\n", se0->get_dir2d() [0], se0->get_dir2d() [1], se1->get_dir2d() [0], se1->get_dir2d() [1], se1->get_current()->p[0], se1->get_current()->p[1] );

  SweepFacet *msf[2] = {NULL, NULL};
  msf[0] = se0->get_sweepfacet ( 0 );
  msf[1] = se1->get_sweepfacet ( 1 );

  if ( se0->get_front ( 1 ) && se1->get_front ( 0 ) )
  {
    Front *cfr = se0->get_front ( 1 );
    dbgprintf ( 2, "common sweepfacet dir --> %lf %lf\n", cfr->get_owner()->get_dir2d() [0], cfr->get_owner()->get_dir2d() [1] );
    // close the front
    FrontLine *cfl = cfr->get_frontline();
    cfl->close_front ( cfr );
  }

  if ( enclose_island ( se0, se1 ) )
  {
    return;
  }

  // create a new edge if necessary
  if ( msf[0] && msf[1] )
  {
    if ( msf[0] == msf[1] ) // corner
    {
      Front *cfr = se0->get_front ( 0 );
      // close the front
      FrontLine *cfl = cfr->get_frontline();
      cfl->close_front ( cfr );
      return;
    }

    // compute new directions
    double ndir3d[3];
    double ndir2d[2];
    geom::cross_product3d ( msf[0]->get_plane(), msf[1]->get_plane(), ndir3d ); // original
//     geom::normalize3d ( ndir3d );
    geom::copyvec2d ( ndir3d, ndir2d );
    dbgprintf ( 2, "new dir --> %lf %lf %lf\n", ndir3d[0], ndir3d[1], ndir3d[2] );

    if ( fabs ( ndir3d[2] ) < Graph::epsilon )
    {
      dbgprintf ( 2, "--> horizontal dir\n" );
      ndir3d[2] = 0.0;
      
#if defined(DURTY)     
      SweepEdge *cse = se0->get_front ( 0 )->get_sweepedge ( 0 );
      // we check if the opposite edge is sharing sf and msf
      if ( cse->get_sweepfacet ( 0 ) == msf[1] && cse->get_sweepfacet ( 1 ) == msf[0] )
      {
        printf ( "continuing ...\n" );
        return;
      }
#endif
    }

    if ( ndir3d[2] < 0.0 )
      voronoi_vertex_merge ( se0, se1, ndir3d );
    else // ndir[2] >= 0.0
    {
      msf[0]->print();
      msf[1]->print();
      geom::normalize2d ( ndir2d );
      dbgprintf ( 2, "new dir 2d --> %lf %lf\n", ndir2d[0], ndir2d[1] );

      Convex_generator *g0 = msf[0]->get_generator();
      Convex_generator *g1 = msf[1]->get_generator();

      // case where the same generator is enclosing one or more cells
      if ( g0 == g1 )
      {
        simple_newedgeswitch ( se0, se1, ndir3d, msf );
        return;
      }

      SweepEdge *ise0[2];
      ise0[0] = msf[0]->get_original_sweepedge ( 0 );
      ise0[1] = msf[0]->get_original_sweepedge ( 1 );
      SweepEdge *ise1[2];
      ise1[0] = msf[1]->get_original_sweepedge ( 0 );
      ise1[1] = msf[1]->get_original_sweepedge ( 1 );

//       printf("speeds --> %lf %lf\n", se0->get_xyspeed(), se1->get_xyspeed());
      dbgprintf ( 2, "cross 1 --> %lf\n", geom::cross_product2d ( ise0[1]->get_dir2d(), ndir2d ) );
      dbgprintf ( 2, "cross 2 --> %lf\n", geom::cross_product2d ( ise1[0]->get_dir2d(), ndir2d ) );

      if ( ( geom::cross_product2d ( ise0[1]->get_dir2d(), ndir2d ) >= 0.0 ) && geom::cross_product2d ( ise1[0]->get_dir2d(), ndir2d ) <= 0.0 )
      {
        simple_newedgeswitch ( se0, se1, ndir3d, msf );
      }
      else
      {
        if ( !voronoi_vertex_merge ( se0, se1, ndir3d ) )
          simple_newedgeswitch ( se0, se1, ndir3d, msf );
      }
    }
  }
  else if ( msf[0] && !msf[1] ) // relative to border crashes
  {
    merge_and_go_left ( se0, se1, msf[0] );
  }
  else if ( !msf[0] && msf[1] )
  {
    merge_and_go_right ( se0, se1, msf[1] );
  }
}