envelope_divide_and_conquer_3.h

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

    Face_handle f;

    if (assign(v, o))
      return v->has_equal_data(begin, end);
    else if (assign(h, o))
      return h->has_equal_data(begin, end);
    else
    {
      CGAL_assertion(assign(f, o));
      assign(f, o);
      return f->has_equal_data(begin, end);
    }
  }

  void print_decisions(Minimization_diagram_2& result)
  {
    Face_iterator fi = result.faces_begin();
    for (; fi != result.faces_end(); ++fi)
    {
      if (fi->is_unbounded())
        continue;
      Face_handle fh = fi;
      Ccb_halfedge_circulator face_hec = fh->outer_ccb();
      Ccb_halfedge_circulator face_hec_begin = face_hec;
      do {
        ++face_hec;
      } while(face_hec != face_hec_begin);

      Hole_iterator inner_iter = fh->holes_begin();
      for (; inner_iter != fh->holes_end(); ++inner_iter)

      {
        face_hec = face_hec_begin = (*inner_iter);
        do {
          ++face_hec;
        } while(face_hec != face_hec_begin);
      }
    }
  }
   

  // confirm that aux source and decision are set over all minimization 
  // diagram features
  bool check_resolve_was_ok(Minimization_diagram_2& result)
  {
    bool all_ok = true;
    Vertex_iterator vi = result.vertices_begin();
    for (; vi != result.vertices_end(); ++vi)
    {
      Vertex_handle vh = vi;
      /*if (vh->get_is_fake())
        continue;
      */

      all_ok &= (vh->get_aux_is_set(0));
      CGAL_assertion_msg(all_ok, "aux source (0) not set over vertex");
      all_ok &= (vh->get_aux_is_set(1));
      CGAL_assertion_msg(all_ok, "aux source (1) not set over vertex");
      all_ok &= (vh->is_decision_set());
      CGAL_assertion_msg(all_ok, "decision was not set over vertex");

    }
    Halfedge_iterator hi = result.halfedges_begin();
    for (; hi != result.halfedges_end(); ++hi)
    {
      Halfedge_handle hh = hi;
     /* if (hh->get_is_fake())
      * continue;
      */

      all_ok &= (hh->get_aux_is_set(0));
      CGAL_assertion_msg(all_ok, "aux source (0) not set over edge");
      all_ok &= (hh->get_aux_is_set(1));
      CGAL_assertion_msg(all_ok, "aux source (1) not set over edge");
      all_ok &= (hh->is_decision_set());
      CGAL_assertion_msg(all_ok, "decision was not set over edge");
    }
    Face_iterator fi = result.faces_begin();
    for (; fi != result.faces_end(); ++fi)
    {
      Face_handle fh = fi;

      all_ok &= (fh->get_aux_is_set(0));
      CGAL_assertion_msg(all_ok, "aux source (0) not set over face");
      all_ok &= (fh->get_aux_is_set(1));
      CGAL_assertion_msg(all_ok, "aux source (1) not set over face");
      all_ok &= (fh->is_decision_set());
      CGAL_assertion_msg(all_ok, "decision was not set over face");
    }
    return all_ok;
  }

  // confirm that envelope data is set over all minimization diagram features
  // and that no fake feature are left
  bool is_envelope_valid(Minimization_diagram_2& result)
  {
    bool all_ok = true;
    Vertex_iterator vi = result.vertices_begin();
    for (; vi != result.vertices_end(); ++vi)
    {
      Vertex_handle vh = vi;
      
      all_ok &= (vh->get_is_set());
      CGAL_assertion_msg(all_ok, "data not set over vertex");
      all_ok &= (!vh->has_no_data());

      CGAL_assertion_msg(all_ok, "data empty over vertex");      
     /* all_ok &= (!vh->get_is_fake());*/
      CGAL_assertion_msg(all_ok, "fake vertex in envelope");
    }
    Halfedge_iterator hi = result.halfedges_begin();
    for (; hi != result.halfedges_end(); ++hi)
    {
      Halfedge_handle hh = hi;
      
      all_ok &= (hh->get_is_set());
      if (!all_ok)
        std::cout << "edge: " << hh->curve() << std::endl;
      CGAL_assertion_msg(all_ok, "data not set over edge");
      all_ok &= (!hh->has_no_data());
      if (!all_ok)

        std::cout << "edge: " << hh->curve() << std::endl;
      CGAL_assertion_msg(all_ok, "data empty over edge");

      /*all_ok &= (!hh->get_is_fake());*/
      CGAL_assertion_msg(all_ok, "fake edge in envelope");
    }
    Face_iterator fi = result.faces_begin();
    for (; fi != result.faces_end(); ++fi)
    {
      Face_handle fh = fi;
      all_ok &= (fh->get_is_set());
      CGAL_assertion_msg(all_ok, "data not set over face");
    }
    return all_ok;
  }
    
  // observer for the minimization diagram
  // keeps the relevant data in the new faces
  class Keep_face_data_observer : public Md_observer
  {
  public:
    typedef typename Minimization_diagram_2::Face_handle Face_handle;
    
    Keep_face_data_observer(Minimization_diagram_2& arr) :
      Md_observer(arr)
    {}

    virtual void after_split_face(Face_handle org_f,
                                  Face_handle new_f,
                                  bool is_hole)
    {
      // update data in the new face from the original face
      if (org_f->get_aux_is_set(0))
        new_f->set_aux_source(0, org_f->get_aux_source(0));
      if (org_f->get_aux_is_set(1))
        new_f->set_aux_source(1, org_f->get_aux_source(1));
      if (org_f->is_decision_set())
        new_f->set_decision(org_f->get_decision());
    }
  };

  

  // observer for the minimization diagram
  // keeps the relevant data in the new edges & vertices
  class Keep_edge_data_observer : public Md_observer
  {
  public:
    typedef typename Minimization_diagram_2::Halfedge_handle   Halfedge_handle;
    typedef typename Minimization_diagram_2::Vertex_handle     Vertex_handle;
    typedef typename Minimization_diagram_2::X_monotone_curve_2 
                                                            X_monotone_curve_2;

    typedef typename Envelope_divide_and_conquer_3<Traits, 
                                                   Minimization_diagram_2,
                                                   EnvelopeResolver_3, 
                                                   Overlay_2>::Self Self;
    Keep_edge_data_observer(Minimization_diagram_2& arr,
                            Self* b = NULL) :
      Md_observer(arr), base(b)
    {
      CGAL_assertion(base);
    }

    /*virtual void before_split_edge (Halfedge_handle e,
                                    Vertex_handle v,
                                    const X_monotone_curve_2& c1,
                                    const X_monotone_curve_2& c2)
    {
    }*/

    virtual void after_split_edge(Halfedge_handle he1, Halfedge_handle he2)
    {
      // update data of the new vertex, which is the common vertex of he1 and 
      // he2, and of the new edge according to the data in the original edge
      CGAL_assertion(he2->source() == he1->target());

      Vertex_handle new_vertex;
//      if (he2->source() == he1->target() ||
//          he2->source() == he1->source())
      new_vertex = he2->source();
//      else
//        new_vertex = he2->target();

      CGAL_assertion(!new_vertex->is_decision_set());
      CGAL_assertion(!new_vertex->get_aux_is_set(0));
      CGAL_assertion(!new_vertex->get_aux_is_set(1));

      // find the halfedge with the additional information, to be copied into
      // the second halfedge
      Halfedge_handle org_he = he1, new_he = he2;
      
      if (org_he->is_decision_set())
      {
        new_he->set_decision(org_he->get_decision());
        new_he->twin()->set_decision(org_he->get_decision());
        new_vertex->set_decision(org_he->get_decision());
      }        
      if (org_he->get_aux_is_set(0))
      {
        new_vertex->set_aux_source(0, org_he->get_aux_source(0));
        new_he->set_aux_source(0, org_he->get_aux_source(0));
        new_he->twin()->set_aux_source(0, org_he->twin()->get_aux_source(0));
      }      
      if (org_he->get_aux_is_set(1))
      {
        new_vertex->set_aux_source(1, org_he->get_aux_source(1));
        new_he->set_aux_source(1, org_he->get_aux_source(1));
        new_he->twin()->set_aux_source(1, org_he->twin()->get_aux_source(1));
      }

      /*new_he->set_is_fake(org_he->get_is_fake());*/
      /*new_he->twin()->set_is_fake(org_he->get_is_fake());*/
      /*new_vertex->set_is_fake(org_he->get_is_fake());*/

      // update all new bools
      new_he->
        set_is_equal_aux_data_in_face(0, org_he->get_is_equal_aux_data_in_face(0));
      new_he->twin()->set_is_equal_aux_data_in_face(0, org_he->twin()->get_is_equal_aux_data_in_face(0));
      new_he->set_is_equal_aux_data_in_face(1, org_he->get_is_equal_aux_data_in_face(1));
      new_he->twin()->set_is_equal_aux_data_in_face(1, org_he->twin()->get_is_equal_aux_data_in_face(1));

      new_he->set_has_equal_aux_data_in_face(0, org_he->get_has_equal_aux_data_in_face(0));
      new_he->twin()->set_has_equal_aux_data_in_face(0, org_he->twin()->get_has_equal_aux_data_in_face(0));
      new_he->set_has_equal_aux_data_in_face(1, org_he->get_has_equal_aux_data_in_face(1));
      new_he->twin()->set_has_equal_aux_data_in_face(1, org_he->twin()->get_has_equal_aux_data_in_face(1));

      // new_he->target is the original edge's target, and org_he->target is the new vertex
      new_he->set_is_equal_aux_data_in_target(0, org_he->get_is_equal_aux_data_in_target(0));
      new_he->set_is_equal_aux_data_in_target(1, org_he->get_is_equal_aux_data_in_target(1));
      org_he->set_is_equal_aux_data_in_target(0, true);
      org_he->set_is_equal_aux_data_in_target(1, true);
      new_he->set_has_equal_aux_data_in_target(0, org_he->get_has_equal_aux_data_in_target(0));
      new_he->set_has_equal_aux_data_in_target(1, org_he->get_has_equal_aux_data_in_target(1));
      org_he->set_has_equal_aux_data_in_target(0, !base->aux_has_no_data(org_he, 0));
      org_he->set_has_equal_aux_data_in_target(1, !base->aux_has_no_data(org_he, 1));
      new_he->set_has_equal_aux_data_in_target_and_face
        (0, org_he->get_has_equal_aux_data_in_target_and_face(0));
      new_he->set_has_equal_aux_data_in_target_and_face
        (1, org_he->get_has_equal_aux_data_in_target_and_face(1));
      org_he->set_has_equal_aux_data_in_target_and_face
        (0, org_he->get_has_equal_aux_data_in_face(0));
      org_he->set_has_equal_aux_data_in_target_and_face
        (1, org_he->get_has_equal_aux_data_in_face(1));

      // new_he->source is the new vertex, and org_he->source is the original vertex
      new_he->twin()->set_is_equal_aux_data_in_target(0, true);
      new_he->twin()->set_is_equal_aux_data_in_target(1, true);
      new_he->twin()->set_has_equal_aux_data_in_target(0,!base->aux_has_no_data(org_he, 0));
      new_he->twin()->set_has_equal_aux_data_in_target(1,!base->aux_has_no_data(org_he, 1));

      new_he->twin()->set_has_equal_aux_data_in_target_and_face
        (0, org_he->twin()->get_has_equal_aux_data_in_face(0));
      new_he->twin()->set_has_equal_aux_data_in_target_and_face
        (1, org_he->twin()->get_has_equal_aux_data_in_face(1));
    }
  protected:
    Self *base;
  };

#ifdef CGAL_ENVELOPE_USE_BFS_FACE_ORDER

  // A BFS visitor class which collects the faces that need resolving
  // in a list according to the discover time
  // In our case graph vertices represent minimization diagram faces
  template <class IndexMap>
  class Faces_order_bfs_visitor : public boost::default_bfs_visitor
  {
  public:
    typedef typename Envelope_divide_and_conquer_3<Traits,
                                                   Minimization_diagram_2,
                                                   EnvelopeResolver_3,
                                                   Overlay_2>::Self Self;

  protected:
    const IndexMap          *index_map; // Mapping vertices to indices
    std::list<Face_handle>& faces;      // The ordered faces list
    Self                    *base;

  public:

    // Constructor.
    Faces_order_bfs_visitor(const IndexMap& imap, std::list<Face_handle>& f,
                            Self* b = NULL) :
      index_map (&imap),
      faces(f),
      base(b)
    {
      CGAL_assertion(base);
    }

    // Write the discover time for a given vertex.
    template <typename Vertex, typename Graph>

    void discover_vertex (Vertex fh, const Graph& )
    {
      // first we check if we can set the decision immediately
      // if a surface of one map doesn't exist, then we set the second surface
      if (base->aux_has_no_data(fh, 0) && !base->aux_has_no_data(fh, 1))
        fh->set_decision(SECOND);
      else if (base->aux_has_no_data(fh, 0) && base->aux_has_no_data(fh, 1))
      {

        fh->set_decision(EQUAL);
        fh->set_no_data();
      }
      else if (!base->aux_has_no_data(fh, 0) && base->aux_has_no_data(fh, 1))
        fh->set_decision(FIRST);
      else
        // 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.push_back(fh);
    }
  };
#endif
  
protected:
  Envelope_resolver         *resolver;
  Traits                    *traits;
  // Should we evetually free the traits object
  bool                      own_traits; 
  bool                      m_is_lower;
};

CGAL_END_NAMESPACE

#endif //CGAL_ENVELOPE_DIVIDE_AND_CONQUER_3_H