envelope_divide_and_conquer_3.h

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

        (1, he1->twin()->get_has_equal_aux_data_in_target_and_face(1));

      // order of halfedges for merge doesn't matter
      Halfedge_handle new_edge = result.merge_edge(he1, he2 ,c);

      CGAL_assertion(new_edge->is_decision_set());

      CGAL_expensive_assertion_msg(result.is_valid(), 
                         "after remove vertex result is not valid");
    }

    // remove isolated vertices

    typename std::list<Vertex_handle>::iterator li;
    for (li = isolated_to_remove.begin(); li != isolated_to_remove.end(); ++li)
    {
      Vertex_handle vh = *li;
      CGAL_assertion(vh->is_isolated());
      CGAL_assertion(can_remove_isolated_vertex(vh));

      result.remove_isolated_vertex(vh);
    }
  }

  template <class FeatureHandle>
  void update_envelope_surfaces_by_decision(FeatureHandle fh)
  {
    CGAL::Dac_decision decision = fh->get_decision();

    Halfedge_handle h;
    Vertex_handle v;
    Face_handle f;

    if (decision == FIRST || decision == BOTH)
    {
      Envelope_data_iterator begin, end;
      get_aux_data_iterators(0, fh, begin, end);
      fh->set_data(begin, end);
    }
    if (decision == SECOND || decision == BOTH)
    {
      // copy data from second envelope
      Envelope_data_iterator begin, end;
      get_aux_data_iterators(1, fh, begin, end);

      if (decision == SECOND)
        fh->set_data(begin, end);
      else
        fh->add_data(begin, end);
    }    
  }

  // foreach feature of result, update the envelope surfaces, according
  // to the decision done over this feature, and its aux sources
  void update_envelope_surfaces_by_decision(Minimization_diagram_2& result)
  {
    // vertices
    Vertex_iterator vi = result.vertices_begin();
    for (; vi != result.vertices_end(); ++vi)
    {
      update_envelope_surfaces_by_decision(vi);
    }
    
    // edges
    Halfedge_iterator hi = result.halfedges_begin();
    for (; hi != result.halfedges_end(); ++hi)
    {
      update_envelope_surfaces_by_decision(hi);
    }
    
    // faces
    Face_iterator fi = result.faces_begin();
    for (; fi != result.faces_end(); ++fi)
      update_envelope_surfaces_by_decision(fi);
  }

  // update the is_equal/has_equal flags of the result envelope
  void update_edge_face_flags(Halfedge_handle h)
  {
    bool is_equal, has_equal;
    is_equal = (h->get_decision() == h->face()->get_decision());
    // has equal can be true even if the decision is not the same,
    // but has same surfaces, i.e. one of the features got BOTH
    // decision, and the other didn't
    has_equal = (h->get_decision() == h->face()->get_decision() ||
                 h->get_decision() == BOTH ||
                 h->face()->get_decision() == BOTH);

    CGAL::Dac_decision decision = h->face()->get_decision();
    bool is_equal_first = (h->get_is_equal_aux_data_in_face(0));
    bool has_equal_first = (h->get_has_equal_aux_data_in_face(0));
    bool is_equal_second = (h->get_is_equal_aux_data_in_face(1));
    bool has_equal_second = (h->get_has_equal_aux_data_in_face(1));
    if (decision == FIRST)
    {
      is_equal &= is_equal_first;
      has_equal &= has_equal_first;
    }
    else if (decision == SECOND)
    {
      is_equal &= is_equal_second;
      has_equal &= has_equal_second;
    }
    else
    {
      is_equal &= (is_equal_first & is_equal_second);
      // we check if the halfedge has a different decision, and if so,

      // we update the flag according to the halfedge decision
      decision = h->get_decision();
      if (decision == FIRST)
      has_equal &= has_equal_first;
      else if (decision == SECOND)
      has_equal &= has_equal_second;
      else      
      has_equal &= (has_equal_first & has_equal_second);
    }

    h->set_is_equal_data_in_face(is_equal);
    h->set_has_equal_data_in_face(has_equal);
  }
  void update_edge_target_flags(Halfedge_handle h)
  {
    bool is_equal, has_equal;

    is_equal = (h->get_decision() == h->target()->get_decision());
    // has equal can be true even if the decision is not the same,
    // but has same surfaces, i.e. one of the features got BOTH
    // decision, and the other didn't
    has_equal = (h->get_decision() == h->target()->get_decision() ||
                 h->get_decision() == BOTH ||
                 h->target()->get_decision() == BOTH);

    CGAL::Dac_decision decision = h->get_decision();
    bool is_equal_first = (h->get_is_equal_aux_data_in_target(0));
    bool has_equal_first = (h->get_has_equal_aux_data_in_target(0));
    bool is_equal_second = (h->get_is_equal_aux_data_in_target(1));
    bool has_equal_second = (h->get_has_equal_aux_data_in_target(1));
    if (decision == FIRST)
    {
      is_equal &= is_equal_first;
      has_equal &= has_equal_first;
    }

    else if (decision == SECOND)
    {
      is_equal &= is_equal_second;
      has_equal &= has_equal_second;
    }
    else
    {
      is_equal &= (is_equal_first & is_equal_second);
      // we check if the vertex has a different decision, and if so,
      // we update the flag according to the vertex decision
      decision = h->target()->get_decision();
      if (decision == FIRST)
      has_equal &= has_equal_first;
      else if (decision == SECOND)
      has_equal &= has_equal_second;

      else      
      has_equal &= (has_equal_first & has_equal_second);
    }
    h->set_is_equal_data_in_target(is_equal);
    h->set_has_equal_data_in_target(has_equal);
  }
  void update_target_face_flags(Halfedge_handle h)
  {
    bool has_equal;
    // has equal can be true even if the decision is not the same,
    // but has same surfaces, i.e. one of the features got BOTH
    // decision, and the other didn't
    has_equal = (h->face()->get_decision() == h->target()->get_decision() ||
                 h->face()->get_decision() == BOTH ||
                 h->target()->get_decision() == BOTH);

    CGAL::Dac_decision decision = h->face()->get_decision();
    bool has_equal_first = (h->get_has_equal_aux_data_in_target_and_face(0));
    bool has_equal_second = (h->get_has_equal_aux_data_in_target_and_face(1));
    if (decision == FIRST)
      has_equal &= has_equal_first;
    else if (decision == SECOND)
      has_equal &= has_equal_second;
    else
    {
      // we check if the vertex has a different decision, and if so,
      // we update the flag according to the vertex decision
      decision = h->target()->get_decision();
      if (decision == FIRST)
        has_equal &= has_equal_first;
      else if (decision == SECOND)
        has_equal &= has_equal_second;

      else      
        has_equal &= (has_equal_first & has_equal_second);
    }
    h->set_has_equal_data_in_target_and_face(has_equal);
  }

  void update_vertex_face_flags(Vertex_handle v, Face_handle f)
  {
    bool is_equal, has_equal;
    is_equal = (v->get_decision() == f->get_decision());
    // has equal can be true even if the decision is not the same,
    // but has same surfaces, i.e. one of the features got BOTH
    // decision, and the other didn't

    has_equal = (v->get_decision() == f->get_decision() ||
                 v->get_decision() == BOTH ||
                 f->get_decision() == BOTH);

    CGAL::Dac_decision decision = v->get_decision();
    bool is_equal_first = (v->get_is_equal_aux_data_in_face(0));
    bool has_equal_first = (v->get_has_equal_aux_data_in_face(0));
    bool is_equal_second = (v->get_is_equal_aux_data_in_face(1));
    bool has_equal_second = (v->get_has_equal_aux_data_in_face(1));
    if (decision == FIRST)
    {
      is_equal &= is_equal_first;
      has_equal &= has_equal_first;
    }
    else if (decision == SECOND)
    {
      is_equal &= is_equal_second;
      has_equal &= has_equal_second;
    }
    else
    {
      is_equal &= (is_equal_first & is_equal_second);
      // we check if the face has a different decision, and if so,
      // we update the flag according to the face decision
      decision = f->get_decision();
      if (decision == FIRST)
      has_equal &= has_equal_first;
      else if (decision == SECOND)
        has_equal &= has_equal_second;
      else      
      has_equal &= (has_equal_first & has_equal_second);
    }
    v->set_is_equal_data_in_face(is_equal);
    v->set_has_equal_data_in_face(has_equal);
  }

  void update_flags(Minimization_diagram_2& result)
  {    
    // edges
    Halfedge_iterator hi = result.halfedges_begin();
    for (; hi != result.halfedges_end(); ++hi)
    {
      update_edge_face_flags(hi);
      update_edge_target_flags(hi);
      update_target_face_flags(hi);
    }

    // vertices
    Vertex_iterator vi = result.vertices_begin();
    for (; vi != result.vertices_end(); ++vi)
      if (vi->is_isolated())
    update_vertex_face_flags(vi, vi->face());

  }

  template <class FeatureHandle>
  bool get_aux_is_set(FeatureHandle fh, unsigned int id)
  {
    return fh->get_aux_is_set(id);
  }
 
  template <class FeatureHandle>
  bool aux_has_no_data(FeatureHandle fh, unsigned int id)
  {
    const Object& o = fh->get_aux_source(id);
    Halfedge_handle h;
    Vertex_handle v;
    Face_handle f;
   
    // aux source of a face must be a face!
    // aux source of a halfedge can be face or halfedge
    // aux source of a vertex can be face, halfedge or vertex
    // this is why we start with a check for a face, then halfedge
    // and last vertex
    if (assign(f, o))
      return f->has_no_data();
    else if (assign(h, o))
      return h->has_no_data();
    else
    {
      CGAL_assertion_code(bool b =)
      assign(v, o);
      CGAL_assertion(b);
      return v->has_no_data();
    }
  }

protected:

  //***************************************************************************
  // methods for assertion and checking
  //***************************************************************************

  void get_data_iterators(Object aux_src,
                          Envelope_data_iterator& begin,
                          Envelope_data_iterator& end)
  {
    CGAL_assertion(!aux_src.is_empty());
    Vertex_handle v;
    Halfedge_handle h;
    Face_handle f;

    if (assign(v, aux_src))
    {
      begin = v->begin_data();
      end = v->end_data();
    }
    else if (assign(h, aux_src))
    {
      begin = h->begin_data();
      end = h->end_data();
    }
    else
    {
      CGAL_assertion(assign(f, aux_src));
      assign(f, aux_src);
      begin = f->begin_data();
      end = f->end_data();
    }
  }
  bool is_equal_data(Object o,
                     Envelope_data_iterator begin,
                     Envelope_data_iterator end)
  {
    CGAL_assertion(!o.is_empty());
    Vertex_handle v;
    Halfedge_handle h;
    Face_handle f;

    if (assign(v, o))
      return v->is_equal_data(begin, end);
    else if (assign(h, o))
      return h->is_equal_data(begin, end);
    else
    {
      CGAL_assertion(assign(f, o));
      assign(f, o);
      return f->is_equal_data(begin, end);
    }
  }
  bool has_equal_data(Object o,
                      Envelope_data_iterator begin,
                      Envelope_data_iterator end)
  {
    CGAL_assertion(!o.is_empty());
    Vertex_handle v;
    Halfedge_handle h;