envelope_divide_and_conquer_3.h

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

  // Remove unneccessary edges, between faces with the same surface
  // (and which are not degenerate)
  void remove_unneccessary_edges(Minimization_diagram_2& result)
  {
    // collect all those edges in this list, and remove them all at the end
    // (thus, not destroying the iterator)
    std::list<Halfedge_handle> edges;
    Halfedge_iterator hi = result.halfedges_begin();
    for (; hi != result.halfedges_end(); ++hi, ++hi)
    {
      Halfedge_handle hh = hi;

      if (can_remove_edge(hh))
      {
        edges.push_back(hh);
      }
    }
    
    for (typename std::list<Halfedge_handle>::iterator ci = edges.begin();
         ci != edges.end(); ++ci)
    {
      // if the endpoints become isolated after the removal we need to remove
      // them if they have the same data as the edge
      Halfedge_handle h = *ci;
      Vertex_handle src = h->source(), trg = h->target();
      Face_handle h_face = h->face();
      bool remove_src = can_remove_edge_target(h->twin()),
           remove_trg = can_remove_edge_target(h);
      bool src_is_equal_0 = (h->twin()->get_is_equal_aux_data_in_face(0) &&
                             h->twin()->get_is_equal_aux_data_in_target(0));
      bool src_is_equal_1 = (h->twin()->get_is_equal_aux_data_in_face(1) &&
                             h->twin()->get_is_equal_aux_data_in_target(1));
      bool trg_is_equal_0 = (h->get_is_equal_aux_data_in_face(0) &&
                             h->get_is_equal_aux_data_in_target(0));
      bool trg_is_equal_1 = (h->get_is_equal_aux_data_in_face(1) &&
                             h->get_is_equal_aux_data_in_target(1));
      bool src_has_equal_0 =
        h->twin()->get_has_equal_aux_data_in_target_and_face(0);
      bool src_has_equal_1 =
        h->twin()->get_has_equal_aux_data_in_target_and_face(1);
      bool trg_has_equal_0 = h->get_has_equal_aux_data_in_target_and_face(0);
      bool trg_has_equal_1 = h->get_has_equal_aux_data_in_target_and_face(1);

      result.remove_edge(*ci, remove_src, remove_trg);
      // otherwise, we should make sure, they will not be removed
      // the first check is needed since if the vertex was removed, then the
      // handle is invalid
      if (!remove_src && src->is_isolated())
      {
        // to be precise we copy from the halfedge-face and halfedge-target
        // relations
        src->set_is_equal_aux_data_in_face(0, src_is_equal_0);
        src->set_is_equal_aux_data_in_face(1, src_is_equal_1);
        // todo: the has_equal flags should be updated also
        // make sure h_face is also src face
        CGAL_assertion(h_face == src->face());
        // CGAL_assertion(src_has_equal_0 ==
        // has_equal_aux_data(0, src, h_face));
        // CGAL_assertion(src_has_equal_1 ==
        // has_equal_aux_data(1, src, h_face));
        src->set_has_equal_aux_data_in_face(0, src_has_equal_0);
        src->set_has_equal_aux_data_in_face(1, src_has_equal_1);
      }
      if (!remove_trg && trg->is_isolated())
      {
        trg->set_is_equal_aux_data_in_face(0, trg_is_equal_0);
        trg->set_is_equal_aux_data_in_face(1, trg_is_equal_1);
        // make sure h_face is also trg face
        CGAL_assertion(h_face == trg->face());
        // CGAL_assertion(trg_has_equal_0 ==
        // has_equal_aux_data(0, trg, h_face));
        // CGAL_assertion(trg_has_equal_1 ==
        // has_equal_aux_data(1, trg, h_face));
        trg->set_has_equal_aux_data_in_face(0, trg_has_equal_0);
        trg->set_has_equal_aux_data_in_face(1, trg_has_equal_1);
      }
    }
  }

  template <class FeatureHandle>
  void get_aux_data_iterators(unsigned int id, FeatureHandle fh,
                              Envelope_data_iterator& begin,
                              Envelope_data_iterator& end)
  {
    Halfedge_handle h;
    Vertex_handle v;
    Face_handle f;

    const Object& o = fh->get_aux_source(id);
    CGAL_assertion(!o.is_empty());

    // 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))
    {
      begin = f->begin_data();
      end = f->end_data();
    }
    else if (assign(h, o))
    {
      begin = h->begin_data();
      end = h->end_data();
    }
    else
    {
      CGAL_assertion_code(bool b = )
      assign(v, o);
      CGAL_assertion(b);
      begin = v->begin_data();
      end = v->end_data();
    }
  }
  
  // check if we can remove the edge from the envelope
  // this can be done if the envelope surfaces on the edge are the same as
  // the envelope surfaces on both sides of the edge
  // (or if the edge is fake, i.e. created in the vd process)
  bool can_remove_edge(Halfedge_handle hh)
  {
    Face_handle f1 = hh->face(), f2 = hh->twin()->face();
      
    // we check if the decision done on the edge is equal to the decision
    // done on the faces. if not, then the envelope surfaces must differ
    CGAL_assertion(hh->is_decision_set() && f1->is_decision_set() &&
                   f2->is_decision_set());
    if (hh->get_decision() != f1->get_decision() ||
        hh->get_decision() != f2->get_decision())
    {
      return false;
    }

    // now, check the equality of the surfaces list according to the decision
    CGAL::Dac_decision decision = hh->get_decision();
    bool equal_first = (hh->get_is_equal_aux_data_in_face(0) &&
                        hh->twin()->get_is_equal_aux_data_in_face(0));
    bool equal_second = (hh->get_is_equal_aux_data_in_face(1) &&
                         hh->twin()->get_is_equal_aux_data_in_face(1));

    if (decision == FIRST)
      return equal_first;
   
    if (decision == SECOND)
      return equal_second;
    
    return (equal_first && equal_second);
  }


  // check if can remove the edge's target if we remove the edge
  // this means that the target has the same envelope information as the edge
  bool can_remove_edge_target(Halfedge_handle h)
  {
    if(h->target()->is_at_infinity())
      return false;

    Vertex_handle v = h->target();
    /*if (v->get_is_fake() && !v->is_decision_set())
      return true;
   

    if (h->get_is_fake() && !h->is_decision_set())
    {
      h->set_decision(h->face()->get_decision());
      h->twin()->set_decision(h->get_decision());
    }*/
    CGAL_assertion(v->is_decision_set());
    CGAL_assertion(h->is_decision_set());

    // if the decision done on the vertex and edge are different,
    // the envelope differs too.
    if (h->get_decision() != v->get_decision())
      return false;

    // now, check the equality of the surfaces list according to the decision

    CGAL::Dac_decision decision = h->get_decision();
    bool equal_first = (h->get_is_equal_aux_data_in_target(0));
    bool equal_second = (h->get_is_equal_aux_data_in_target(1));

    if (decision == FIRST)
      return equal_first;
   
    if (decision == SECOND)
      return equal_second;
    
    return (equal_first && equal_second);
  }
  
  // check if we can remove an isolated vertex from the envelope
  // this can be done if the envelope surfaces on the vertex are the same as
  // the envelope surfaces on its incident face
  bool can_remove_isolated_vertex(Vertex_handle vh)
  {
    Face_handle f = vh->face();
    CGAL_assertion(vh->is_decision_set() && f->is_decision_set());
    // if the decision done on the vertex and face are different,
    // the envelope differs too.
    if (vh->get_decision() != f->get_decision())
      return false;

    // now, check the equality of the surfaces list according to the decision
    CGAL::Dac_decision decision = vh->get_decision();

    bool equal_first = (vh->get_is_equal_aux_data_in_face(0));
    bool equal_second = (vh->get_is_equal_aux_data_in_face(1));

    if (decision == FIRST)
      return equal_first;
    
    if (decision == SECOND)
      return equal_second;
    
    return (equal_first && equal_second);
  }

  // check if we can remove a (non-isolated) vertex from the envelope
  // we check only from the combinatoric aspect of the envelope, not from
  // the geometric point of view (i.e. if the curves can merge)
  // this can be done if the envelope surfaces on the vertex are the same as
  // the envelope surfaces on its 2 incident halfedges
  bool combinatorically_can_remove_vertex(Vertex_handle vh)
  {
    Halfedge_around_vertex_circulator hec1 = vh->incident_halfedges();
    Halfedge_around_vertex_circulator hec2 = hec1++;
    Halfedge_handle he1 = hec1, he2 = hec2;
    CGAL_assertion(he1 != he2);
    CGAL_assertion(he1->is_decision_set() && he2->is_decision_set());
    
    /*if (vh->get_is_fake())
    {
      CGAL_assertion(he1->get_decision() == he2->get_decision());
      return true;
    }*/
    
    CGAL_assertion(vh->is_decision_set());
    // if the decision done on the vertex and its incident halfedges are
    // different, the envelope differs too.
    CGAL_assertion(vh == he1->target() && vh == he2->target());
    if (vh->get_decision() != he1->get_decision() ||
        vh->get_decision() != he2->get_decision())
      return false;

    // now, check the equality of the surfaces list according to the decision
    CGAL::Dac_decision decision = vh->get_decision();
    bool equal_first = (he1->get_is_equal_aux_data_in_target(0) &&
                        he2->get_is_equal_aux_data_in_target(0));
    bool equal_second = (he1->get_is_equal_aux_data_in_target(1) &&
                         he2->get_is_equal_aux_data_in_target(1));

    if (decision == FIRST)
      return equal_first;
    
    if (decision == SECOND)
      return equal_second;

    return (equal_first && equal_second);
  }
  
  // Remove unneccessary vertices, which have degree 2, and the 2 curves 
  // can be merged
  // (and which are not degenerate)
  void remove_unneccessary_vertices(Minimization_diagram_2& result)
  {
    // we have 2 types of unneccessary vertices: those with degree 2 (that
    // satisfy all the conditions below), and isolated vertices that have the
    // same envelope information as the face they're contained in.
    
    // all the vertices that don't have their data set, are those vertices
    // on vertical edges, created in the decomposition process,
    // and are not neccessary

    // also those vertices with degree 2, that can merge their 2 edges and 
    // with same data as both these edges, can be removed
    
    // collect all vertices candidate to remove in this list,
    // and remove the correct ones at the end
    // (thus, not destroying the iterator)
    std::list<Vertex_handle> candidates_to_remove;
    std::list<Vertex_handle> isolated_to_remove;

    Vertex_iterator vi = result.vertices_begin();
    for (; vi != result.vertices_end(); ++vi)
    {
      Vertex_handle vh = vi;
      if (!vh->is_decision_set() || vh->degree() == 2)
        candidates_to_remove.push_back(vh);
      else if (vh->is_isolated() && can_remove_isolated_vertex(vh))
        isolated_to_remove.push_back(vh);
    }

    typename Traits::Merge_2 curves_merge = traits->merge_2_object();
    typename Traits::Are_mergeable_2 curves_can_merge = 
                                              traits->are_mergeable_2_object();

    // check the candidates and remove if necessary
    typename std::list<Vertex_handle>::iterator ci;
    for (ci = candidates_to_remove.begin(); 
        ci != candidates_to_remove.end(); ++ci)
    {
      Vertex_handle vh = *ci;
      CGAL_assertion(vh->degree() == 2);
      
      // we can remove this vertex only if the data on its halfedges is the 
      // same
      if (!combinatorically_can_remove_vertex(vh))
        continue;
                     
      // merge the edges, if geometrically possible (if data on vertex is not
      // set, then it must be geometrically possible)
      Halfedge_around_vertex_circulator hec1 = vh->incident_halfedges();
      Halfedge_around_vertex_circulator hec2 = hec1++;
      Halfedge_handle he1 = hec1, he2 = hec2;
      

      const X_monotone_curve_2& a = he1->curve(), b = he2->curve();
      CGAL_assertion(vh->is_decision_set() || curves_can_merge(a,b));
      if (vh->is_decision_set() && !curves_can_merge(a,b))
        continue;

      X_monotone_curve_2 c;
      curves_merge(a,b,c);

      // the decisions on he1 and he2 were the same, so the decision on 
      // the edge that will be left after the merge will be ok
      // but we need to take care of the bool flags of the target relation
      // of the edge that will be left
      // he1 and he2 both point to the removed vertex, so each should copy
      // the other's twin flags. the flags in the twins don't change
      //    he1            he2
      // x----------->x<------------x
      //  <----------- ------------>
      //   he1->twin()   he2->twin()
      he1->set_is_equal_aux_data_in_target(0, he2->twin()->get_is_equal_aux_data_in_target(0));
      he1->set_is_equal_aux_data_in_target(1, he2->twin()->get_is_equal_aux_data_in_target(1));
      he1->set_has_equal_aux_data_in_target(0, he2->twin()->get_has_equal_aux_data_in_target(0));
      he1->set_has_equal_aux_data_in_target(1, he2->twin()->get_has_equal_aux_data_in_target(1));
      he1->set_has_equal_aux_data_in_target_and_face
        (0, he2->twin()->get_has_equal_aux_data_in_target_and_face(0));
      he1->set_has_equal_aux_data_in_target_and_face
        (1, he2->twin()->get_has_equal_aux_data_in_target_and_face(1));

      he2->set_is_equal_aux_data_in_target(0, he1->twin()->get_is_equal_aux_data_in_target(0));
      he2->set_is_equal_aux_data_in_target(1, he1->twin()->get_is_equal_aux_data_in_target(1));
      he2->set_has_equal_aux_data_in_target(0, he1->twin()->get_has_equal_aux_data_in_target(0));
      he2->set_has_equal_aux_data_in_target(1, he1->twin()->get_has_equal_aux_data_in_target(1));
      he2->set_has_equal_aux_data_in_target_and_face
        (0, he1->twin()->get_has_equal_aux_data_in_target_and_face(0));
      he2->set_has_equal_aux_data_in_target_and_face