arr_construction_visitor.h

很多二维 三维几何计算算法 C++ 类库

// Copyright (c) 1997  Tel-Aviv University (Israel).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/Arrangement_2/include/CGAL/Sweep_line_2/Arr_construction_visitor.h $
// $Id: Arr_construction_visitor.h 37149 2007-03-16 09:16:03Z afabri $
// 
//
// Author(s)     : Baruch Zukerman <[e-mail]>

#ifndef CGAL_ARR_CONSTRUCTION_VISITOR_H
#define CGAL_ARR_CONSTRUCTION_VISITOR_H


#include <CGAL/Arr_accessor.h>
#include <CGAL/Sweep_line_2_empty_visitor.h>
#include <CGAL/Unique_hash_map.h> 
#include <CGAL/Sweep_line_2/Integer_hash_function.h>
#include <vector>

CGAL_BEGIN_NAMESPACE

template <class Traits_, class Arrangement, class Event_, class Subcurve_> 
class Arr_construction_visitor : public Empty_visitor<Traits_,
                                                      Subcurve_,
                                                      Event_>
{
protected:

  typedef typename Arrangement::Halfedge_handle        Halfedge_handle;
  typedef typename Arrangement::Vertex_handle          Vertex_handle;
  typedef typename Arrangement::Face_handle            Face_handle;
  typedef typename Arrangement::Halfedge_around_vertex_circulator Halfedge_around_vertex_circulator;
  typedef typename Arrangement::Ccb_halfedge_circulator 
    Ccb_halfedge_circulator;
  typedef typename Arrangement::Hole_iterator         Hole_iterator;
  typedef Arr_construction_visitor<Traits_,
                                   Arrangement,
                                   Event_,
                                   Subcurve_>          Self;

  typedef Traits_                                      Traits;
  typedef Event_                                       Event;
  typedef Subcurve_                                    Subcurve;

  typedef typename Traits::X_monotone_curve_2          X_monotone_curve_2;
  typedef typename Traits::Point_2                     Point_2;
 
  typedef Empty_visitor<Traits,
                        Subcurve,
                        Event>                         Base;
 
  typedef typename Base::SubCurveIter                  SubCurveIter;
  typedef typename Base::SubCurveRevIter               SubCurveRevIter;
  typedef typename Base::SL_iterator                   SL_iterator;

  typedef Unique_hash_map<Halfedge_handle, 
                          std::list<unsigned int> >    Halfedge_indexes_map;
  typedef typename Halfedge_indexes_map::data_type     Indexes_list;
  typedef Unique_hash_map<unsigned int,
                          Vertex_handle,
                          Integer_hash_function>       Iso_vertices_map;

protected:
          
  Arr_accessor<Arrangement>  m_arr_access;
  unsigned int               m_sc_counter;  // Counter for subcurves that may
                                            // represent a hole (the upper
                                            // subcurves that emarge from event
                                            // points with only right curves). 

  std::vector<Halfedge_handle>
                             m_sc_he_table; // A table that maps a subcurve
                                            // index to its halfedhe handle,
                                            // directed from right ot left.
  Iso_vertices_map           m_iso_verts_map; // maps an index to the isolated vertex.

  Halfedge_indexes_map       m_he_indexes_table;

  // additional data members to support construction of unbounded arrangement.
  Halfedge_handle            m_lh;
  Halfedge_handle            m_th;
  Halfedge_handle            m_bh;
  Halfedge_handle            m_rh;
  std::list<unsigned int>    m_subcurves_at_ubf;
  Event*                     m_prev_minus_inf_x_event;
  Event*                     m_prev_plus_inf_y_event;
  
private:

  Arr_construction_visitor (const Self& );
  Self& operator= (const Self& );

public:

  Arr_construction_visitor(Arrangement *arr):
      m_arr_access (*arr),
      m_sc_counter (0),
      m_sc_he_table(1),
      m_prev_minus_inf_x_event(NULL),
      m_prev_plus_inf_y_event(NULL)
  {}

  virtual ~Arr_construction_visitor(){}

  void before_sweep()
  {
    m_lh = m_arr_access.top_left_fictitious_vertex()->incident_halfedges();
    if(m_lh->source() != m_arr_access.bottom_left_fictitious_vertex())
      m_lh = m_lh->next();
    else
      m_lh = m_lh->twin();

    m_bh = m_lh->next();
    m_rh = m_bh->next();
    m_th = m_rh->next();

    CGAL_assertion(m_lh->direction() == LARGER);
    CGAL_assertion(m_lh->face() != m_arr_access.fictitious_face());
    CGAL_assertion(m_lh->source() == m_arr_access.top_left_fictitious_vertex() &&
                   m_lh->target() == m_arr_access.bottom_left_fictitious_vertex());

    CGAL_assertion(m_bh->direction() == SMALLER);
    CGAL_assertion(m_bh->face() != m_arr_access.fictitious_face());
    CGAL_assertion(m_bh->source() == m_arr_access.bottom_left_fictitious_vertex() &&
                   m_bh->target() == m_arr_access.bottom_right_fictitious_vertex());

    CGAL_assertion(m_rh->direction() == SMALLER);
    CGAL_assertion(m_rh->face() != m_arr_access.fictitious_face());
    CGAL_assertion(m_rh->source() == m_arr_access.bottom_right_fictitious_vertex() &&
                   m_rh->target() == m_arr_access.top_right_fictitious_vertex());

    CGAL_assertion(m_th->direction() == LARGER);
    CGAL_assertion(m_th->face() != m_arr_access.fictitious_face());
    CGAL_assertion(m_th->source() == m_arr_access.top_right_fictitious_vertex() &&
                   m_th->target() == m_arr_access.top_left_fictitious_vertex());
  }

  bool after_handle_event(Event* event, SL_iterator iter, bool)
  {
    if(!event->has_left_curves() && !event->has_right_curves())
    {
      //isolated event (no curves)
      Vertex_handle v = insert_isolated_vertex(event->get_point(), iter);
      m_iso_verts_map[++m_sc_counter] = v;
      insert_index_to_sc_he_table(m_sc_counter, Halfedge_handle());
      if(iter != this->status_line_end())
      {
        Subcurve *sc_above = *iter;
        sc_above->push_back_halfedge_index(m_sc_counter);
      }
      else
        m_subcurves_at_ubf.push_back(m_sc_counter);
      

      return true;
    }

    if(!event->has_left_curves() && event->is_finite())
    {
      CGAL_assertion(event->has_right_curves());
      //its an event that may represent a hole
      (*(event->right_curves_rbegin()))->set_index(++m_sc_counter);
      if(iter != this->status_line_end())
      {
        Subcurve *sc_above = *iter;
        sc_above->push_back_halfedge_index(m_sc_counter);
      }
      else
        m_subcurves_at_ubf.push_back(m_sc_counter);
    }

    for(SubCurveIter itr = event->left_curves_begin();
        itr != event->left_curves_end();
        ++itr)
    {
      (*itr)->set_last_event(event);
    }

    if(event->get_num_right_curves() == 0)
    {
      set_prev_inf_event_to_null(event);
      return true;
    }

    event->get_is_curve_in_arr().resize(event->get_num_right_curves(),false);
    for(SubCurveIter itr = event->right_curves_begin();
      itr != event->right_curves_end();
      ++itr)
    {
      (*itr)->set_last_event(event);
    }
    return false; 
  }

  void add_subcurve(const X_monotone_curve_2& cv,Subcurve* sc)
  {
    Event *lastEvent = get_last_event(sc);
    Halfedge_handle res; 
    Halfedge_handle hhandle = this ->current_event()->get_halfedge_handle();

    int jump = lastEvent->get_halfedge_jump_count(sc);
    // if the previous event on the curve is not in the planar map yet
    if ( lastEvent->get_halfedge_handle() == Halfedge_handle(NULL) ) 
    {
      // we have a handle from the previous insert
      if ( hhandle != Halfedge_handle(NULL) )
      { 
        res = this->insert_from_right_vertex(cv, hhandle, sc);
        res = res->twin();
      }
      else
      {
        // if this is the first left curve being inserted
        res = this->insert_in_face_interior(cv, sc);
      }
    } 
    else 
    {
      // the previous event on the curve is already in the planar map. 
      // Let's use it.
      Halfedge_handle prev = lastEvent->get_halfedge_handle();

      // skip to the right halfedge
      for ( int i = 0 ; i < jump ; i++ )
        prev = (prev->next())->twin();
      
      // we have a handle from the previous insert
      if ( hhandle != Halfedge_handle(NULL) ) 
      {
        CGAL_assertion(prev->face() == hhandle->face());
       
        bool dummy;
        

        res = this->insert_at_vertices(cv,hhandle,prev,sc, dummy);
        res = res->twin();
      }
      else
      {
        res = this->insert_from_left_vertex(cv, prev, sc);
      }
    }
    if ( lastEvent->get_num_left_curves() == 0 &&  
      lastEvent->is_curve_largest((Subcurve*)sc) )
    {
      lastEvent->set_halfedge_handle(res->twin());

      // if sc has valid index, insert his index to m_sc_he_table
      if(sc->has_valid_index())
      {
        CGAL_assertion(res->twin()->direction() == LARGER);
        insert_index_to_sc_he_table(sc->index(), res->twin());
      }
      
    }
    this->current_event()->set_halfedge_handle(res);

    if(lastEvent->dec_right_curves_counter() == 0)
    {
      set_prev_inf_event_to_null(lastEvent);
      (this ->deallocate_event(lastEvent));
    }

    //clear the list of indexes of sc
    sc->clear_haldedges_indexes();
  }

 
  virtual Halfedge_handle
    insert_in_face_interior(const X_monotone_curve_2& cv,
			    Subcurve* sc)
  {
    Vertex_handle v1 = 
      m_arr_access.create_vertex(_point(get_last_event(sc)->get_point()));
    Vertex_handle v2 =
      m_arr_access.create_vertex(_point(this->current_event()->get_point()));
    Halfedge_handle res =