overlay_visitor.h

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

     //update the result edge
    this ->create_edge(sc, res);

    map_halfedge_and_twin(res, false, cv.get_curve_info());

    // new face was created, need to update the new face's data
    if(new_face_created)
    {
      Halfedge_handle_red  red_he  ;
      Halfedge_handle_blue blue_he ;

      
      // special case: we need to take the face that is incident to the twin
      // halfedge
      bool special_case = 
        (this->current_event()->is_finite_in_x() && 
         this->current_event()->is_plus_boundary_in_y());

      // get the new face
      Face_handle new_face = (special_case ? res->twin()->face() : res->face());

      //traverse new_face's boundary
      Ccb_halfedge_circulator ccb_end = new_face->outer_ccb();
      Ccb_halfedge_circulator ccb_circ = ccb_end;
      do
      { 
        //get the current halfedge on the face boundary
        Halfedge_handle he =  ccb_circ;

        //CGAL_assertion(m_halfedges_map.is_defined(he));
        if(!m_halfedges_map.is_defined(he))
        {
          ++ccb_circ;
          continue;
        }
        const Curve_info& cv_info = m_halfedges_map[he];
        if(cv_info.get_color() == Curve_info::RED)
        {
          red_he = cv_info.get_red_halfedge_handle();
          if(blue_he != Halfedge_handle_blue())
            break;
        }
        else
          if(cv_info.get_color() == Curve_info::BLUE)
          {
            blue_he = cv_info.get_blue_halfedge_handle();
            if(red_he != Halfedge_handle_red())
              break;
          }
          else 
          {
            // overlap
            CGAL_assertion(cv_info.get_color() == Curve_info::PURPLE);
            red_he  = cv_info.get_red_halfedge_handle()  ;
            blue_he = cv_info.get_blue_halfedge_handle() ;
            break;
          }
        ++ccb_circ;
      }
      while(ccb_circ != ccb_end);
      //finished traversing the boundary of the face

      if(red_he != Halfedge_handle_red() && blue_he != Halfedge_handle_blue())
      {
        // red face and blue face intersects (or overlap)
        Face_handle_red red_face = red_he->face();
        Face_handle_blue blue_face = blue_he->face();
        m_overlay_traits->create_face(red_face, blue_face,new_face);
      }
      else
      {
        // red face inside blue face
        if(red_he != Halfedge_handle_red())
        {
          Face_handle_red red_face = red_he->face();
          Face_handle_blue blue_face;
          Subcurve* sc_above = sc->get_above();
          if(!sc_above)
           blue_face = sc->get_top_blue_halfedge()->face();
          else
            blue_face = 
              sc_above->get_blue_halfedge_handle()->face();
          
          m_overlay_traits->create_face(red_face, blue_face,new_face);
        }
        else
        {
          // blue face inside red face
          CGAL_assertion(blue_he != Halfedge_handle_blue() && 
                         red_he == Halfedge_handle_red());
          Face_handle_red red_face;
          Face_handle_blue blue_face = blue_he->face();
          Subcurve* sc_above = sc->get_above();
          if(!sc_above)
            red_face = sc->get_top_red_halfedge()->face();
          else
            red_face = 
              sc_above->get_red_halfedge_handle()->face();
          
          m_overlay_traits->create_face(red_face, blue_face,new_face);
        }
      }
    }

    return res;
  }

  virtual Vertex_handle insert_isolated_vertex(const Point_2& pt,
                                               SL_iterator iter)
  {
    Vertex_handle v = Base::insert_isolated_vertex(pt, iter);
    Object red = pt.get_red_object();
    Object blue = pt.get_blue_object();
    Vertex_handle_red     red_v;
    Vertex_handle_blue    blue_v;
    assign(red_v, red);
    assign(blue_v, blue);

    if(!red.is_empty() && !blue.is_empty())
    {
      m_overlay_traits->create_vertex(red_v, blue_v, v);
      return v;
    }
    
    CGAL_assertion(!red.is_empty() || !blue.is_empty());

    Subcurve* sc_above; 
    if(red.is_empty())
    {
      // isolated blue vertex inside red face
      Face_handle_red red_f ;
      if( iter == this ->status_line_end())
      {
        m_overlay_traits->create_vertex(m_red_th->face(), blue_v, v);
        return v;
      }
      sc_above = *iter;
      if(! sc_above)
        red_f = m_red_th->face();
      else
      {
        if(sc_above->get_color() != Curve_info::BLUE)
          red_f = sc_above->get_red_halfedge_handle()->face();
        else
        {
          sc_above = sc_above->get_above();
          if(!sc_above)
            red_f = m_red_th->face();
          else
            red_f = sc_above->get_red_halfedge_handle()->face();
        }
      }
      m_overlay_traits->create_vertex(red_f, blue_v, v);
      return v;
    }
    
    CGAL_assertion(blue.is_empty());
    // isolated red vertex inside blue face

    Face_handle_blue    blue_f;
    if( iter == this ->status_line_end())
    {
      m_overlay_traits->create_vertex(red_v,m_blue_th->face(),v);
      return v;
    }
    sc_above = *iter;
    if(! sc_above)
      blue_f = m_blue_th->face();
    else
    {
      if(sc_above->get_color() != Curve_info::RED)
        blue_f = sc_above->get_blue_halfedge_handle()->face();
      else
      {
        sc_above = sc_above->get_above();
          if(!sc_above)
          blue_f = m_blue_th->face();
        else
          blue_f = sc_above->get_blue_halfedge_handle()->face();
      }
    }
    m_overlay_traits->create_vertex(red_v, blue_f, v);
    return v;
  }

  // maps halfedge and his twin, right_dir is true iff he is directed from
  // left to right
  void map_halfedge_and_twin(Halfedge_handle he, bool right_dir, 
                             const Curve_info& cv_info)
  {
    // original halfedges that were stored is directed from right to left
    Halfedge_handle_red     red_he_info = cv_info.get_red_halfedge_handle();
    Halfedge_handle_blue    blue_he_info = cv_info.get_blue_halfedge_handle();
    Halfedge_handle_red     red_he_info_twin;
    Halfedge_handle_blue    blue_he_info_twin; 


    if(red_he_info  != Halfedge_handle_red())
      red_he_info_twin = red_he_info->twin();

    if(blue_he_info != Halfedge_handle_blue())
      blue_he_info_twin = blue_he_info->twin();


    //cv_info_twin will have the twin halfedge
    Curve_info cv_info_twin(red_he_info_twin, blue_he_info_twin);

    if(right_dir)
    {
      m_halfedges_map[he] = cv_info_twin;
      m_halfedges_map[he->twin()] = cv_info;
    }
    else
    {
      m_halfedges_map[he] = cv_info;
      m_halfedges_map[he->twin()] = cv_info_twin;
    }
  }

  void create_vertex(Event *event, Vertex_handle res_v, Subcurve* sc)
  {
    const Point_2& pt = event->get_point();
    CGAL_assertion( !pt.is_red_object_null() || !pt.is_blue_object_null());
    const Object& red_obj  = pt.get_red_object();
    const Object& blue_obj = pt.get_blue_object();
    Vertex_handle_red red_v;
    Subcurve* sc_above = sc->get_above();
    if(assign(red_v, red_obj))
    {
      Vertex_handle_blue    blue_v;
      if(assign(blue_v, blue_obj))
      {
        // red vertex on blue vertex
        m_overlay_traits ->create_vertex(red_v, blue_v, res_v);
      }
      else
      {
        Halfedge_handle_blue    blue_he;
        if(assign(blue_he, blue_obj))
        {
          //red vertex on blue halfedge
          m_overlay_traits->create_vertex(red_v, blue_he, res_v);
        }
        else
        {
          // red vertex inside blue face
          CGAL_assertion(blue_obj.is_empty());
          Face_handle_blue    blue_f;
          if(!sc_above)
            blue_f = sc->get_top_blue_halfedge()->face();
          else
          {
            blue_f = sc_above ->get_blue_halfedge_handle()->face();
          }
          m_overlay_traits->create_vertex(red_v, blue_f, res_v);
        }
      }
    }
    else
    {
      Halfedge_handle_red    red_he;
      if(assign(red_he, red_obj))
      {
        Halfedge_handle_blue   blue_he;
        if(assign(blue_he, blue_obj))
        {
          //itersection red halfedge and blue halfedge
          m_overlay_traits->create_vertex(red_he, blue_he, res_v);
        }
        else
        {
          Vertex_handle_blue    blue_v;
          CGAL_assertion(assign(blue_v, blue_obj));

          assign(blue_v, blue_obj);
          // blue vertex on red halfedge
          m_overlay_traits->create_vertex(red_he, blue_v, res_v);
        }
      }
      else
      {
        // blue vertex inside red face
        CGAL_assertion(red_obj.is_empty());
        Vertex_handle_blue    blue_v;

        CGAL_assertion(assign(blue_v, blue_obj));
        assign(blue_v, blue_obj);
        Face_handle_red    red_f;
        if(!sc_above)
          red_f = sc->get_top_red_halfedge()->face();
        else
        {
          red_f = sc_above ->get_red_halfedge_handle()->face();
        }
        m_overlay_traits->create_vertex(red_f, blue_v, res_v);
      }
    }
  }

  void create_edge(Subcurve *sc, Halfedge_handle res_he)
  {
    Halfedge_handle_red  red_he;
    Halfedge_handle_blue blue_he;

    // update the result halfedge
    if(sc->get_color() == Curve_info::PURPLE)
    {
       // overlap edge
      red_he = sc->get_red_halfedge_handle();
      blue_he = sc->get_blue_halfedge_handle();
      m_overlay_traits ->create_edge(red_he, blue_he, res_he);
    }
    else
      if(sc->get_color() == Curve_info::RED)
      {
        // red edge on blue face
        red_he = sc->get_red_halfedge_handle();
        Face_handle_blue blue_f;
       
        Subcurve* sc_above = sc->get_above();
        if(!sc_above)
          blue_f = sc->get_top_blue_halfedge()->face();
        else
          blue_f = sc_above->get_blue_halfedge_handle()->face();
          
        m_overlay_traits ->create_edge(red_he, blue_f, res_he);
      }
      else
      {
        // blue edge on red face
        CGAL_assertion(sc->get_color() == Curve_info::BLUE);

        blue_he = sc->get_blue_halfedge_handle();
        Face_handle_red red_f;
       
        Subcurve* sc_above = sc->get_above();
        if(!sc_above)
          red_f = sc->get_top_red_halfedge()->face();
        else
          red_f = sc_above->get_red_halfedge_handle()->face();
          
        m_overlay_traits ->create_edge(red_f, blue_he, res_he);
      }
  }

  void after_sweep()
  {
    //after sweep finshed, merge the two remaining unbouded_faces from each arrangment
    m_overlay_traits ->create_face(m_red_th->face(),
                                   m_blue_th->face(),
                                   this->m_th->face());
  }

protected:

  Hash_map                  m_halfedges_map;
  OverlayTraits*            m_overlay_traits;

  Arr_accessor<Arrangement1> m_red_arr_accessor;
  Arr_accessor<Arrangement2> m_blue_arr_accessor;

  Halfedge_handle_red        m_red_th;
  Halfedge_handle_blue       m_blue_th;
};

CGAL_END_NAMESPACE

#endif