envelope_element_visitor_3.h

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

            );
            CGAL_expensive_assertion(tmp_res == res);
          }
          else
            res = resolve_minimal_face(f2, &new_he_twin);
        #else
          res = resolve_minimal_face(f2, &new_he_twin);
        #endif
        copy_data_by_comparison_result(face, f2, res);
      }
      if (!f1->is_decision_set())
      {
        #ifdef CGAL_ENVELOPE_SAVE_COMPARISONS
          if (itype != 0)
          {
            res = convert_decision_to_comparison_result(f2->get_decision());
            res = resolve_by_intersection_type(res, itype);
            CGAL_expensive_assertion_code(
              Comparison_result tmp_res = resolve_minimal_face(f1, &new_he);
            );
            CGAL_expensive_assertion(tmp_res == res);
          }
          else
            res = resolve_minimal_face(f1, &new_he);
        #else
          res = resolve_minimal_face(f1, &new_he);
        #endif
        copy_data_by_comparison_result(face, f1, res);
      }

    }
    
    // we also need to check the faces incident to the halfedges in special_edges
    // since the envelope data over them should be computed using compare_left/right versions
    Halfedges_list_iterator special_edge_it;
    for(special_edge_it = result_special_edges.begin();
        special_edge_it != result_special_edges.end(); ++special_edge_it)
    {
      // we assume that the halfedge given points to the correct face (which is inside the original face)
      Halfedge_handle special_he = *special_edge_it;
      Face_handle f = special_he->face();
      if (!f->is_decision_set())
      {
        Comparison_result res = resolve_minimal_face(f, &special_he);
        copy_data_by_comparison_result(face, f, res);      
      }

      // take care for the edge, if necessary
      if (!special_he->is_decision_set() &&
          can_copy_decision_from_face_to_edge(special_he))
      {
    //    if (!special_he->get_aux_is_set(0) || !special_he->get_aux_is_set(1))
    //    {
    //      // this can only happen when the edge is fake, since the edge is on 
		  //// the face's boundary
    //      CGAL_assertion(special_he->get_is_fake());
    //      special_he->set_aux_source(0, face->get_aux_source(0));
    //      special_he->set_aux_source(1, face->get_aux_source(1));
    //      special_he->twin()->set_aux_source(0, face->get_aux_source(0));
    //      special_he->twin()->set_aux_source(1, face->get_aux_source(1));
	   //   }
      	//if (special_he->get_is_fake())
      	//{
      	//  // this edge is not fake anymore, as it coincides with a projected
      	//  // intersection
      	//  special_he->set_is_fake(false);
      	//  special_he->twin()->set_is_fake(false);
       // }
        special_he->set_decision(EQUAL);
        special_he->twin()->set_decision(EQUAL);
      }
    }

    // update data on special vertices
    Vertices_list_iterator special_vertex_it;
    for(special_vertex_it = result_special_vertices.begin();
        special_vertex_it != result_special_vertices.end(); ++special_vertex_it)
    {
      Vertex_handle special_v = *special_vertex_it;
      if (!special_v->is_decision_set())
      {
      
        if (special_v->get_aux_is_set(0) && special_v->get_aux_is_set(1))
          set_data_by_comparison_result(special_v, EQUAL);
        else
		  // this is a new vertex inside the face, so we need to update its
		  // aux source information from face also (done in method)
          copy_all_data_to_vertex(face, special_v);
      } else
        CGAL_assertion(special_v->get_aux_is_set(0) && special_v->get_aux_is_set(1));
     }
    
    // assert all new faces got data set, if not, then maybe no curve cuts the face,
    // and should use regular resolve_minimal_face
    typename std::list<Face_handle>::iterator new_face_it;
    for(new_face_it = result_face_parts.begin();
        new_face_it != result_face_parts.end(); ++new_face_it)
    {
      Face_handle new_face = *new_face_it;
      if (!new_face->is_decision_set())
      {
        Comparison_result res = resolve_minimal_face(new_face);
        copy_data_by_comparison_result(face, new_face, res);
      }

      // check face boundary for "data from face" features
      #ifdef CGAL_ENVELOPE_SAVE_COMPARISONS
        copy_data_to_face_boundary(new_face);
      #endif
    }

  }    

  // get an edge with 2 surfaces defined over it, and split it to get the shape
  // of the envelope of these surfaces over the edge


  void resolve(Halfedge_handle edge, Minimization_diagram_2& result)
  {
    const Xy_monotone_surface_3& surf1 = get_aux_surface(edge, 0);
    const Xy_monotone_surface_3& surf2 = get_aux_surface(edge, 1);

    // find the projected intersections
    std::list<Object> inter_objs;
    get_projected_intersections(surf1, surf2, std::back_inserter(inter_objs));

    if (inter_objs.size() == 0)
    {
      resolve_minimal_edge(edge, edge);
      #ifdef CGAL_ENVELOPE_SAVE_COMPARISONS
        copy_data_to_edge_endpoints(edge);
      #endif
      return;
    }

    const X_monotone_curve_2& original_cv = edge->curve();
   
    // we want to work on the halfedge going from left to right
    if(edge->direction() != SMALLER)
      edge = edge->twin();
      
    Vertex_handle original_src = edge->source();
    Vertex_handle original_trg = edge->target();
    
    // we should have a list of points where we should split the edge's curve
    // we then will sort the list, and split the curve

    // we should pay a special attension for overlaps, since we can get special
    // edges

    // we associate with every point 2 flags:
    // 1. is the point a left endpoint of an overlapping segment
    // 2. is the point a right endpoint of an overlapping segment
    typedef std::vector<Point_2_with_info>      Points_vec;
    Points_vec                                  split_points;
    bool is_min_end_at_inf = false;
    bool is_max_end_at_inf = false;

    Point_2 point;
    Intersection_curve icurve;
    Object cur_obj;

    std::list<Object>::iterator inter_objs_it = inter_objs.begin();
    for(; inter_objs_it != inter_objs.end(); ++inter_objs_it)
    {
      cur_obj = *inter_objs_it; 
      CGAL_assertion(!cur_obj.is_empty());
      if (assign(point, cur_obj))
      {
        // if the point is on the curve, should add it the the split points
        // list, otherwise, it is irrelevant and should be ignored
        if (is_point_on_curve(point, original_cv))
          split_points.push_back(Point_2_with_info(point, false, false));
      }
      else if (assign(icurve, cur_obj))
      {
        const X_monotone_curve_2& x_curve = icurve.first;

        // find the intersection points and overlapping segments with the
        // original curve and insert them to the list of split points
        // intersect the x-monotone curve with the edge's curve
        typedef std::pair<Point_2, unsigned int> Intersect_point_2;
        std::list<Object> intersections_list;
        const Intersect_point_2  *ip;
        const X_monotone_curve_2 *icv;
        
        traits->intersect_2_object()(x_curve, original_cv,
                                      std::back_inserter(intersections_list));

        std::list<Object>::iterator inter_it = intersections_list.begin();
        for(; inter_it != intersections_list.end(); ++inter_it)
        {
          ip = object_cast<Intersect_point_2> (&(*inter_it));
          if (ip != NULL)
          {
            split_points.push_back(Point_2_with_info(ip->first, false, false));
          }
          else
          {
            icv = object_cast<X_monotone_curve_2> (&(*inter_it));
            CGAL_assertion (icv != NULL);

            // we will add the *icv end points to the split_points, unless
            // but we should be carefull with infinite curves.
            Arr_traits_adaptor_2<Traits> tr_adaptor(*traits);
            if(tr_adaptor.boundary_in_y_2_object()(*icv, MIN_END) == NO_BOUNDARY &&
                tr_adaptor.boundary_in_x_2_object()(*icv, MIN_END) == NO_BOUNDARY)
                split_points.push_back(Point_2_with_info(
                                        traits->construct_min_vertex_2_object()(*icv),
                                        true, false));
            else
              is_min_end_at_inf = true;

            if(tr_adaptor.boundary_in_y_2_object()(*icv, MAX_END) == NO_BOUNDARY &&
                tr_adaptor.boundary_in_x_2_object()(*icv, MAX_END) == NO_BOUNDARY)
                split_points.push_back(Point_2_with_info(
                                        traits->construct_max_vertex_2_object()(*icv),
                                        false, true));
            else
              is_max_end_at_inf = true;
          }
        }       
      }
     
      else
        CGAL_assertion_msg(false, "wrong projected intersection type");
    }
    
    // if there aren't any split points, we can finish
    if (split_points.empty())
    {
      resolve_minimal_edge(edge, edge);
      #ifdef CGAL_ENVELOPE_SAVE_COMPARISONS
        copy_data_to_edge_endpoints(edge);
      #endif
      return;
    }
    
    // sort the split points from left to right
    // and split the original edge in these points
    Points_compare comp(*traits);
    std::sort(split_points.begin(), split_points.end(), comp);
 
    // if overlaps > 0 it will indicate that we are inside an overlapping
    // segment meaning, we have a special edge
    int overlaps = 0;    

    // check if source is a special vertex (i.e. also a projected intersection)
    // by checking the first point in the list
    bool source_is_special = false;
    CGAL_assertion(split_points.size() >= 1);
    if ((!original_src->is_at_infinity() && 
         traits->equal_2_object()(split_points[0].first,
                                  original_src->point())) ||
        (original_src->is_at_infinity() && is_min_end_at_inf))
    {
      overlaps++;
      source_is_special = true;
    }
    
    // check if target is a special vertex, by checking the last point in the list
    bool target_is_special = false;
    if ((!original_trg->is_at_infinity() && 
         traits->equal_2_object()(split_points[split_points.size()-1].first, 
                                  original_trg->point())) ||
        (original_trg->is_at_infinity() && is_max_end_at_inf))
      target_is_special = true;

    

    // remember the envelope decision over the first & last parts, to
    // be able to copy it to the original endpoints
    // TODO: the initial value is only needed to shut up the compiler
    // TODO: is this realy needed, or we can use the decision made on "edge"
    // (is "edge" always the first part? )
    Comparison_result first_part_res = EQUAL;
    
    // cur_part is the part of the original edge that might be split
    Halfedge_handle cur_part = edge;

    for(unsigned int i=0; i<split_points.size(); ++i)
    {
      Point_2_with_info cur_p = split_points[i];
      // if we get to the target vertex, we end the loop, since no more splits

      // are needed
      if (!original_trg->is_at_infinity() && cur_p.first == original_trg->point())
        break;
        
      Vertex_handle cur_src_vertex = cur_part->source();

      // check that the current split point is not already a vertex
      if ((!cur_src_vertex->is_at_infinity() && cur_p.first != cur_src_vertex->point())||
           cur_src_vertex->is_at_infinity())

      {
        // split the edge in this point
        X_monotone_curve_2 a,b;

        traits->split_2_object()(cur_part->curve(), cur_p.first, a, b);
        // todo: can we use the internal split?
        Halfedge_handle split_he = result.split_edge(cur_part, a, b);
        // split always returns the halfedge with source = cur_part.source
        CGAL_assertion(split_he->source() == cur_src_vertex);

        // the new vertex is split_he->target(), we set envelope data on it
        copy_all_data_to_vertex(edge, split_he->target());

        // identify the part of the split edge that we are finished with
        // (this is the one with cur_src_vertex),
        // and the part that might be split again
        Halfedge_handle finished_part = split_he;
        cur_part = split_he->next();

        // set the envelope data over the finished part
        // if the finished 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 finished_part_res;
        if (overlaps > 0)
          finished_part_res = EQUAL;
        else
          finished_part_res = resolve_minimal_edge(edge, finished_part);

        finished_part->set_decision(finished_part_res);
        finished_part->twin()->set_decision(finished_part_res);

        if (finished_part == edge)
          first_part_res = finished_part_res;
      }

      // check the overlaps indications
      if (cur_p.second == true)
        ++overlaps; // we start a new overlapping segment at this point
      if (cur_p.third == true)
        --overlaps; // we end an overlapping segment at this point