envelope_divide_and_conquer_3.h

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

        {
          // new face created.
          // 'he' is directed from left to right, so the face to the left
          // of 'he'  is above 'cv.
          Face_handle f;
          if(side == ON_NEGATIVE_SIDE) // the surface is below cv.
          {
            f = he->twin()->face();
            f->set_data(surf);
            he->face()->set_no_data();
          }
          else
          {
            CGAL_assertion(side == ON_POSITIVE_SIDE);
            f = he->face();
            f->set_data(surf);
            he->twin()->face()->set_no_data();
          }

          Ccb_halfedge_circulator face_hec = f->outer_ccb();
          Ccb_halfedge_circulator face_hec_begin = face_hec;
          do 
          {
            face_hec->set_is_equal_data_in_face(true);
            face_hec->set_has_equal_data_in_face(true);
            face_hec->set_has_equal_data_in_target_and_face(true);

            face_hec->twin()->set_is_equal_data_in_face(false);
            face_hec->twin()->set_has_equal_data_in_face(false);
            face_hec->twin()->set_has_equal_data_in_target_and_face(false);

            ++face_hec;
          } 
          while(face_hec != face_hec_begin);
        }
      }
      else
      {
        // the xy-surface is an isolated point
        Point_2 p;
        CGAL_assertion(assign(p, obj));
        assign(p, obj);
        insert_point(result, p);
      }
    }

    // update information in all the edges & vertices to indicate that
    // this surface is the envelope
    Halfedge_iterator hi = result.halfedges_begin();
    for (; hi != result.halfedges_end(); ++hi)
    {
      hi->set_data(surf);
      // since all the edges & vertices have their envelope data equal to the
      // current surface, we can set is/has equal_data_in_target of all
      // halfedges to true
      hi->set_is_equal_data_in_target(true);
      hi->set_has_equal_data_in_target(true);
    }

    Vertex_iterator vi = result.vertices_begin();
    for (; vi != result.vertices_end(); ++vi)
    {
      vi->set_data(surf);
      if (vi->is_isolated())
      {
        // update the is/has equal_data_in_face flags according to the face data
        bool equal_data = !vi->face()->has_no_data();
        vi->set_is_equal_data_in_face(equal_data);
        vi->set_has_equal_data_in_face(equal_data);
      }
    }
  }
  

public:
  
  void merge_envelopes(Minimization_diagram_2& result1,
                       Minimization_diagram_2& result2,
                       Minimization_diagram_2& result)
  {
    // overlay the 2 arrangements
   
    Overlay_2 overlay;
    overlay(result1, result2, result);
  
    CGAL_expensive_assertion_msg(is_valid(result),
                                 "after overlay result is not valid");
       
    // make sure the aux flags are correctly set by the overlay
    //CGAL_assertion(verify_aux_flags(result));

    // for each face, edge and vertex in the result, should calculate
    // which surfaces are on the envelope
    // a face can be cut, or faces can be merged.
   
    // now the minimization diagram might change - we need to keep data in the
    // edges, when they're split
    Keep_edge_data_observer edge_observer(result, this);

    // compute the surface on the envelope for each edge
    // edge can be split as surfaces can intersect (or touch) over it
    std::list<Halfedge_handle> edges_to_resolve;
    Edge_iterator ei = result.edges_begin();
    for (; ei != result.edges_end(); ++ei)
    {
      Halfedge_handle hh = ei;
      // there must be data from at least one map, because all the surfaces
      // are continous
      if (!get_aux_is_set(hh, 0) || !get_aux_is_set(hh, 1))
        continue;
      CGAL_assertion(get_aux_is_set(hh, 0));
      CGAL_assertion(get_aux_is_set(hh, 1));
      CGAL_assertion(!aux_has_no_data(hh, 1) || !aux_has_no_data(hh, 0));
      if (aux_has_no_data(hh, 0) && !aux_has_no_data(hh, 1))
      {
        hh->set_decision(SECOND);
        hh->twin()->set_decision(SECOND);
        continue;
      }
      else if (!aux_has_no_data(hh, 0) && aux_has_no_data(hh, 1))
      {
        hh->set_decision(FIRST);
        hh->twin()->set_decision(FIRST);
        continue;
      }

      bool should_resolve = true;
      #ifdef CGAL_ENVELOPE_SAVE_COMPARISONS
        if (hh->get_has_equal_aux_data_in_face(0) &&
            hh->get_has_equal_aux_data_in_face(1))
          should_resolve = false;

        if (hh->twin()->get_has_equal_aux_data_in_face(0) &&
            hh->twin()->get_has_equal_aux_data_in_face(1))
          should_resolve = false;
      #endif

      // we collect the edges in a list to deal afterwards, because the resolve
      // can split edges, and destroy the iterator
      if (should_resolve)
        edges_to_resolve.push_back(hh);
    }
    // now deal with the edges
    typename std::list<Halfedge_handle>::iterator li;
    for (li = edges_to_resolve.begin(); li != edges_to_resolve.end(); ++li)
    {
      resolver->resolve(*li, result);
     
    }
    edges_to_resolve.clear();
    
    // decompose the result, to have faces without holes
   /* decompose(result);
    CGAL_expensive_assertion_msg(result.is_valid(), 
                       "after decomposition result is not valid");*/

    // compute the surface on the envelope for each face,
    // splitting faces if needed

    std::list<Face_handle> faces_to_split;

    #ifdef CGAL_ENVELOPE_USE_BFS_FACE_ORDER
    // we traverse the faces of result in BFS order to maximize the
    // efficiency gain by the conclusion mechanism of
    // compare_distance_to_envelope results
    // Create a mapping of result faces to indices.
    CGAL::Arr_face_index_map<Minimization_diagram_2> index_map (result);

    // Perform breadth-first search from the unbounded face, and use the BFS
    // visitor to associate each arrangement face with its discover time.
    Faces_order_bfs_visitor<CGAL::Arr_face_index_map<Minimization_diagram_2> >
      bfs_visitor(index_map, faces_to_split, this);
    Face_handle first_face = result.faces_begin();
    /*if (result.number_of_faces() > 1)
      first_face = ++(result.faces_begin());
    */

    boost::breadth_first_search(Dual_Minimization_diagram_2(result),
                                first_face,
                                boost::vertex_index_map(index_map).
                                visitor(bfs_visitor));
    index_map.detach();
#else
    // traverse the faces in arbitrary order  
    Face_iterator fi = result.faces_begin();
    for (; fi != result.faces_end(); ++fi)
    {
      Face_handle fh = fi;
        // if a surface of one map doesn't exist, then we set the second surface
        if (aux_has_no_data(fh, 0) && !aux_has_no_data(fh, 1))
        {
          fh->set_decision(SECOND);
          continue;
        }
        else if (aux_has_no_data(fh, 0) && aux_has_no_data(fh, 1))
        {
          fh->set_decision(EQUAL);
          fh->set_no_data();

          continue;
        }
        else if (!aux_has_no_data(fh, 0) && aux_has_no_data(fh, 1))
        {
          fh->set_decision(FIRST);
          continue;
        }

        // here, we have both surfaces.
        // we save the face in a list for a later treatment, because the
        // face can change and destroy the iterator
        faces_to_split.push_back(fh);
      }
    #endif
        
    deal_with_faces_to_split(faces_to_split, result);

//    #ifndef CGAL_ENVELOPE_SAVE_COMPARISONS
//      hi = result.halfedges_begin();
//      for (; hi != result.halfedges_end(); ++hi, ++hi)
//      {
//        if (!hi->is_decision_set())
//          resolver->resolve(hi, result);
//      }
//    #endif
    
    // detach the edge_observer from result, since no need for it anymore
    edge_observer.detach();

    // compute the surface on the envelope for each vertex
    Vertex_iterator vi = result.vertices_begin();
    for (; vi != result.vertices_end(); ++vi)
    {
      Vertex_handle vh = vi;
      if (vh->is_decision_set())
        continue;
      // there must be data from at least one map, because all the surfaces
      // are continous
      CGAL_assertion(get_aux_is_set(vh, 0));
      CGAL_assertion(get_aux_is_set(vh, 1));
      CGAL_assertion(!aux_has_no_data(vh, 1) || !aux_has_no_data(vh, 0));
      if (aux_has_no_data(vh, 0) && !aux_has_no_data(vh, 1))
      {
        vh->set_decision(SECOND);
        continue;
      }
      else if (!aux_has_no_data(vh, 0) && aux_has_no_data(vh, 1))
      {
        vh->set_decision(FIRST);
        continue;
      }
      resolver->resolve(vh);
     
    }

    CGAL_expensive_assertion_msg(result.is_valid(),
                                 "after resolve result is not valid");

    // make sure that aux_source and decision are set at all features
    // after all resolvings
    CGAL_assertion(check_resolve_was_ok(result));
 
    // make sure the aux flags are correctly after all resolvings
    //CGAL_assertion(verify_aux_flags(result));

    // finally, remove unneccessary edges, between faces  with the same surface
    // (and which are not degenerate)
  
    remove_unneccessary_edges(result);
    CGAL_expensive_assertion_msg(result.is_valid(), 
                       "after remove edges result is not valid");

    // also remove unneccessary vertices (that were created in the process of
    // vertical decomposition but the vertical edge was removed)
    remove_unneccessary_vertices(result);
    CGAL_expensive_assertion_msg(result.is_valid(), 
                       "after remove vertices result is not valid");

    // update is_equal_data and has_equal_data of halfedge->face and
    // vertex->face relations, according to the decision, and the aux
    // similar flags
    update_flags(result);

    // update the envelope surfaces according to the decision and the aux
    // surfaces in aux source
    update_envelope_surfaces_by_decision(result);
    
    // make sure that all the flags are correctly set on the envelope result
    //CGAL_assertion(verify_flags(result));
    CGAL_expensive_assertion_msg(is_valid(result),
                                 "after merge result is not valid");
  }


protected:
 
  void deal_with_faces_to_split(std::list<Face_handle>& faces_to_split,
                                Minimization_diagram_2& result)
  {
    // for each face in faces_to_split, find the intersection over the face,
    // and split the face
    typename std::list<Face_handle>::iterator li;
    for (li = faces_to_split.begin(); li != faces_to_split.end(); ++li)
    {
     
      resolver->resolve(*li, result);
    
    }
    faces_to_split.clear();
  }

  template <class InputIterator>
  bool is_equal_data(const InputIterator & begin1,
                     const InputIterator & end1,
                     const InputIterator & begin2,
                     const InputIterator & end2)
  {
    // insert the input data objects into a set
    std::set<Xy_monotone_surface_3> first(begin1, end1);
    std::set<Xy_monotone_surface_3> second(begin2, end2);

    if (first.size() != second.size())
      return false;

    return (first == second);
  }

  // todo: should remove the uses of this method from this class
  template <class InputIterator>
  bool has_equal_data(const InputIterator & begin1,
                      const InputIterator & end1,
                      const InputIterator & begin2,
                      const InputIterator & end2)
  {
    // insert the input data objects into a set
    std::set<Xy_monotone_surface_3> first(begin1, end1);
    std::set<Xy_monotone_surface_3> second(begin2, end2);
    std::list<Xy_monotone_surface_3> intersection;
    std::set_intersection(first.begin(), first.end(),
                          second.begin(), second.end(),
                          std::back_inserter(intersection));
    return (intersection.size() > 0);
    return true;
  }
  // todo: should remove the uses of this method from this class
  template <class FeatureHandle1, class FeatureHandle2>
  bool has_equal_aux_data(unsigned int id, FeatureHandle1 fh1,
                          FeatureHandle2 fh2)
  {
    Envelope_data_iterator begin1, end1, begin2, end2;
    get_aux_data_iterators(id, fh1, begin1, end1);
    get_aux_data_iterators(id, fh2, begin2, end2);
    bool has_eq = has_equal_data(begin1, end1, begin2, end2);
    return has_eq;
  }