arr_construction_visitor.h

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

      m_arr_access.insert_in_face_interior_ex(_curve(cv),
                                              m_th->face(),
                                              v1,
                                              v2,
                                              SMALLER);                                                                  
    if(sc->has_haldedges_indexes())
    {
      CGAL_assertion(res->twin()->direction() == LARGER);
      Indexes_list& list_ref = m_he_indexes_table[res->twin()];
      list_ref.clear();
      list_ref.splice(list_ref.end(), sc->get_haldedges_indexes_list());
    }
    return (res);

  }

  virtual Halfedge_handle insert_at_vertices(const X_monotone_curve_2& cv,
                                             Halfedge_handle hhandle,
                                             Halfedge_handle prev,
                                             Subcurve* sc,
                                             bool &new_face_created)
  {
    const bool      both_unbounded = hhandle->is_fictitious() || prev->is_fictitious();
    Halfedge_handle res;
    bool flip_res = false;
    if(this->current_event()->is_finite_in_x() && 
       this->current_event()->is_plus_boundary_in_y())
    {
      res = m_arr_access.insert_at_vertices_ex(_curve(cv),
                                               prev,
                                               hhandle,
                                               SMALLER,
                                               new_face_created,
                                               both_unbounded);
      flip_res = true;
    }
    else
      res = m_arr_access.insert_at_vertices_ex(_curve(cv),
                                               hhandle,
                                               prev,
                                               LARGER,
                                               new_face_created,
                                               both_unbounded);

     // map the halfedge to the indexes list of all subcurves that are below him
      if(sc->has_haldedges_indexes())
      {
        Halfedge_handle temp = res;
        if(flip_res)
          temp = temp->twin();
        CGAL_assertion(temp->direction() == LARGER);
        Indexes_list& list_ref = m_he_indexes_table[temp];
        list_ref.clear();
        list_ref.splice(list_ref.end(), sc->get_haldedges_indexes_list());
      }
   
    if (new_face_created)
    {
      // In case a new face has been created (pointed by the new halfedge
      // we obtained), we have to examine the holes and isolated vertices
      // in the existing face (pointed be the twin halfedge) and relocate
      // the relevant features in the new face.
      //m_arr_access.relocate_in_new_face (res);
      CGAL_assertion(res->face() != res->twin()->face());
      
      this->relocate_holes_and_iso_verts_in_new_face(res);
    }

    if(flip_res)
      return res->twin();

    return res;
  }

  virtual Halfedge_handle insert_from_right_vertex
                          (const X_monotone_curve_2& cv,
                           Halfedge_handle he,
                           Subcurve* sc)
  {
    Vertex_handle v = 
      m_arr_access.create_vertex(_point(get_last_event(sc)->get_point()));
    Halfedge_handle res = m_arr_access.insert_from_vertex_ex(_curve(cv), he, v, LARGER);
    if(sc->has_haldedges_indexes())
    {
      CGAL_assertion(res->direction() == LARGER);
      Indexes_list& list_ref = m_he_indexes_table[res];
      list_ref.clear();
      list_ref.splice(list_ref.end(), sc->get_haldedges_indexes_list());
    }
    return (res);
  }

  virtual Halfedge_handle insert_from_left_vertex
                          (const X_monotone_curve_2& cv,
                           Halfedge_handle he,
                           Subcurve* sc)
  {
    Vertex_handle v = 
      m_arr_access.create_vertex(_point(this->current_event()->get_point()));
    Halfedge_handle res = m_arr_access.insert_from_vertex_ex(_curve(cv), he, v, SMALLER);
    if(sc->has_haldedges_indexes())
    {
      CGAL_assertion(res->twin()->direction() == LARGER);
      Indexes_list& list_ref = m_he_indexes_table[res->twin()];
      list_ref.clear();
      list_ref.splice(list_ref.end(), sc->get_haldedges_indexes_list());
    }
    
    return (res);
  }


  virtual Vertex_handle insert_isolated_vertex(const Point_2& pt,
                                               SL_iterator)
  {
    return (m_arr_access.arrangement().insert_in_face_interior (_point(pt),
								m_th->face()));
  }

  void relocate_holes_and_iso_verts_in_new_face(Halfedge_handle he)
  {
    // We use a constant indexes map so no new entries are added there.
    const Halfedge_indexes_map& const_he_indexes_table = m_he_indexes_table;
    Face_handle                 new_face = he->face();
    Halfedge_handle             curr_he = he;

    do
    {
      // we are intreseted only in halfedges directed from right to left.
      if(curr_he->direction() == LARGER)
      {
        const Indexes_list& indexes_list = const_he_indexes_table[curr_he];
        typename Indexes_list::const_iterator itr;

        for (itr = indexes_list.begin();
             itr != indexes_list.end();
             ++itr)
        {
          CGAL_assertion(*itr != 0 && *itr < m_sc_he_table.size());
          Halfedge_handle he_on_face = m_sc_he_table[*itr];
          //if he_on_face is a null halfedge handle then its index for an
          //isolated vertex.
          if(he_on_face == Halfedge_handle())
          {
            Vertex_handle v = m_iso_verts_map[*itr];
            CGAL_assertion(v != Vertex_handle());
            if(v->face() == new_face)
              continue;
            m_arr_access.move_isolated_vertex(v->face(),
                                              new_face,
                                              v);

          }
          else
          {
            if(he_on_face->twin()->face() == new_face)
              //this hole was already relocated
              continue;

            m_arr_access.move_hole (he_on_face->twin()->face(),
                                    new_face,
                                    he_on_face->twin()->ccb());
            relocate_holes_and_iso_verts_in_new_face(he_on_face->twin());
          }
        }
      }
      curr_he = curr_he->next();
    }
    while(curr_he != he);

  }

  void before_handle_event(Event* event)
  {
    if(event->is_finite())
      return;

     // if it is an event at infinity, split the corresponding fictitious edge.
    Boundary_type inf_x = event->infinity_at_x();
    Boundary_type inf_y = event->infinity_at_y();

    Vertex_handle v_at_inf = 
      m_arr_access.create_vertex_at_infinity(inf_x, inf_y);
    switch(inf_x)
    {
    case MINUS_INFINITY:
      m_arr_access.split_fictitious_edge(m_lh, v_at_inf);
      event->set_halfedge_handle(m_lh);
      if(m_prev_minus_inf_x_event)
        m_prev_minus_inf_x_event->set_halfedge_handle(m_lh->next());
      m_prev_minus_inf_x_event = event;
      return;

    case PLUS_INFINITY:
      m_arr_access.split_fictitious_edge(m_rh, v_at_inf);
      event->set_halfedge_handle(m_rh);
      m_rh = m_rh->next();
      return;

    case NO_BOUNDARY:
    default:
      break;
    }

    switch(inf_y)
    {
      case MINUS_INFINITY:
        m_arr_access.split_fictitious_edge(m_bh, v_at_inf);
        event->set_halfedge_handle(m_bh);
        m_bh = m_bh->next();
        return;

      case PLUS_INFINITY:
        {
          m_arr_access.split_fictitious_edge(m_th, v_at_inf);
          event->set_halfedge_handle(m_th);
          if(m_prev_plus_inf_y_event != NULL)
            m_prev_plus_inf_y_event->set_halfedge_handle(m_th->next());
          m_prev_plus_inf_y_event = event;
          Indexes_list& list_ref = m_he_indexes_table[m_th->next()];
          list_ref.clear();
          list_ref.splice(list_ref.end(), m_subcurves_at_ubf);
          CGAL_assertion(m_subcurves_at_ubf.empty());
        }
        return;

      case NO_BOUNDARY:
      default:
        // doesn't suppose to reach here at all.
        CGAL_assertion(false);
    }
  }
  
  Event* get_last_event(Subcurve* sc)
  {
    return (reinterpret_cast<Event*>((sc)->get_last_event()));
  }

private:

  /*!
   * Cast a Traits::Point_2 into an Arrangement::Point_2 object.
   * These two types may not be the same when the addition visitor inherits
   * from this base class.
   */
  const typename Arrangement::Point_2& _point (const Point_2& p) const
  {
    return (static_cast<const typename Arrangement::Point_2&> (p));
  }

  /*!
   * Cast a Traits::X_monotone_curve_2 into an Arrangement::X_monotone_curve_2
   * object.
   * These two types may not be the same when the addition visitor inherits
   * from this base class.
   */
  const typename Arrangement::X_monotone_curve_2&
    _curve (const X_monotone_curve_2& cv) const
  {
    return (static_cast<const typename Arrangement::X_monotone_curve_2&> (cv));
  }

  void insert_index_to_sc_he_table(unsigned int i, Halfedge_handle he)
  {
    CGAL_assertion(i!=0);
    if(i >= m_sc_he_table.size())
    {
      m_sc_he_table.resize(2*i);
    }

    m_sc_he_table[i] = he;
  }

  void set_prev_inf_event_to_null(Event* e)
  {
    CGAL_assertion(!this->current_event()->is_minus_boundary_in_x());    
    if(e == m_prev_plus_inf_y_event)
      m_prev_plus_inf_y_event = NULL;
  }

};

CGAL_END_NAMESPACE

#endif