envelope_element_visitor_3.h

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

    // from the edge to the vertex, the envelope goes closer), then if the
    // second map wins on the edge, it wins on the vertex also
    else if (edge->get_decision() == SECOND &&
             edge->get_has_equal_aux_data_in_target(0) &&
             !edge->get_has_equal_aux_data_in_target(1))
    {
      edge->target()->set_decision(SECOND);
    }
    // if the second map is continous, but the first isn't, then if the
    // first map wins on the edge, it wins on the vertex also
    else if (edge->get_decision() == FIRST &&
             !edge->get_has_equal_aux_data_in_target(0) &&
             edge->get_has_equal_aux_data_in_target(1))
    {
      edge->target()->set_decision(FIRST);
    }
  }

  
  // copy the halfedges of a ccb (in from) to the md "to" inside the face inside_face
  void copy_ccb(Ccb_halfedge_circulator hec, // the circulator to insert
                Minimization_diagram_2 &    ,// the original arrangement
                Face_handle inside_face,     // the face in which we insert it
                Minimization_diagram_2 &to,  // the arrangement to which we insert

                Halfedges_map& map_copied_to_orig_halfedges,
                Vertices_map&  map_copied_to_orig_vertices,
                Halfedges_map& map_orig_to_copied_halfedges,
                Vertices_map&  map_orig_to_copied_vertices,
                bool is_outer_ccb) // do we copy an outer (or inner) ccb
               
  {
    Md_accessor to_accessor(to);
    // count the number of faces that are closed by this ccb
    // (it can be more than 1 in degenerate cases, when closed area hangs
    // on a boundary vertex)
    int n_faces_closed = 0;
    
    Ccb_halfedge_circulator hec_begin = hec;
    bool first_he = true;
    Halfedge_handle copied_prev_he;
    do 
    {
      Halfedge_handle hh = hec;

      if (hh->twin()->face() == hh->face() &&
          map_orig_to_copied_halfedges.is_defined(hh))
      {
        // this can happen in the case of antennas, when we get to the same
        // antena halfedge from the other side
        copied_prev_he = map_orig_to_copied_halfedges[hh];
      }
      else
      {
        const X_monotone_curve_2& current_cv = hh->curve();
        if (first_he)
        {
          first_he = false;

          // create the 2 vertices and connect them with the edge
          // copied_prev_he should be directed from copied_source to copied_target
          Vertex_handle copied_source = to_accessor.create_vertex(hh->source()->point());
          Vertex_handle copied_target = to_accessor.create_vertex(hh->target()->point());
          copied_prev_he = to_accessor.insert_in_face_interior_ex(current_cv,
                                                                  inside_face,
                                                                  copied_source,
                                                                  copied_target,
                                                                  hh->direction());
                                                                          
          map_copied_to_orig_halfedges[copied_prev_he] = hh;
          map_orig_to_copied_halfedges[hh] = copied_prev_he;
          map_copied_to_orig_halfedges[copied_prev_he->twin()] = hh->twin();
          map_orig_to_copied_halfedges[hh->twin()] = copied_prev_he->twin();

          map_copied_to_orig_vertices[copied_prev_he->source()] = hh->source();
          map_orig_to_copied_vertices[hh->source()] = copied_prev_he->source();
          map_copied_to_orig_vertices[copied_prev_he->target()] = hh->target();
          map_orig_to_copied_vertices[hh->target()] = copied_prev_he->target();
        }          
        else
        {
          CGAL_assertion(map_copied_to_orig_halfedges[copied_prev_he]->target() == hh->source());

          // insert from vertex: prev_he->target()
          // should check if hh->target is already a vertex in the copied face
          // in which case we should use insert at vertices
          bool use_2_vertices = false;
          Vertex_handle copied_v2;
          if (map_orig_to_copied_vertices.is_defined(hh->target()))
          {
            use_2_vertices = true;
            copied_v2 = map_orig_to_copied_vertices[hh->target()];
          }

          Halfedge_handle copied_new_he;
          if (!use_2_vertices)
          {
            // create vertex for the new target, and insert the new edge
            Vertex_handle copied_target = to_accessor.create_vertex(hh->target()->point());
            copied_new_he = to_accessor.insert_from_vertex_ex(current_cv,
                                                              copied_prev_he,
                                                              copied_target,
                                                              hh->direction());

            
            // the target of copied_new_he is the new vertex, so it is directed
            // the same way as hh in "from"

            // update the vertices maps:
            map_copied_to_orig_vertices[copied_new_he->target()] = hh->target();
            map_orig_to_copied_vertices[hh->target()] = copied_new_he->target();
          }
          else
          {
            ++n_faces_closed;
            
            // in order to insert the new edge we should determine the prev
            // halfedge of copied_v2 - this is done be going backwards on the
            // ccb (in the copied arrangement) until finding the first halfedge
            // with target copied_v2
            // (note that going on twin()->next() is problematic in case that
            // the inner boundary we traverse is made of several faces)
            Halfedge_handle copied_prev_v2 = copied_prev_he;
            while(copied_prev_v2->source() != copied_v2)
              copied_prev_v2 = copied_prev_v2->prev();
            copied_prev_v2 = copied_prev_v2->twin();

            CGAL_assertion_code(
              Halfedge_handle tmp =
                  to_accessor.locate_around_vertex(copied_v2, current_cv);
            );
            CGAL_assertion(tmp == copied_prev_v2);

            bool new_face;
            if (is_outer_ccb)
            {
              // if it is the first face created, and the last halfedge to
              // insert, this is a regular outer ccb, with no special
              // degeneracies (around the current vertices, at least)
              // so we can use the accessor method
              if (n_faces_closed == 1 &&
                  map_orig_to_copied_halfedges.is_defined(hh->next()))
              {
                copied_new_he = to_accessor.insert_at_vertices_ex

                                                     (current_cv,
                                                      copied_prev_he,
                                                      copied_prev_v2,
                                                      hh->direction(),
                                                      new_face);
                CGAL_assertion(new_face);
              }
              else
              {
                // TODO:can we use accessor method?
                copied_new_he = to.insert_at_vertices(current_cv, copied_prev_he, copied_prev_v2);
              }
              // in order to use the accessor version, we need to identify
              // the order in which to pass the halfedges
              // (we should be careful in cases where more than one face is
              // created by the outer ccb
            }
            else // copy inner boundary
            {
              // should always flip the side of the edge, because the face
              // that we close is never the copied face, even in strane
              // situations like this: (two faces thouch in vertex)
              //     ------         |\  /|
              //     | |\ |         | \/ |
              //     | | \|         | /\ |
              //     ---            |/  \|
              //
              //
              copied_new_he = to_accessor.insert_at_vertices_ex(current_cv,
                                                                copied_prev_v2,
                                                                copied_prev_he,
                                                                hh->twin()->direction(),
                                                                new_face);
              CGAL_assertion(new_face);
              copied_new_he = copied_new_he->twin();
            }

            CGAL_assertion(copied_new_he->target() == copied_v2);
          }
          // update the halfedges maps:
          map_copied_to_orig_halfedges[copied_new_he] = hh;
          map_copied_to_orig_halfedges[copied_new_he->twin()] = hh->twin();
          map_orig_to_copied_halfedges[hh] = copied_new_he;
          map_orig_to_copied_halfedges[hh->twin()] = copied_new_he->twin();

          // update the previous he
          copied_prev_he = copied_new_he;
        }
      }
      hec++;
    } while(hec != hec_begin);

  }

  void copy_ccb_unbounded(Ccb_halfedge_circulator hec, // the circulator to insert
                          Minimization_diagram_2 &from,// the original arrangement
                          Minimization_diagram_2 &to,  // the arrangement to which we insert
                          Halfedges_map& map_copied_to_orig_halfedges,
                          Vertices_map&  map_copied_to_orig_vertices,
                          Halfedges_map& map_orig_to_copied_halfedges,
                          Vertices_map&  map_orig_to_copied_vertices)
  {
    //find a non fictitous edge (if there is such one)
    Ccb_halfedge_circulator hec_end = hec;
    Halfedge_handle non_fict;
    do
    {
      if(!hec->is_fictitious())
      {
        non_fict = hec;
        break;
      }
      ++hec;
    }
    while(hec != hec_end);

    Md_accessor from_accessor(from);
    Md_accessor to_accessor(to);

    if(non_fict == Halfedge_handle())
    {
      // all edges are fictitous
      Vertex_handle v_from = from_accessor.top_left_fictitious_vertex();
      Vertex_handle v_to = to_accessor.top_left_fictitious_vertex();

      Halfedge_handle curr_from = v_from->incident_halfedges();
      Halfedge_handle curr_to = v_to->incident_halfedges();
      if(curr_from->direction() == SMALLER)
        curr_from = curr_from->twin();
      else
        curr_from = curr_from->next();

       if(curr_to->direction() == SMALLER)
        curr_to = curr_to->twin();
      else
        curr_to = curr_to->next();

       Halfedge_handle curr_from_end = curr_from;
       do
       {
         map_copied_to_orig_vertices[curr_to->source()] = curr_from->source();
         map_orig_to_copied_vertices[curr_from->source()] = curr_to->source();

         map_copied_to_orig_halfedges[curr_to] = curr_from;
         map_copied_to_orig_halfedges[curr_to->twin()] = curr_from->twin();
         map_orig_to_copied_halfedges[curr_from] = curr_to;
         map_orig_to_copied_halfedges[curr_from->twin()] = curr_to->twin();

         curr_from = curr_from->next();
         curr_to = curr_to->next();

       }while(curr_from != curr_from_end);
    }
    else
    {
      Halfedge_handle he =
        insert_non_intersecting_curve(to, non_fict->curve());
      if(he->direction() != non_fict->direction())
        he = he->twin();
     
      std::list<X_monotone_curve_2> cv_list;
      for(Halfedge_handle e = non_fict->next(); e != non_fict; e = e->next())
      {
        if(!e->is_fictitious())
          cv_list.push_back(e->curve());
      }
      insert_non_intersecting_curves(to, cv_list.begin(), cv_list.end());

      Halfedge_handle curr_edge_from = non_fict;
      do
      {
        map_copied_to_orig_vertices[he->source()] = curr_edge_from->source();
        map_orig_to_copied_vertices[curr_edge_from->source()] = he->source();

        map_copied_to_orig_halfedges[he] = curr_edge_from;
        map_copied_to_orig_halfedges[he->twin()] = curr_edge_from->twin();
        map_orig_to_copied_halfedges[curr_edge_from] = he;
        map_orig_to_copied_halfedges[curr_edge_from->twin()] = he->twin();

        curr_edge_from = curr_edge_from->next();
        he = he->next();
      }
      while(curr_edge_from != non_fict);
    }
  }

  // copy the halfedges of the boundary of face (in from) to the md "to"
  // return a handle to the copied face in "to"
  // precondition: "to" is empty
  Face_handle copy_face(Face_handle face, Minimization_diagram_2& from,
                        Minimization_diagram_2& to,
                        Halfedges_map& map_copied_to_orig_halfedges,
                        Vertices_map&  map_copied_to_orig_vertices)
  {   
    CGAL_precondition(to.number_of_vertices() == 0);
    //CGAL_precondition(!face->is_unbounded());

    //fakes_exist = false;
    Vertices_map  map_orig_to_copied_vertices;
    Halfedges_map map_orig_to_copied_halfedges;
    
    Face_handle to_uf = to.unbounded_face();


    // first deal with outer boundary
    
    Ccb_halfedge_circulator hec = face->outer_ccb();
    if(face->is_unbounded())
      copy_ccb_unbounded(hec, from, to,  // the arrangement to which we insert
                         map_copied_to_orig_halfedges,
                         map_copied_to_orig_vertices,
                         map_orig_to_copied_halfedges,
                         map_orig_to_copied_vertices);
    else
      copy_ccb(hec, from, to_uf, to,
               map_copied_to_orig_halfedges,
               map_copied_to_orig_vertices,
               map_orig_to_copied_halfedges,
               map_orig_to_copied_vertices,
               true);
    CGAL_assertion(is_valid(to));
    

    // we need to find the copied face
    /*Hole_iterator to_uf_hi = to_uf->holes_begin();
    Ccb_halfedge_circulator to_uf_hec = (*to_uf_hi);
    CGAL_assertion(to_uf->number_of_holes() == 1);
    Halfedge_handle to_f_he = to_uf_hec->twin();*/
    CGAL_assertion(map_orig_to_copied_halfedges.is_defined(hec));
    Halfedge_handle hec_to = map_orig_to_copied_halfedges[hec];
    Fac