envelope_element_visitor_3.h

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

    Ccb_halfedge_circulator hec_begin = hec;
    do {
      Halfedge_handle hh = hec;
      if(hh->is_fictitious())
      {
        ++hec;
        continue;
      }
      CGAL_assertion(face == hh->face());
      // if it is a vertical decomposition edge, copy data from face
      /*if (!hh->is_decision_set() && hh->get_is_fake())
      {
        hh->set_decision(face->get_decision());
        hh->twin()->set_decision(face->get_decision());
      }*/
      if (!hh->is_decision_set() && can_copy_decision_from_face_to_edge(hh))
      {
        // copy the decision from face to the edge
        hh->set_decision(face->get_decision());
        hh->twin()->set_decision(hh->get_decision());
      }
      // TODO: is this correct? shouldn't we split the edge first?
      // I think it is correct, because there is no intersection (of
      // the edges aux sources) over the edge, as if there was such
      // intersection, there would also be intersection between the surfaces
      // over the face, and we know now that there isn't.
      
      // if the first map is continous, but the second isn't (i.e. when we move
      // from the face to the edge, the envelope goes closer), then if the
      // second map wins on the face, it wins on the edge also
      else if (!hh->is_decision_set() &&
               face->get_decision() == SECOND &&
               hh->get_has_equal_aux_data_in_face(0) &&
               !hh->get_has_equal_aux_data_in_face(1))
      {
        hh->set_decision(SECOND);
        hh->twin()->set_decision(SECOND);

      }
      // if the second map is continous, but the first isn't, then if the
      // first map wins on the face, it wins on the edge also
      else if (!hh->is_decision_set() &&
               face->get_decision() == FIRST &&
               !hh->get_has_equal_aux_data_in_face(0) &&
               hh->get_has_equal_aux_data_in_face(1))
      {
        hh->set_decision(FIRST);
        hh->twin()->set_decision(FIRST);
      }

      // conclude to the vertices
      // we check both endpoints, since it can be possible that we cannot
      // conclude from one edge, bt can conclude from the other
      conclude_decision_to_vertex(hh->source(), hh->twin(), face, false);
      conclude_decision_to_vertex(hh->target(), hh, face, true);
                      
      hec++;
    } while(hec != hec_begin); 
  }

  // try to conclude the decision from the halfedge or the face to the vertex
  // the method assumes that the vertex is an endpoint of the edge represented
  // by "hh", which lies on the boundary of "fh"
  // the last bool indicates whether to check if possible to conclude from
  // face to vertex. it is only possible when hh->face == fh
  void conclude_decision_to_vertex(Vertex_handle vh, Halfedge_handle hh,
                                   Face_handle fh, bool try_vertex_face)
  {
    if (vh->is_decision_set())
      return;


    // first, we try to copy decision from edge, then from face
    if (hh->is_decision_set() &&
        can_copy_decision_from_edge_to_vertex(hh))
    {
      vh->set_decision(hh->get_decision());
    }
    // if the first map is continous, but the second isn't (i.e. when we move
    // 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 (hh->get_decision() == SECOND &&
             hh->get_has_equal_aux_data_in_target(0) &&
             !hh->get_has_equal_aux_data_in_target(1))
    {
      vh->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 (hh->get_decision() == FIRST &&
             !hh->get_has_equal_aux_data_in_target(0) &&
             hh->get_has_equal_aux_data_in_target(1))
    {
      vh->set_decision(FIRST);
    }
    // check if we can copy from the face
    // todo: what if has_equal has 3 possible values? (and projected intersection
    // vertices have unknown flags)
    else if (try_vertex_face)
	{
      /*CGAL_assertion(has_equal_aux_data_in_target_and_face(hh) == 
	                 has_equal_aux_data(vh, fh));*/
      if (has_equal_aux_data_in_target_and_face(hh))
	  {

        // can copy the data from the face, since we already took care of
        // the vertices of projected intersections
        vh->set_decision(fh->get_decision());
	  }
	}
  }
  
  // todo: this is for checking
  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);
  }
  // todo: this is for checking
  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());

    if (assign(v, o))
    {
      begin = v->begin_data();
      end = v->end_data();
    }
    else if (assign(h, o))
    {
      begin = h->begin_data();
      end = h->end_data();
    }
    else
   	{
   	  CGAL_assertion(assign(f, o));
      assign(f, o);
      begin = f->begin_data();
      end = f->end_data();
   	}
  }

  // todo: this is for checking
  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;
  }

  // todo: this is for checking
  template <class FeatureHandle1, class FeatureHandle2>
  bool has_equal_aux_data(FeatureHandle1 fh1, FeatureHandle2 fh2)
  {
	  return (has_equal_aux_data(0, fh1, fh2) &&
		        has_equal_aux_data(1, fh1, fh2));
  }


  // check if we can copy the decision made on a boundary edge to the face
  // if so, res will contain this decision's comparison result
  bool can_copy_decision_from_boundary_edge(Face_handle face, Comparison_result& res)
  {
    bool result = false;
    // check outer boundary
    Ccb_halfedge_circulator hec = face->outer_ccb();
    Ccb_halfedge_circulator hec_begin = hec;
    do {
      Halfedge_handle hh = hec;
      if(hh->is_fictitious())
      {
        ++hec;
        continue;
      }
      if (can_copy_decision_from_face_to_edge(hh) &&

          hh->is_decision_set() &&
          hh->get_decision() != BOTH)
      {
        res = convert_decision_to_comparison_result(hh->get_decision());
        result = true;
      }
      // if the first map is continous, but the second isn't (i.e. when we move
      // from the edge to the face, the envelope goes farther), then if the
      // first map wins on the edge, it wins on the face also
      else if (hh->is_decision_set() &&
               hh->get_decision() == FIRST &&
               hh->get_has_equal_aux_data_in_face(0) &&
               !hh->get_has_equal_aux_data_in_face(1))
      {
        res = convert_decision_to_comparison_result(FIRST);
        result = true;
      } 
      // if the second map is continous, but the first isn't, then if the
      // second map wins on the edge, it wins on the face also
      else if (hh->is_decision_set() &&
               hh->get_decision() == SECOND &&
               !hh->get_has_equal_aux_data_in_face(0) &&
               hh->get_has_equal_aux_data_in_face(1))
      {
        res = convert_decision_to_comparison_result(SECOND);
        result = true;
      }           
      hec++;
    } while(hec != hec_begin && !result);
    if (result) return true;
    // check inner boundaries
    Hole_iterator hole_iter = face->holes_begin();
    for (; hole_iter != face->holes_end(); ++hole_iter)
    {
      hec = (*hole_iter);
      hec_begin = hec;

      do {
        Halfedge_handle hh = hec;
        if (can_copy_decision_from_face_to_edge(hh) &&
            hh->is_decision_set() &&
            hh->get_decision() != BOTH)
        {
          res = convert_decision_to_comparison_result(hh->get_decision());
          result = true;
        }
        // if the first map is continous, but the second isn't (i.e. when we move
        // from the edge to the face, the envelope goes farther), then if the
        // first map wins on the edge, it wins on the face also
        else if (hh->is_decision_set() &&
                 hh->get_decision() == FIRST &&
                 hh->get_has_equal_aux_data_in_face(0) &&
                 !hh->get_has_equal_aux_data_in_face(1))
        {
          res = convert_decision_to_comparison_result(FIRST);

          result = true;
        }
        // if the second map is continous, but the first isn't, then if the
        // second map wins on the edge, it wins on the face also
        else if (hh->is_decision_set() &&
                 hh->get_decision() == SECOND &&
                 !hh->get_has_equal_aux_data_in_face(0) &&
                 hh->get_has_equal_aux_data_in_face(1))
        {
          res = convert_decision_to_comparison_result(SECOND);
          result = true;
        }
  
        hec++;
      } while(hec != hec_begin && !result);
      if (result) return true;
    }

    return result;
  }

  Comparison_result convert_decision_to_comparison_result(CGAL::Dac_decision d)
  {
    return enum_cast<Comparison_result>(d);
    /*if (d == FIRST)
      return SMALLER;
    else if (d == SECOND)
      return LARGER;
    else
      return EQUAL;*/
  }
  
  bool has_equal_aux_data_with_face(Vertex_handle v)
  {
    CGAL_assertion(v->is_isolated());
    return (v->get_has_equal_aux_data_in_face(0) &&
            v->get_has_equal_aux_data_in_face(1));
  }

  bool has_equal_aux_data_in_target_and_face(Halfedge_handle h)
  {
    return (h->get_has_equal_aux_data_in_target_and_face(0) &&
            h->get_has_equal_aux_data_in_target_and_face(1));
  }

  // check the aux data on the endpoint vertices of the edge
  // and if it equals the aux data on the edge, copy it, to save calculations for
  // these features later
  void copy_data_to_edge_endpoints(Halfedge_handle edge)
  {
    // take care for source
    if (!edge->source()->is_decision_set() &&
        can_copy_decision_from_edge_to_vertex(edge->twin()))
      // can copy the data from the edge, since we already took care of
      // the vertices of projected intersections
      edge->source()->set_decision(edge->get_decision());
    // if the first map is continous, but the second isn't (i.e. when we move
    // 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->twin()->get_has_equal_aux_data_in_target(0) &&
             !edge->twin()->get_has_equal_aux_data_in_target(1))
    {
      edge->source()->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->twin()->get_has_equal_aux_data_in_target(0) &&
             edge->twin()->get_has_equal_aux_data_in_target(1))
    {
      edge->source()->set_decision(FIRST);
    }

    // take care for target
    if (!edge->target()->is_decision_set() &&
        can_copy_decision_from_edge_to_vertex(edge))
      // can copy the data from the edge, since we already took care of
      // the vertices of projected intersections
      edge->target()->set_decision(edge->get_decision());
    // if the first map is continous, but the second isn't (i.e. when we move