env_divide_and_conquer_2_impl.h

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

// ---------------------------------------------------------------------------
// Compare two diagram vertices.
//
template <class Traits, class Diagram>
Comparison_result Envelope_divide_and_conquer_2<Traits,Diagram>::
_compare_vertices (Vertex_const_handle v1,
                   Vertex_const_handle v2,
                   bool& same_x) const
{
  Comparison_result   res = traits->compare_x_2_object() (v1->point(),
                                                          v2->point());
  
  if (res != EQUAL)
  {
    same_x = false;
    return (res);
  }
  else
  {
    same_x = true;
  }

  // In case the x-coordinates of the two vertices are equal:
  res = traits->compare_xy_2_object() (v1->point(),
                                       v2->point());
  
  if ((env_type == LOWER && res == SMALLER) ||
      (env_type == UPPER && res == LARGER))
    return (SMALLER);
  else if ((env_type == LOWER && res == LARGER) ||
           (env_type == UPPER && res == SMALLER))
    return (LARGER);
  
  // The two vertices represent equal points:
  return (EQUAL);
}

// ---------------------------------------------------------------------------
// Deal with an interval which is non-empty in one of the merged diagrams and
// empty in the other.
//
template <class Traits, class Diagram>
void Envelope_divide_and_conquer_2<Traits,Diagram>::
_merge_single_interval (Edge_const_handle e,
                        Vertex_const_handle v, bool v_exists,
                        bool same_org,
                        Envelope_diagram_1& out_d)
{
  if (! v_exists)
  {
    // The non-empty edge e is unbounded from the right, so we simply have
    // to update the rightmost edge in out_d.
    out_d.rightmost()->add_curves (e->curves_begin(), e->curves_end());
    return;
  }
  
  Vertex_handle      new_v;
  
  if (same_org)
  {
    // The non-empty edge ends at v, so we simply insert it to out_d.
    new_v = _append_vertex (out_d, v->point(), e);
    new_v->add_curves (v->curves_begin(), v->curves_end());
    
    return;
  }
  
  // If v is not on e, we should insert it to the merged diagram only if it
  // is below (or above, in case of an upper envelope) the curves of e.
  Comparison_result  res = traits->compare_y_at_x_2_object() (v->point(),
                                                              e->curve());
  
  if ((res == EQUAL) ||
      (env_type == LOWER && res == SMALLER) ||
      (env_type == UPPER && res == LARGER))
  {
    new_v = _append_vertex (out_d, v->point(), e);
    new_v->add_curves (v->curves_begin(), v->curves_end());
  }
  
  if (res == EQUAL)
  {
    // In case of equality, append e's curves to those of the new vertex.
    new_v->add_curves (e->curves_begin(), e->curves_end());
  }
  
  return;
}

// ---------------------------------------------------------------------------
// Merge two non-empty intervals into the merged diagram.
//
template <class Traits, class Diagram>
void Envelope_divide_and_conquer_2<Traits,Diagram>::
_merge_two_intervals (Edge_const_handle e1, bool is_leftmost1,
                      Edge_const_handle e2, bool is_leftmost2,
                      Vertex_const_handle v, bool v_exists,
                      int org_v,
                      Envelope_diagram_1& out_d)
{
  // Get the relative position of two curves associated with e1 and e2
  // at the rightmost of the left endpoints of e1 and e2.
  Comparison_result      u_res;
  bool                   equal_at_v = false;
  Point_2                pu;
  bool                   pu_exists = false;
 
  u_res = traits->compare_y_position_2_object() (e1->curve(),
                                                 e2->curve());
  
  // Flip the result in case of an upper envelope.
  if (env_type == UPPER)
    u_res = CGAL::opposite (u_res);
  
  // Use the current rightmost of the two left vertices as a reference point.
  bool                 v_rm_exists = true;
  Vertex_const_handle  v_rm;
  Vertex_initializer<Vertex_const_handle> v_init;
  v_init(v_rm);

  if (is_leftmost1)
  {
    if (is_leftmost2)
      v_rm_exists = false;
    else
      v_rm = e2->left();
  }
  else
  {
    if (is_leftmost2)
      v_rm = e1->left();
    else
    {
      if ((traits->compare_xy_2_object() (e1->left()->point(),
                                          e2->left()->point()) == LARGER))
        v_rm = e1->left();
      else
        v_rm = e2->left();
    }
  }

  // Find the next intersection of the envelopes to the right of the current
  // rightmost point in the merged diagram.
  std::list<CGAL::Object>           objects;
  CGAL::Object                      obj;
  X_monotone_curve_2                icv;
  std::pair<Point_2, unsigned int>  ipt;
  
  traits->intersect_2_object() (e1->curve(), e2->curve(),
                                std::back_inserter(objects));
  
  while (! objects.empty())
  {
    // Pop the xy-lexicographically smallest intersection object.
    obj = objects.front();
    objects.pop_front();
    
    if (CGAL::assign(ipt, obj))
    {
      // We have a simple intersection point.
      if (v_rm_exists &&
          traits->compare_xy_2_object() (ipt.first, 
                                         v_rm->point()) != LARGER)
      {
        // The point is to the left of the current rightmost vertex in out_d,
        // so we skip it and continue examining the next intersections.
        // However, we update the last intersection point observed.
        pu = ipt.first;
        pu_exists = true;
        continue;
      }
      
      if (v_exists)
      {
        Comparison_result res = traits->compare_xy_2_object() (ipt.first, 
                                                               v->point());
        
        if (res == EQUAL)
          // v is an intersection points, so both curves are equal there:
          equal_at_v = true;
        
        if (res != SMALLER)
        {
          // We passed the next vertex, so we can stop here.
          break;
        }
      }
      
      // Create a new vertex in the output diagram that corrsponds to the
      // current intersection point.
      Vertex_handle        new_v;
      
      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)
        new_v = _append_vertex (out_d, ipt.first, e1);
      else
        new_v = _append_vertex (out_d, ipt.first, e2);
      
      // 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());
      
      // Update the handle to the rightmost vertex in the output diagram.
      v_rm = new_v;
      v_rm_exists = true;

      // Get the curve order immediately to the right of the intersection
      // point. Note that in case of even (non-zero) multiplicity the order
      // remains the same.
      if (ipt.second % 2 == 1)
      {
        // Odd multiplicity: flip the current comparison result.
        u_res = CGAL::opposite (u_res);
      }
      else if (ipt.second == 0)
      {
        // The multiplicity is unknown, so we have to compare the curves to
        // the right of their intersection point.
        u_res = traits->compare_y_at_x_right_2_object() (e1->curve(),
                                                         e2->curve(),
                                                         ipt.first);
        CGAL_assertion (u_res != EQUAL);
      }
    }
    else
    {
      // We have an x-monotone curve representing an overlap of the two
      // curves.
      bool     assign_success = CGAL::assign (icv, obj);
      
      CGAL_assertion (assign_success);
      if (! assign_success)
        continue;

      // Get the endpoints of the overlapping curves.
      const bool  has_left = 
        (traits->boundary_in_x_2_object() (icv, MIN_END) == NO_BOUNDARY);
      const bool  has_right = 
        (traits->boundary_in_x_2_object() (icv, MAX_END) == NO_BOUNDARY);
      Point_2     p1, p2;
      
      if (has_left)
        p1 = traits->construct_min_vertex_2_object() (icv);
      
      if (has_right)
        p2 = traits->construct_max_vertex_2_object() (icv);
      
      // Check if the overlapping curve is not relevant to our range.
      if (v_rm_exists && has_right &&
          traits->compare_xy_2_object() (p2, 
                                         v_rm->point()) != LARGER)
      {
        // The right point of the overlappinf curve is to the left of the
        // current rightmost vertex in out_d, so we skip it and continue
        // examining the next intersections.
        // However, we update the last intersection point observed.
        pu = p2;
        pu_exists = true;
        continue;
      }
      
      if (v_exists && has_right)
      {
        Comparison_result res = traits->compare_xy_2_object() (p1, 
                                                               v->point());
        
        if (res == EQUAL)
          // v is an intersection points, so both curves are equal there:
          equal_at_v = true;
        
        if (res != SMALLER)
        {
          // We passed the next vertex, so we can stop here.
          break;
        }
      }
      
      // There is an overlap between the range [u, v] and icv.
      if (has_left && 
          (! v_rm_exists ||
           traits->compare_xy_2_object() (p1, 
                                          v_rm->point()) == LARGER))
      {
        // Create an output edge that represent the portion of [u, v] to the
        // left of the overlapping curve.
        Vertex_handle        new_v;

        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)
          new_v = _append_vertex (out_d, ipt.first, e1);
        else
          new_v = _append_vertex (out_d, ipt.first, e2);
        
        // 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());

        // Update the handle to the rightmost vertex in the output diagram.
        v_rm = new_v;
        v_rm_exists = true;
      }
      
      if (has_right &&
          (! v_exists ||
           traits->compare_xy_2_object() (p2, 
                                          v->point()) == SMALLER))
      {
        // Create an edge that represents the overlapping curve.
        Vertex_handle        new_v;
        
        new_v = _append_vertex (out_d, ipt.first, e1);
        new_v->left()->add_curves (e2->curves_begin(), e2->curves_end());
        
        new_v->add_curves (e1->curves_begin(), e1->curves_end());
        new_v->add_curves (e2->curves_begin(), e2->curves_end());
        
        // Update the handle to the rightmost vertex in the output diagram.
        v_rm = new_v;
        v_rm_exists = true;

        // Compare the curves to the right of p2.
        u_res = traits->compare_y_at_x_right_2_object() (e1->curve(),
                                                         e2->curve(),
                                                         p2);
        CGAL_assertion (u_res != EQUAL);
      }
      else
      {
        // The overlapping curves reaches v.
        equal_at_v = true;
        u_res = EQUAL;
        break;
      }
      
    }
    
  } // End of the traversal over the intersection objects.
  
  // Handle the portion after the intersection objects.
  if (equal_at_v)
  {
    CGAL_assertion (v_exists);