env_divide_and_conquer_2_impl.h

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

    
    // In this case the two urves intersect (or overlap) at v.
    Vertex_handle        new_v;
    
    if (u_res == SMALLER)
      new_v = _append_vertex (out_d, v->point(), e1);
    else
      new_v = _append_vertex (out_d, v->point(), e2);
    
    if (u_res == EQUAL)
      new_v->left()->add_curves (e1->curves_begin(), e1->curves_end());
    
    // Note that the new vertex is incident to all curves in e1 and in e2.
    new_v->add_curves (e1->curves_begin(), e1->curves_end());
    new_v->add_curves (e2->curves_begin(), e2->curves_end());
    
    return;
  }
  
  if (! v_exists)
  {
    // Both edges are unbounded from the right, so we simply have
    // to update the rightmost edge in out_d.
    CGAL_assertion (u_res != EQUAL);
    
    if (u_res == SMALLER)
      out_d.rightmost()->add_curves (e1->curves_begin(), e1->curves_end());
    else
      out_d.rightmost()->add_curves (e2->curves_begin(), e2->curves_end());
    
    return;
  }
  
  // Check if we need to insert v into the diagram.
  if (pu_exists)
  {
    // Update the relative position of the two curves, which is their
    // order immediately to the right of their last observed intersection
    // point pu.
    u_res = traits->compare_y_at_x_right_2_object() (e1->curve(),
                                                     e2->curve(),
                                                     pu);
    
    if (env_type == UPPER)
      u_res = CGAL::opposite (u_res);
  }
  CGAL_assertion (u_res != EQUAL);

  if (u_res == SMALLER)
  {    
    // The final part of the interval is taken from e1.
    Vertex_handle        new_v;

    if (org_v == 1)
    {
      // In case v is also from e1, append it to the merged diagram.
      new_v = _append_vertex (out_d, v->point(), e1);
      new_v->add_curves (v->curves_begin(), v->curves_end());
    }
    else
    {
      // If v is from e2, check if it below (or above, in case of an upper
      // envelope) cv1 to insert it.
      const Comparison_result  res = 
        traits->compare_y_at_x_2_object() (v->point(),
                                           e1->curve());
      
      if (res == EQUAL ||
          (env_type == LOWER && res == SMALLER) ||
          (env_type == UPPER && res == LARGER))
      {
        new_v = _append_vertex (out_d, v->point(), e1);
        new_v->add_curves (v->curves_begin(), v->curves_end());
        
        if (res == EQUAL)
          new_v->add_curves (e1->curves_begin(), e1->curves_end());
      }
    }
  }
  else
  {
    // The final part of the interval is taken from e2.
    Vertex_handle        new_v;

    if (org_v == 2)
    {
      // In case v is also from e2, append it to the merged diagram.
      new_v = _append_vertex (out_d, v->point(), e2);
      new_v->add_curves (v->curves_begin(), v->curves_end());
    }
    else
    {
      // If v is from e1, check if it below (or above, in case of an upper
      // envelope) cv2 to insert it.
      const Comparison_result  res = 
        traits->compare_y_at_x_2_object() (v->point(),
                                           e2->curve());
      
      if (res == EQUAL ||
          (env_type == LOWER && res == SMALLER) ||
          (env_type == UPPER && res == LARGER))
      {
        new_v = _append_vertex (out_d, v->point(), e2);
        new_v->add_curves (v->curves_begin(), v->curves_end());
        
        if (res == EQUAL)
          new_v->add_curves (e2->curves_begin(), e2->curves_end());
      }
    }
  }

  return;
}

// ---------------------------------------------------------------------------
// Append a vertex to the given diagram.
//
template <class Traits, class Diagram>
typename Envelope_divide_and_conquer_2<Traits,Diagram>::Vertex_handle
Envelope_divide_and_conquer_2<Traits,Diagram>::_append_vertex
        (Envelope_diagram_1& diag,
         const Point_2& p, Edge_const_handle e)
{
  // Create the new vertex and the new edge.
  Vertex_handle   new_v = diag.new_vertex (p);
  Edge_handle     new_e = diag.new_edge();
  
  if (! e->is_empty())
    new_e->add_curves (e->curves_begin(), e->curves_end());
  
  // Connect the new vertex.
  new_v->set_left (new_e);
  new_v->set_right (diag.rightmost());
  
  if (diag.leftmost() != diag.rightmost())
  {
    // The diagram is not empty. Connect the new edge to the left of the
    // rightmost edge of the diagram.
    new_e->set_right (new_v);
    new_e->set_left (diag.rightmost()->left());
    diag.rightmost()->left()->set_right (new_e);
    diag.rightmost()->set_left (new_v);
  }
  else
  {
    // The diagram is empty: Make the new edge the leftmost.
    new_e->set_right (new_v);
    diag.set_leftmost (new_e);
    diag.rightmost()->set_left (new_v);      
  }
  
  return (new_v);
}    

// ---------------------------------------------------------------------------
// Merge the vertical segments into the envelope given as a minimization
// (or maximization) diagram.
//
template <class Traits, class Diagram>
void Envelope_divide_and_conquer_2<Traits,Diagram>::
_merge_vertical_segments (Curve_pointer_vector& vert_vec,
                          Envelope_diagram_1& out_d)
{
  // Sort the vertical segments by their increasing x-coordinate.
  Less_vertical_segment  les_vert (traits);

  std::sort (vert_vec.begin(), vert_vec.end(), les_vert);

  // Proceed on the diagram and on the sorted sequence of vertical segments
  // and merge them into the diagram.
  typename Traits_adaptor_2::Compare_x_2             comp_x =
                                      traits->compare_x_2_object();
  typename Traits_adaptor_2::Compare_xy_2            comp_xy =
                                      traits->compare_xy_2_object();
  typename Traits_adaptor_2::Compare_y_at_x_2        comp_y_at_x =
                                      traits->compare_y_at_x_2_object();
  typename Traits_adaptor_2::Construct_min_vertex_2  min_vertex =
                                      traits->construct_min_vertex_2_object();
  typename Traits_adaptor_2::Construct_max_vertex_2  max_vertex =
                                      traits->construct_max_vertex_2_object();

  Edge_handle             e = out_d.leftmost();
  Vertex_handle           v;
  Curve_pointer_iterator  iter = vert_vec.begin();
  Curve_pointer_iterator  next;
  Comparison_result       res;
  bool                    in_e_range;
  bool                    on_v;
  Point_2                 p;

  Vertex_initializer<Vertex_handle> v_init;
  v_init(v);
  
  while (iter != vert_vec.end())
  {
    // Check if the current vertical segment is on the x-range of the current
    // edge.
    if (e != out_d.rightmost())
    {
      // The current edge is not the rightmost one: we compare the x-coordinate
      // of the vertical segment to its right vertex.
      v = e->right();

      res = comp_x (min_vertex (**iter), v->point());
      in_e_range = (res != LARGER);
      on_v = (res == EQUAL);
    }
    else
    {
      // This is the rightmost edge, so the vertical segment must lie on its
      // x-range.
      in_e_range = true;
      on_v = false;
    }
    
    // If the current vertical segment is not in the x-range of the current
    // edge, we proceed to the next edge.
    if (! in_e_range)
    {
      e = v->right();
      continue;
    }

    // Go over all vertical segments that share the same x-coordinate and
    // find the one(s) with the smallest endpoint (or largest endpoint, if
    // we construct an upper envelope). 
    std::list<X_monotone_curve_2>    env_cvs;

    env_cvs.push_back (**iter);
    next = iter;
    ++next;
    while (next != vert_vec.end() &&
           comp_x (min_vertex (**iter), min_vertex (**next)) == EQUAL)
    {
      if (env_type == LOWER)
      {
        // Compare the lower endpoints of both curves.
        res = comp_xy (min_vertex (env_cvs.front()), min_vertex (**next));

        // Update the list of vertical segments with minimal endpoints as
        // necessary.
        if (res == EQUAL)
        {
          env_cvs.push_back (**next);
        }
        if (res == LARGER)
        {
          env_cvs.clear();
          env_cvs.push_back (**next);
        }
      }
      else
      {
        // Compare the upper endpoints of both curves.
        res = comp_xy (max_vertex (env_cvs.front()), max_vertex (**next));

        // Update the list of vertical segments with maximal endpoints as
        // necessary.
        if (res == EQUAL)
        {
          env_cvs.push_back (**next);
        }
        if (res == SMALLER)
        {
          env_cvs.clear();
          env_cvs.push_back (**next);
        }
      }

      ++next;
    }

    // Compare the endpoint to the diagram feature.
    if (env_type == LOWER)
      p = min_vertex (env_cvs.front());
    else
      p = max_vertex (env_cvs.front());

    if (on_v)
    {
      // Compare p to the current vertex.
      res = comp_xy (p, v->point());

      if (res == EQUAL)
      {
        // Add curves to the current vertex.
        v->add_curves (env_cvs.begin(), env_cvs.end());
      }
      else if ((env_type == LOWER && res == SMALLER) ||
               (env_type == UPPER && res == LARGER))
      {
        // Replace the list of curves associated with the vertex.
        v->clear_curves();
        v->add_curves (env_cvs.begin(), env_cvs.end());
      }
    }
    else
    {
      // p lies in the interior of the current edge.
      Vertex_handle   new_v;

      if (e->is_empty())
      {
        // Split the empty edge and associate the new vertex with the
        // vertical segments.
        new_v = _split_edge (out_d, p, e);
        new_v->add_curves (env_cvs.begin(), env_cvs.end());
      }
      else
      {
        // Compare p with the current curve.
        res = comp_y_at_x (p, e->curve());
        
        if ((env_type == LOWER && res != LARGER) ||
            (env_type == UPPER && res != SMALLER))
        {
          new_v = _split_edge (out_d, p, e);
          new_v->add_curves (env_cvs.begin(), env_cvs.end());

          if (res == EQUAL)
            new_v->add_curve (e->curve());
        }
      }
    }

    // Proceed to the next vertical segment with larger x-coordinate.
    iter = next;
  }

  return;
}

// ---------------------------------------------------------------------------
// Split a given diagram edge by inserting a vertex in its interior.
//
template <class Traits, class Diagram>
typename Envelope_divide_and_conquer_2<Traits,Diagram>::Vertex_handle
Envelope_divide_and_conquer_2<Traits,Diagram>::_split_edge
    (Envelope_diagram_1& diag,
     const Point_2& p, Edge_handle e)
{
  // Create the new vertex and the new edge.
  Vertex_handle   new_v = diag.new_vertex (p);
  Edge_handle     new_e = diag.new_edge();
  
  // Duplicate the curves container associated with e.
  if (! e->is_empty())
    new_e->add_curves (e->curves_begin(), e->curves_end());
  
  // Connect the new vertex between e and new_e.
  new_v->set_left (e);
  new_v->set_right (new_e);
  
  new_e->set_left (new_v);
  if (e != diag.rightmost())
    new_e->set_right (e->right());
  else
    diag.set_rightmost (new_e);

  e->set_right (new_v);

  // Return the new vertex.
  return (new_v);
}

CGAL_END_NAMESPACE

#endif