env_divide_and_conquer_2_impl.h

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

// Copyright (c) 2006  Tel-Aviv University (Israel).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/Envelope_2/include/CGAL/Envelope_2/Env_divide_and_conquer_2_impl.h $
// $Id: Env_divide_and_conquer_2_impl.h 37894 2007-04-03 18:32:11Z efif $
//
// Author(s)     : Ron Wein   <[e-mail]>

#ifndef CGAL_ENVELOPE_DIVIDE_AND_CONQUER_2_IMPL_H
#define CGAL_ENVELOPE_DIVIDE_AND_CONQUER_2_IMPL_H

/*! \file
 * Definitions of the functions of the Envelope_divide_and_conquer_2 class.
 */

CGAL_BEGIN_NAMESPACE

/*! \todo Make the handlers default constructibe
 * Some compilers complain that the handlers are not initialized. Currently,
 * there is no requirement from the concepts they model respectively to
 * have default constructors. The following is a work around.
 */
template <typename Handle>
class Vertex_initializer {
public:
  void operator()(Handle & handle) {}
};

template <typename Vertex>
class Vertex_initializer<Vertex *> {
public:
  void operator()(Vertex * & handle) {handle = NULL; }
};

// ---------------------------------------------------------------------------
// Construct the lower/upper envelope of the given list of non-vertical curves.
//
template <class Traits, class Diagram>
void Envelope_divide_and_conquer_2<Traits,Diagram>::
_construct_envelope_non_vertical (Curve_pointer_iterator begin,
                                  Curve_pointer_iterator end,
                                  Envelope_diagram_1& out_d)
{
  out_d.clear();
  
  if (begin == end)
  {
    return;
  }
  
  // Check if the range contains just a single curve.
  Curve_pointer_iterator    iter = begin;
  ++iter;
  
  if (iter == end)
  {
    // Construct a singleton diagram, which matches a single curve.
    _construct_singleton_diagram (*(*begin), out_d);
  }
  else
  {
    // Divide the given range of curves into two.
    Curve_pointer_iterator  div_it = begin;
    unsigned int            count = 0;
    
    for (iter = begin; iter != end; ++iter)
    {
      if (count % 2 == 0)
        ++div_it;
      
      count++;
    }
    
    // Construct the diagrams (envelopes) for the two sub-ranges recursively 
    // and then merge the two diagrams to obtain the result.
    Envelope_diagram_1   d1;
    Envelope_diagram_1   d2;
    
    _construct_envelope_non_vertical (begin, div_it,
                                      d1);
    
    _construct_envelope_non_vertical (div_it, end,
                                      d2);

    _merge_envelopes (d1, d2, out_d);

    // Print the minimization diagram.
    /* RWRW:
    Edge_const_handle    e = out_d.leftmost();
    Vertex_const_handle  v;

    std::cout << "The diagram: ";
    while (e != out_d.rightmost())
    {
      if (! e->is_empty())
        std::cout << e->curve() << "  ";
      else
        std::cout << "[empty]" << "  ";

      v = e->right();
      std::cout << "(" << v->point() << ")  ";
      
      e = v->right();
    }
    std::cout << "[empty]" << std::endl;
    */
  }
  
  return;
}

// ---------------------------------------------------------------------------
// Construct a singleton diagram, which matches a single curve.
//
template <class Traits, class Diagram>
void Envelope_divide_and_conquer_2<Traits,Diagram>::
_construct_singleton_diagram (const X_monotone_curve_2& cv,
                              Envelope_diagram_1& out_d)
{
  CGAL_assertion (out_d.leftmost() == out_d.rightmost());
  CGAL_assertion (out_d.leftmost()->is_empty());
  
  // Check if the given curve is bounded from the left and from the right.
  if (traits->boundary_in_x_2_object() (cv, MIN_END) != NO_BOUNDARY)
  {
    if (traits->boundary_in_x_2_object() (cv, MAX_END) != NO_BOUNDARY)
    {
      // The curve is defined over (-oo, oo), so its diagram contains
      // only a single edge.
      out_d.leftmost()->add_curve (cv);
      
      return;
    }

    // The curve is defined over (-oo, x], where x is finite.
    // Create a vertex and associate it with the right endpoint of cv.
    CGAL_precondition
      (traits->boundary_in_y_2_object() (cv, MAX_END) == NO_BOUNDARY);
    
    Vertex_handle  v = 
      out_d.new_vertex (traits->construct_max_vertex_2_object() (cv));
    Edge_handle    e_right = out_d.new_edge();
    
    v->add_curve (cv);
    v->set_left (out_d.leftmost());
    v->set_right (e_right);
    
    // The leftmost edge is associated with cv, and the rightmost is empty.
    out_d.leftmost()->add_curve (cv);
    out_d.leftmost()->set_right (v);
    
    e_right->set_left (v);
    out_d.set_rightmost (e_right);
    
    return;
  }
  
  if (traits->boundary_in_x_2_object() (cv, MAX_END) != NO_BOUNDARY)
  {
    // The curve is defined over [x, +oo), where x is finite.
    // Create a vertex and associate it with the left endpoint of cv.
    CGAL_precondition
      (traits->boundary_in_y_2_object() (cv, MIN_END) == NO_BOUNDARY);
    
    Vertex_handle  v = 
      out_d.new_vertex (traits->construct_min_vertex_2_object() (cv));
    Edge_handle    e_left = out_d.new_edge();
    
    v->add_curve (cv);
    v->set_left (e_left);
    v->set_right (out_d.rightmost());
    
    // The rightmost edge is associated with cv, and the leftmost is empty.
    out_d.rightmost()->add_curve (cv);
    out_d.rightmost()->set_left (v);
    
    e_left->set_right (v);
    out_d.set_leftmost (e_left);
    
    return;
  }
  
  // If we reached here, the curve is defined over a bounded x-range.
  // We therefore create the following diagram:
  //
  //             (empty)    v1     e       v2   (empty)
  //      -oo -------------(+)============(+)------------ +oo
  //
  CGAL_precondition
    (traits->boundary_in_y_2_object() (cv, MIN_END) == NO_BOUNDARY);
  CGAL_precondition
    (traits->boundary_in_y_2_object() (cv, MAX_END) == NO_BOUNDARY);
  
  Vertex_handle  v1 = 
    out_d.new_vertex (traits->construct_min_vertex_2_object() (cv));
  Vertex_handle  v2 = 
    out_d.new_vertex (traits->construct_max_vertex_2_object() (cv));
  Edge_handle    e_left = out_d.new_edge();
  Edge_handle    e_right = out_d.new_edge();
  Edge_handle    e = out_d.leftmost();
  
  v1->add_curve (cv);
  v1->set_left (e_left);
  v1->set_right (e);
  
  v2->add_curve (cv);
  v2->set_left (e);
  v2->set_right (e_right);
  
  e->add_curve (cv);
  e->set_left (v1);
  e->set_right (v2);
  
  e_left->set_right (v1);
  e_right->set_left (v2);
  
  out_d.set_leftmost (e_left);
  out_d.set_rightmost (e_right);
  
  return;
}

// ---------------------------------------------------------------------------
// Merge two minimization (or maximization) diagrams.
//
template <class Traits, class Diagram>
void Envelope_divide_and_conquer_2<Traits,Diagram>::
_merge_envelopes (const Envelope_diagram_1& d1,
                  const Envelope_diagram_1& d2,
                  Envelope_diagram_1& out_d)
{
  Edge_const_handle    e1 = d1.leftmost();
  bool                 is_leftmost1 = true;
  Vertex_const_handle  v1;
  Edge_const_handle    e2 = d2.leftmost();
  bool                 is_leftmost2 = true;
  Vertex_const_handle  v2;
  Vertex_const_handle  next_v;
  bool                 next_exists = true;
  Comparison_result    res_v = EQUAL;
  bool                 same_x = false;

  Vertex_initializer<Vertex_const_handle> v_init;
  v_init(v1);
  v_init(v2);
  v_init(next_v);
    
  do
  {
    // Locate the vertex that has smaller x-coordinate between v1 and v2.
    // If both have the same x-ccordinate, find the one that should be in
    // the envelope.
    same_x = false;
    
    if (e1 == d1.rightmost())
    {
      if (e2 == d2.rightmost())
      {
        // Both current edges do not have a vertex to their right.
        next_exists = false;
      }
      else
      {
        // e1 is not bounded from the right while e2 is.
        v2 = e2->right();
        next_v = v2;
        res_v = LARGER;
      }
    }
    else if (e2 == d2.rightmost())
    {
      // e2 is not bounded from the right while e1 is.
      v1 = e1->right();
      next_v = v1;
      res_v = SMALLER;
    }
    else
    {
      v1 = e1->right();
      v2 = e2->right();
      res_v = _compare_vertices (v1, v2, same_x);
      next_v = (res_v == SMALLER) ? v1 : v2;
    }
    
    // Check if the current edges represent empty intervals or not.
    if (! e1->is_empty() && ! e2->is_empty())
    {
      // Both edges are not empty, and there are curves defined on them.
      _merge_two_intervals (e1, is_leftmost1,
                            e2, is_leftmost2,
                            next_v, next_exists,
                            (res_v == SMALLER) ? 1 : 2,
                            out_d);
    }
    else if (! e1->is_empty() && e2->is_empty())
    {
      // e1 is not empty but e2 is empty:
      _merge_single_interval (e1,
                              next_v, next_exists,
                              (res_v == SMALLER),
                              out_d);
    }
    else if (e1->is_empty() && ! e2->is_empty())
    {
      // e1 is empty and e2 is not empty:
      _merge_single_interval (e2,
                              next_v, next_exists,
                              (res_v != SMALLER),
                              out_d);
    }
    else
    {
      // Both edges are empty: append an empty edge to out_d:
      if (next_exists)
      {
        Vertex_handle  new_v = _append_vertex (out_d, next_v->point(), e1);
        new_v->add_curves (next_v->curves_begin(), next_v->curves_end());
      }
    }
    
    // Proceed to the next diagram edge(s), if possible.
    if (next_exists)
    {
      // Check if we should proceed on d1 or on d2.
      if (res_v == SMALLER)
      {
        e1 = v1->right();
        is_leftmost1 = false;

        if (same_x)
        {
          e2 = v2->right();
          is_leftmost2 = false;
        }
      }
      else if (res_v == LARGER)
      {
        e2 = v2->right();
        is_leftmost2 = false;

        if (same_x)
        {
          e1 = v1->right();
          is_leftmost1 = false;
        }
      }
      else
      {
        e1 = v1->right();
        is_leftmost1 = false;
                
        e2 = v2->right();
        is_leftmost2 = false;
      }
    }
    
  } while (next_exists);
  
  return;
}