minkowski_sum_conv_2.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/Minkowski_sum_2/include/CGAL/Minkowski_sum_2/Minkowski_sum_conv_2.h $
// $Id: Minkowski_sum_conv_2.h 38305 2007-04-18 15:35:01Z ophirset $
//
// Author(s)     : Ron Wein   <[e-mail]>

#ifndef CGAL_MINKOWSKI_SUM_CONV_H
#define CGAL_MINKOWSKI_SUM_CONV_H

#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Minkowski_sum_2/Labels.h>
#include <CGAL/Minkowski_sum_2/Arr_labeled_traits_2.h>
#include <CGAL/Minkowski_sum_2/Union_of_segment_cycles_2.h>

CGAL_BEGIN_NAMESPACE

/*! \class
 * A class for computing the Minkowski sum of two simple polygons based on the
 * convolution of their boundaries.
 */
template <class Kernel_, class Container_>
class Minkowski_sum_by_convolution_2
{
public:

  typedef Kernel_                                        Kernel;
  typedef CGAL::Polygon_2<Kernel, Container_>            Polygon_2;

private:

  // Kernel types:
  typedef typename Kernel::Point_2                       Point_2;
  typedef typename Kernel::Vector_2                      Vector_2;
  typedef typename Kernel::Direction_2                   Direction_2;
  
  // Kernel functors:
  typedef typename Kernel::Equal_2                       Equal_2;
  typedef typename Kernel::Construct_translated_point_2  Translate_point_2;
  typedef typename Kernel::Construct_vector_2            Construct_vector_2;
  typedef typename Kernel::Construct_direction_2         Construct_direction_2;
  typedef typename Kernel::Orientation_2                 Compute_orientation_2;
  typedef typename Kernel::Compare_xy_2                  Compare_xy_2;
  typedef typename Kernel::Counterclockwise_in_between_2 Ccw_in_between_2;

  // Polygon-related types:
  typedef typename Polygon_2::Vertex_circulator          Vertex_circulator;
  typedef std::pair<Vertex_circulator, unsigned int>     Vertex_ref;
  typedef std::pair<Vertex_ref, Vertex_ref>              Anchor;
  typedef std::list<Anchor>                              Anchors_queue;

  /*! \class
   * An auxiliary class for representing labels of convolved vertex pairs.
   */
  class Convolution_label
  {
  private:
    
    unsigned int      index1;       // Vertex index of the first polygon.
    unsigned int      index2;       // Vertex index of the second polygon.
    unsigned int      move_on;      // On which polygon do we move.

  public:

    /*! Default constructor. */
    Convolution_label () :
      move_on (0)
    {}

    /*! Constructor with parameters. */
    Convolution_label (unsigned int ind1, unsigned int ind2, 
		       unsigned int move) :
      index1 (ind1),
      index2 (ind2),
      move_on (move)
    {
      CGAL_precondition (move_on == 1 || move_on == 2);
    }

    /*! Less-then operator (for the usage of std::set). */
    bool operator< (const Convolution_label& label) const
    {
      if (index1 < label.index1)
	return (true);
      else if (index1 > label.index1)
	return (false);

      if (index2 < label.index2)
	return (true);
      else if (index2 > label.index2)
	return (false);

      return (move_on < label.move_on);
    }
  };

  typedef std::set<Convolution_label>                     Labels_set;

  // Traits-related types:
  typedef Arr_segment_traits_2<Kernel>                    Segment_traits_2;
  typedef Arr_labeled_traits_2<Segment_traits_2>          Traits_2; 

  typedef typename Segment_traits_2::X_monotone_curve_2   Segment_2;
  typedef typename Traits_2::X_monotone_curve_2           Labeled_segment_2;
  typedef std::list<Labeled_segment_2>                    Segments_list;

  typedef Union_of_segment_cycles_2<Traits_2, Polygon_2>  Union_2;

  // Data members:
  Equal_2                 f_equal;
  Translate_point_2       f_add;
  Construct_vector_2      f_vector;
  Construct_direction_2   f_direction;
  Compute_orientation_2   f_orientation;
  Compare_xy_2            f_compare_xy;
  Ccw_in_between_2        f_ccw_in_between;

public:

  /*! Default constructor. */
  Minkowski_sum_by_convolution_2 ()
  {
    // Obtain kernel functors.
    Kernel                ker;

    f_equal = ker.equal_2_object();
    f_add = ker.construct_translated_point_2_object(); 
    f_vector = ker.construct_vector_2_object();
    f_direction = ker.construct_direction_2_object();
    f_orientation = ker.orientation_2_object();
    f_compare_xy = ker.compare_xy_2_object();
    f_ccw_in_between = ker.counterclockwise_in_between_2_object();
  }    

  /*!
   * Compute the Minkowski sum of two simple polygons.
   * Note that as the input polygons may not be convex, the Minkowski sum may
   * not be a simple polygon. The result is therefore represented as
   * the outer boundary of the Minkowski sum (which is always a simple polygon)
   * and a container of simple polygons, representing the holes inside this
   * polygon.
   * \param pgn1 The first polygon.
   * \param pgn2 The second polygon.
   * \param sum_bound Output: A polygon respresenting the outer boundary
   *                          of the Minkowski sum.
   * \param sum_holes Output: An output iterator for the holes in the sum,
   *                          represented as simple polygons.
   * \pre Both input polygons are simple.
   * \return A past-the-end iterator for the holes in the sum.
   */
  template <class OutputIterator>
  OutputIterator operator() (const Polygon_2& pgn1,
                             const Polygon_2& pgn2,
                             Polygon_2& sum_bound,
                             OutputIterator sum_holes) const
  {
    CGAL_precondition (pgn1.is_simple());
    CGAL_precondition (pgn2.is_simple());

    // Prepare the vector of directions for the first polygon.
    const unsigned int    n1 = pgn1.size();
    const bool            forward1 = (pgn1.orientation() == COUNTERCLOCKWISE);
    std::vector<Direction_2>  dirs1 (n1);
    Vertex_circulator         curr1, next1;
    unsigned int              k1;

    next1 = curr1 = pgn1.vertices_circulator();
    for (k1 = 0; k1 < n1; k1++)
    {
      if (forward1)
        ++next1;
      else
        --next1;

      dirs1[k1] = f_direction (f_vector (*curr1, *next1));
      curr1 = next1;
    }

    // Prepare the vector of directions for the second polygon.
    // Also prepare a list containing all reflex vertices of this polygon.
    const unsigned int    n2 = pgn2.size();
    const bool            forward2 = (pgn2.orientation() == COUNTERCLOCKWISE);
    std::vector<Direction_2>  dirs2 (n2);
    Vertex_circulator         prev2, curr2, next2;
    Vertex_ref                bottom_left;
    bool                      is_convex2 = true;
    std::list<Vertex_ref>     reflex_vertices;
    unsigned int              k2;
    
    prev2 = next2 = curr2 = pgn2.vertices_circulator();
    
    if (forward2)
      --prev2;
    else
      ++prev2;

    for (k2 = 0; k2 < n2; k2++)
    {
      if (forward2)
        ++next2;
      else
        --next2;

      if (k2 == 0)
        bottom_left = Vertex_ref (curr2, 0);
      else if (f_compare_xy (*curr2, *(bottom_left.first)) == SMALLER)
        bottom_left = Vertex_ref (curr2, k2);

      if (f_orientation (*prev2, *curr2, *next2) == RIGHT_TURN)
      {
        // We found a reflex vertex.
        is_convex2 = false;
        reflex_vertices.push_back (Vertex_ref (curr2, k2));
      }

      dirs2[k2] = f_direction (f_vector (*curr2, *next2));
      prev2 = curr2;
      curr2 = next2;
    }

    // Add the bottom-left vertex of the second polygon to the reflex vertices.
    typename std::list<Vertex_ref>::iterator  reflex_it;

    reflex_vertices.push_front (bottom_left);

    // Construct the segments of the convolution cycles.
    unsigned int                  curr_id = 0;
    unsigned int                  cycles = 0;
    Segments_list                 conv_segments;
    Segments_list                 cycle;
    Labels_set                    used_labels;
    Anchor                        anchor;
    Anchors_queue                 queue;
    unsigned int                  loops;

    for (reflex_it = reflex_vertices.begin();
         reflex_it != reflex_vertices.end(); ++reflex_it)
    {
      // Get the current reflex vertex (or the bottom-left vertex).
      next2 = curr2 = reflex_it->first;
      k2 = reflex_it->second;

      if (forward2)
        ++next2;
      else
        --next2;

      // Search the first polygon for a vertex that contains (k1, k2, 1) in
      // a convolution cycle.
      next1 = curr1 = pgn1.vertices_circulator();
      for (k1 = 0; k1 < n1; k1++)
      {
        if (forward1)
          ++next1;
        else
          --next1;
        
        if ((used_labels.count (Convolution_label (k1, k2, 1)) == 0 &&
             (f_ccw_in_between (dirs1[k1],
                                dirs2[(n2 + k2 - 1) % n2],
                                dirs2[k2]) ||
              f_equal (dirs1[k1], dirs2[k2]))) ||
            (used_labels.count (Convolution_label (k1, k2, 2)) == 0 &&
             f_ccw_in_between (dirs2[k2],
                               dirs1[(n1 + k1 - 1) % n1],
                               dirs1[k1])))
        {
          // Construct the current convolution cycle.
          queue.clear();
          queue.push_back (Anchor (Vertex_ref (curr1, k1),
                                   Vertex_ref (curr2, k2)));
          loops = 0;

          while (! queue.empty())
          {
            // Pop the first pair of anchor vertices from the queue.
            anchor = queue.front();
            queue.pop_front();
            loops++;

            const Vertex_ref&    vert1 = anchor.first;
            const Vertex_ref&    vert2 = anchor.second;

            if (loops > 0 &&
                used_labels.count (Convolution_label (vert1.second, 
                                                      vert2.second, 2)) != 0)
            {
              loops--;
              continue;
            }

            // Add a loop to the current convolution cycle.
            curr_id++;
            _convolution_cycle (curr_id,
                                n1, forward1, dirs1, vert1.first, vert1.second,
                                n2, forward2, dirs2, vert2.first, vert2.second,
                                used_labels, queue,
                                cycle);

            // Catenate the segments of the current loop to the convolution
            // list.
            if (cycle.empty())
            {
              loops--;
            }
            else
            {
              conv_segments.splice (conv_segments.end(), cycle);
              CGAL_assertion (cycle.empty());
            }
          }
	  cycles++;
        }

        curr1 = next1;
      }
    }

    // Compute the union of the cycles that represent the Minkowski sum.
    Union_2     unite;

    sum_holes = unite (conv_segments.begin(), conv_segments.end(),
                       sum_bound, sum_holes);