envelope_element_visitor_3.h

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

              
    }

    // set envelope data on the last part (cur_part)
    // if the last part is a special edge, and no verticals are involved
    // we can set both aux data on it. otherwise we should use the traits
    // compare method.

    Comparison_result cur_part_res;
    if (overlaps > 0)
      cur_part_res = EQUAL;
    else
      cur_part_res = resolve_minimal_edge(edge, cur_part);

    cur_part->set_decision(cur_part_res);
    cur_part->twin()->set_decision(cur_part_res);

    if (cur_part == edge)
      first_part_res = cur_part_res;
      
    // if the original source and target have same aux data as the edge
    // we can set envelope data over them also
    // if they are special vertices, we set both aux data. otherwise we copy
    // from the incident edge part.


    // the incident edge part to source should be edge (the first part)
    CGAL_assertion(original_src == edge->source());
    if (!original_src->is_decision_set() &&
        can_copy_decision_from_edge_to_vertex(edge->twin()))
    {
      if (source_is_special)
        set_data_by_comparison_result(original_src, EQUAL);
      #ifdef CGAL_ENVELOPE_SAVE_COMPARISONS
        else
          set_data_by_comparison_result(original_src, first_part_res);
      #endif

    }
    // the incident edge part to target should be cur_part (the last part)
    CGAL_assertion(original_trg == cur_part->target());
    if (!original_trg->is_decision_set() &&
        can_copy_decision_from_edge_to_vertex(cur_part))
    {
      if (target_is_special)
        set_data_by_comparison_result(original_trg, EQUAL);
      #ifdef CGAL_ENVELOPE_SAVE_COMPARISONS
        else
          set_data_by_comparison_result(original_trg, cur_part_res);
      #endif
    }

  }
  
  // get a vertex with 2 surfaces defined over it and decide the envelope data
  // on it between them
  void resolve(Vertex_handle vertex)
  {
    // it is enough to compare only one surface from each group (because they
    // all overlap over the vertex), but set all the group
    const Xy_monotone_surface_3& surf1 = get_aux_surface(vertex, 0);
    const Xy_monotone_surface_3& surf2 = get_aux_surface(vertex, 1);
    const Point_2& point_2 = vertex->point();
    Comparison_result cur_res = compare_distance_to_envelope(point_2,surf1,surf2);
    vertex->set_decision(cur_res);
  }

  /*! Access the traits object (const version). */
  const Traits* get_traits () const
  {
    return (traits);
  }

  /*! Access the traits object (non-const version). */
  Traits* get_traits ()
  {
    return (traits);
  }

protected:
  
  // compute Comparison_result of surfaces over the face, assuming they get 
  // the same answer for all points in face
  // if we get a halfedge, it is assumed to be on the outer boundary of the 
  // face, and its curve is assumed to be a projected intersection curve, 
  // and we compare the surfaces to the left/right of it
  // otherwise we compare the surfaces over an (arbitrary) edge of the face,
  // assuming this is the correct answer for the face since the surfaces are 
  // continous
  // In either case, we try to copy decision from an incident face, is possible
  // before asking the geometric question
  Comparison_result resolve_minimal_face(Face_handle face, 
                                         Halfedge_handle* he = NULL)
  {
    CGAL_precondition(he == NULL || (*he)->face() == face);
    //CGAL_assertion(!face->is_unbounded());
    Comparison_result res = EQUAL;

    bool success = false;
    #ifdef CGAL_ENVELOPE_SAVE_COMPARISONS
      success = can_copy_decision_from_boundary_edge(face, res);
    #endif
    
    if (success)
      return res;
      
    const Xy_monotone_surface_3& surf1 = get_aux_surface(face, 0);
    const Xy_monotone_surface_3& surf2 = get_aux_surface(face, 1);

    if (he == NULL)
    {
      // compare the surfaces over arbitrary edge
      Ccb_halfedge_circulator hec = face->outer_ccb();
      Ccb_halfedge_circulator curr = hec;
      bool found_edge = false;
      do
      {
        Halfedge_handle he = hec;
        if(he->is_fictitious())
          ++hec;
        else
        {
          found_edge = true;
          const X_monotone_curve_2& cv = hec->curve();
          res = compare_distance_to_envelope(cv,surf1,surf2);

          break;
        }
      }
      while(curr != hec);

      if(!found_edge)
      {
        // all edges are fictitous, we have two infinite surfaces.
        // but still, there can be holes.
        if(face->holes_begin() != face->holes_end())
        {
          Hole_iterator hit = face->holes_begin();
          Ccb_halfedge_circulator hec = *hit;
          CGAL_assertion(!hec->is_fictitious());
          const X_monotone_curve_2& cv = hec->curve();
          res = compare_distance_to_envelope(cv,surf1,surf2);
        }
        else
        {
          //two infinite surfaces, no outer boundary or holes. 
          res = compare_distance_to_envelope(surf1,surf2, Has_boundary_category());
        }
      }
      
      //assertion code begin
      // check that result is equal on all edges
      CGAL_assertion_code(	
        Ccb_halfedge_circulator hec_begin = hec;    
        ++hec;
        while (hec != hec_begin)
        {
          if(hec->is_fictitious())
          {
            ++hec;
            continue;
          }
          Comparison_result tmp = 
                        compare_distance_to_envelope(hec->curve(),surf1,surf2);
      );
      CGAL_assertion_msg(tmp == res, 
                         "compare over curve returns non-consistent results");
      CGAL_assertion_code(
          ++hec;

        }
      );
      //assertion code end
      return res;
    }
    else
    {
      // compare the surfaces over the halfedge's curve
      const X_monotone_curve_2& cv = (*he)->curve();

      // a face is always to the left of its halfedge
      if ((*he)->direction() == SMALLER)
      {
        res = traits->compare_z_at_xy_above_3_object()(cv,surf1,surf2);
        if(type == UPPER)
          res = CGAL::opposite(res);
      }
      else
      {
        res = traits->compare_z_at_xy_below_3_object()(cv,surf1,surf2);
        if(type == UPPER)
          res = CGAL::opposite(res);

      }
    }
    return res;
  }

  // use the Intersection type (Transversal/Tangent) and return the appropriate
  // comparison result of the other side of the intersection curve, 
  // if the first side has result "res"
  Comparison_result resolve_by_intersection_type(Comparison_result res,
                                                 Multiplicity itype)
  {
    itype %= 2;
    if (itype == 1)
    {
      if (res == LARGER)
        return SMALLER;
      else if (res == SMALLER)
        return LARGER;
      else
        return res;
    }
    else
    {
      CGAL_assertion(itype == 0);
      return res;
    }

  }
  
  // find intersections between 2 xy-monotone surfaces
  // use caching for repeating questions of same pair of surfaces
  template <class OutputIterator>
  OutputIterator get_projected_intersections(const Xy_monotone_surface_3& s1,
                                             const Xy_monotone_surface_3& s2,
                                             OutputIterator o)
  {
    return traits->construct_projected_intersections_2_object()(s1, s2, o);
  }

  // Geometry can be a Point_2 or a X_monotone_curve_2
  template <class Geometry>
  Comparison_result compare_distance_to_envelope(Geometry& g,
                                                 const Xy_monotone_surface_3& s1,
                                                 const Xy_monotone_surface_3& s2)
  {
    Comparison_result res = traits->compare_z_at_xy_3_object()(g, s1, s2);
    return ((type == LOWER) ? res : CGAL::opposite(res));
  }


  // compare two infinite surfaces with no boundary or holes
  Comparison_result compare_distance_to_envelope(const Xy_monotone_surface_3& s1,
                                                 const Xy_monotone_surface_3& s2,
                                                 Tag_true)
  {
    Comparison_result res = traits->compare_z_at_xy_3_object()(s1, s2);
    return ((type == LOWER) ? res : CGAL::opposite(res));
  }

   // compare two infinite surfaces with no boundary or holes
  Comparison_result compare_distance_to_envelope(const Xy_monotone_surface_3&,
                                                 const Xy_monotone_surface_3&,
                                                 Tag_false)
  {
    CGAL_assertion(false); // doesnt' suppose to reach here at all!!!
    return SMALLER;
  }

  // helper method to get the surfaces we need to work on
  template <class FeatureHandle>
  const Xy_monotone_surface_3& get_aux_surface(FeatureHandle fh, unsigned int id)
  {
	  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
    Face_handle f;
  	if (assign(f, o))
  	  return f->get_data();
    
    Halfedge_handle h;
    if (assign(h, o))
  	  return h->get_data();
  	
    Vertex_handle v;
    CGAL_assertion_code(bool b =)
    assign(v, o);
    CGAL_assertion(b);
  	return v->get_data();
  }
                                  
  bool can_copy_decision_from_face_to_edge(Halfedge_handle h)
  {
    // can copy decision from face to its incident edge if the aux
    // envelopes are continous over the face and edge
    return (h->get_has_equal_aux_data_in_face(0) &&
            h->get_has_equal_aux_data_in_face(1));
  }

  bool can_copy_decision_from_edge_to_vertex(Halfedge_handle h)
  {
    // can copy decision from face to its incident edge if the aux
    // envelopes are continous over the face and edge
    return (h->get_has_equal_aux_data_in_target(0) &&
            h->get_has_equal_aux_data_in_target(1));
  }


  // check the aux data on the edges & vertices of the boundary of the face,
  // and if it equals the aux data on the face, copy it, to save calculations for
  // these features later
  // also consider isolated vertices
  // "res" is the decision made on the face
  void copy_data_to_face_boundary(Face_handle face)
  {
    Ccb_halfedge_circulator ccb = face->outer_ccb();
    copy_data_to_face_boundary(face, ccb);

    Hole_iterator inner_iter = face->holes_begin();
    for (; inner_iter != face->holes_end(); ++inner_iter)
    {
      ccb = (*inner_iter);
      copy_data_to_face_boundary(face, ccb);
    }

    Isolated_vertex_iterator iso_iter = face->isolated_vertices_begin();
    for (; iso_iter != face->isolated_vertices_end(); ++iso_iter)
    {
      Vertex_handle vh = iso_iter;
      if (!vh->is_decision_set() && has_equal_aux_data_with_face(vh))
        // can copy the data from the face, since we already took care of
        // the vertices of projected intersections
        vh->set_decision(face->get_decision());
    }
  }

  void copy_data_to_face_boundary(Face_handle face,
                                  Ccb_halfedge_circulator hec)
  {