arr_basic_addition_visitor.h

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

    if(he_above == Halfedge_handle(NULL))
      return this->m_arr_access.insert_in_face_interior_ex(cv.base(),
                                                   this->m_th->face(),
                                                   v1,
                                                   v2,
                                                   SMALLER);

    return this->m_arr_access.insert_in_face_interior_ex(cv.base(),
                                                   he_above->face(),
                                                   v1,
                                                   v2,
                                                   SMALLER);
  }

  Halfedge_handle insert_at_vertices (const X_monotone_curve_2& cv,
                                      Halfedge_handle hhandle,
                                      Halfedge_handle prev,
                                      Subcurve* sc,
                                      bool &new_face_created)
  {
    return (_insert_at_vertices(cv, hhandle, prev, sc, new_face_created));
  }

  virtual Halfedge_handle split_edge(Halfedge_handle /*he*/,
                                     Subcurve* /*sc*/,
                                     const Point_2& /*pt*/)
  {
    return Halfedge_handle();
  }
  

  // check if the halfedge associated with 'sc' will be splitted at the given
  // return false.
  virtual bool is_split_event(Subcurve* /*sc*/, Event* /*event*/)
  {
    return false;
  }


  virtual Vertex_handle insert_isolated_vertex(const Point_2& pt,
                                               SL_iterator iter)
  {
    Vertex_handle res(NULL);
    //the isolated vertex is already at the arrangement
    if(pt.get_vertex_handle() != Vertex_handle(NULL))
      return res;
    if(iter == this->status_line_end())
    {
      res = this->m_arr_access.arrangement().insert_in_face_interior
        (pt.base(), this->m_arr_access.arrangement().unbounded_face());
    }
    else
    {
      Halfedge_handle he = ray_shoot_up(*iter);
      if (he == Halfedge_handle(NULL))
      {
        res = this->m_arr_access.arrangement().insert_in_face_interior
          (pt.base(), this->m_arr_access.arrangement().unbounded_face());
      }
      else
      {
        res = this->m_arr_access.arrangement().insert_in_face_interior (pt.base(), he->face());
      }
    }

    return (res);
  }


  Halfedge_handle ray_shoot_up(Subcurve* sc)
  {
    Halfedge_handle he_above;
    for(SL_iterator iter = this -> status_line_position(sc);
        iter != this -> status_line_end();
        ++iter)
    {
      if((*iter)->get_last_curve().get_halfedge_handle() !=
         Halfedge_handle(NULL))
      {
        he_above = (*iter)->get_last_curve().get_halfedge_handle();
        return (he_above);
      }
    }
  
    return (he_above);
  }




   void update_event(){}

   void update_event(Event*,
                    const Point_2&,
                    const X_monotone_curve_2&,
		     bool /* is_left_end */)
  {}

  void update_event(Event*,
                    Subcurve*,
                    Subcurve*,
                    bool /*created*/ = false)
  {}

  void update_event(Event*,
                    Subcurve*)
  {}


  void update_event(Event* e, const Point_2& pt)
  {
    Vertex_handle vh;
    if(e->get_point().get_vertex_handle() == vh)
      e->get_point().set_vertex_handle(pt.get_vertex_handle());
  }

  virtual Halfedge_handle
    insert_in_face_interior(const X_monotone_curve_2& cv,
                            Subcurve* sc)
  {
    Event *lastEvent = this->get_last_event(sc);
    Vertex_handle last_v = lastEvent->get_point().get_vertex_handle();
    Vertex_handle curr_v =
      this->current_event()->get_point().get_vertex_handle();
    Vertex_handle null_v;

    if(last_v == null_v && curr_v == null_v)
      return (this->_insert_in_face_interior(cv, sc));
    if(last_v == null_v && curr_v != null_v)
    {
      Halfedge_handle he = this->m_arr_access.arrangement().insert_from_right_vertex (cv.base(),
                                                                  curr_v);
      return (he->twin());
    }
    if(last_v != null_v && curr_v == null_v)
      return (this->m_arr_access.arrangement().insert_from_left_vertex (cv.base(), last_v));

    CGAL_assertion(last_v != null_v && curr_v != null_v);
    return (this->m_arr_access.arrangement().insert_at_vertices (cv.base(), last_v, curr_v));

  }


  virtual Halfedge_handle
    insert_from_right_vertex (const X_monotone_curve_2& cv,
                              Halfedge_handle he,
                              Subcurve* sc)
  {
    Event *lastEvent = this->get_last_event(sc);
    Vertex_handle last_v = lastEvent->get_point().get_vertex_handle();

    if(last_v != Vertex_handle())
      return (this->m_arr_access.arrangement().insert_at_vertices (cv.base(), he, last_v));
    
    return (_insert_from_right_vertex(cv, he, sc));
  }

  virtual Halfedge_handle
    insert_from_left_vertex (const X_monotone_curve_2& cv,
                             Halfedge_handle he,
                             Subcurve* sc)
  {
    Vertex_handle curr_v =
      this->current_event()->get_point().get_vertex_handle();

     if(curr_v != Vertex_handle())
       return (this->m_arr_access.arrangement().insert_at_vertices (cv.base(), he, curr_v));

    return (_insert_from_left_vertex(cv, he, sc));
  }

  Halfedge_handle _insert_from_left_vertex(const X_monotone_curve_2& cv,
                                           Halfedge_handle he,
                                           Subcurve* /*sc*/)
  {
    Event* curr_event = this->current_event();
    Vertex_handle v = 
        this->m_arr_access.create_vertex(curr_event->get_point().base());
      return this->m_arr_access.insert_from_vertex_ex(cv.base(), he, v, SMALLER);
  }

  Halfedge_handle _insert_from_right_vertex(const X_monotone_curve_2& cv,
                                            Halfedge_handle he,
                                            Subcurve* sc)
  {
    Event* last_event = this->get_last_event(sc);
    Vertex_handle v = 
        this->m_arr_access.create_vertex(last_event->get_point().base());
      return this->m_arr_access.insert_from_vertex_ex(cv.base(), he, v, LARGER);
  }

  Halfedge_handle _insert_at_vertices (const X_monotone_curve_2& cv,
                                       Halfedge_handle hhandle,
                                       Halfedge_handle prev,
                                       Subcurve* /*sc*/,
                                       bool &new_face_created)
  {
 
  bool        prev1_before_prev2 = true;

  if (this->m_arr_access.are_on_same_inner_component(hhandle, prev))
  {
    // If prev1 and prev2 are on different components, the insertion of the
    // new curve does not generate a new face, so the way we send these
    // halfedge pointers to the auxiliary function _insert_at_vertices() does
    // not matter.
    // However, in our case, where the two halfedges are reachable from one
    // another and are located on the same hole, a new face will be created
    // and form a hole inside their current incident face. In this case we
    // have to arrange prev1 and prev2 so that the new face (hole) will be
    // incident to the correct halfedge, directed from prev1's target to
    // prev2's target.
    // To do this, we check whether prev1 lies inside the new face we are
    // about to create (or alternatively, whether prev2 does not lie inside
    // this new face).
    const unsigned int  dist1 = this->m_arr_access.halfedge_distance (hhandle, prev);
    const unsigned int  dist2 = this->m_arr_access.halfedge_distance (prev, hhandle);

    prev1_before_prev2 = (dist1 > dist2) ?
      (this->m_arr_access.is_inside_new_face (hhandle, prev, cv.base())) :
      (! this->m_arr_access.is_inside_new_face (prev, hhandle, cv.base()));
  }

  // Perform the insertion.

  new_face_created = false;
  Halfedge_handle  new_he = (prev1_before_prev2) ?
    this->m_arr_access.insert_at_vertices_ex (cv.base(),
                                        hhandle,
                                        prev,
                                        LARGER,
                                        new_face_created,
                                        false) :
    this->m_arr_access.insert_at_vertices_ex (cv.base(),
                                        prev,
                                        hhandle,
                                        SMALLER,
                                        new_face_created,
                                        false);

  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 by the twin halfedge) and move the relevant
    // holes and isolated vertices into the new face.
    this->m_arr_access.relocate_in_new_face (new_he);
  }

  // Return a handle to the new halfedge directed from prev1's target to
  // prev2's target. Note that this may be the twin halfedge of the one
  // returned by _insert_at_vertices();
  if (! prev1_before_prev2)
    new_he = new_he->twin();

  return (new_he);
  }

protected:

  X_monotone_curve_2   sub_cv1;         // Auxiliary variable (for splitting).
  X_monotone_curve_2   sub_cv2;         // Auxiliary variable (for splitting).

};


CGAL_END_NAMESPACE

#endif