approx_offset_base_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/Approx_offset_base_2.h $
// $Id: Approx_offset_base_2.h 37897 2007-04-03 18:34:02Z efif $
//
// Author(s)     : Ron Wein   <[e-mail]>

#ifndef CGAL_APPROXIMATED_OFFSET_BASE_H
#define CGAL_APPROXIMATED_OFFSET_BASE_H

#include <CGAL/Polygon_2.h>
#include <CGAL/Gps_circle_segment_traits_2.h>
#include <CGAL/Minkowski_sum_2/Labels.h>
#include <CGAL/Minkowski_sum_2/Arr_labeled_traits_2.h>

CGAL_BEGIN_NAMESPACE

/*! \class
 * A base class for approximating the offset of a given polygon by a given
 * radius.
 */
template <class Kernel_, class Container_>
class Approx_offset_base_2
{
private:

  typedef Kernel_                                        Kernel;
  typedef typename Kernel::FT                            NT;

protected:

  typedef Kernel                                         Basic_kernel;
  typedef NT                                             Basic_NT;
  typedef CGAL::Polygon_2<Kernel, Container_>            Polygon_2;

private:
  
  // Kernel types:
  typedef typename Kernel::Point_2                       Point_2;
  typedef typename Kernel::Line_2                        Line_2;

  // Polygon-related types:
  typedef typename Polygon_2::Vertex_circulator          Vertex_circulator;

  // Traits-class types:
  typedef Gps_circle_segment_traits_2<Kernel>            Traits_2;
  typedef typename Traits_2::CoordNT                     CoordNT;
  typedef typename Traits_2::Point_2                     Tr_point_2;
  typedef typename Traits_2::Curve_2                     Curve_2;
  typedef typename Traits_2::X_monotone_curve_2          X_monotone_curve_2;

protected:

  typedef typename Traits_2::Polygon_2                   Offset_polygon_2;
  
  typedef Arr_labeled_traits_2<Traits_2>                 Labeled_traits_2; 
  typedef typename Labeled_traits_2::X_monotone_curve_2  Labeled_curve_2;

  // Data members:
  double        _eps;            // An upper bound on the approximation error.
  int           _inv_sqrt_eps;   // The inverse squared root of _eps.

public:

  /*!
   * Constructor.
   * \param eps An upper bound on the approximation error.
   */
  Approx_offset_base_2 (const double& eps) :
    _eps (eps)
  {
    CGAL_precondition (CGAL::sign (eps) == POSITIVE);

    _inv_sqrt_eps = static_cast<int> (1.0 / CGAL::sqrt (_eps));
    if (_inv_sqrt_eps == 0)
      _inv_sqrt_eps = 1;
  }    

protected:

  /*!
   * Compute curves that constitute the offset of a simple polygon by a given
   * radius, with a given approximation error.
   * \param pgn The polygon.
   * \param r The offset radius.
   * \param cycle_id The index of the cycle.
   * \param oi An output iterator for the offset curves.
   * \pre The value type of the output iterator is Labeled_curve_2.
   * \return A past-the-end iterator for the holes container.
   */
  template <class OutputIterator>
  OutputIterator _offset_polygon (const Polygon_2& pgn,
                                  const Basic_NT& r,
                                  unsigned int cycle_id,
                                  OutputIterator oi) const
  {
    // Prepare circulators over the polygon vertices.
    const bool            forward = (pgn.orientation() == COUNTERCLOCKWISE);
    Vertex_circulator     first, curr, next;

    first = pgn.vertices_circulator();
    curr = first; 
    next = first;

    // Traverse the polygon vertices and edges and approximate the arcs that
    // constitute the single convolution cycle.
    NT              x1, y1;              // The source of the current edge.
    NT              x2, y2;              // The target of the current edge.
    NT              delta_x, delta_y;    // (x2 - x1) and (y2 - y1), resp.
    NT              abs_delta_x;
    NT              abs_delta_y;
    CGAL::Sign      sign_delta_x;        // The sign of (x2 - x1).
    CGAL::Sign      sign_delta_y;        // The sign of (y2 - y1).
    NT              sqr_d;               // The squared length of the edge.
    NT              err_bound;           // An approximation bound for d.
    NT              app_d;               // The apporximated edge length.
    NT              app_err;             // The approximation error.
    CGAL::Sign      sign_app_err;        // Its sign.
    NT              lower_tan_half_phi;
    NT              upper_tan_half_phi;
    NT              sqr_tan_half_phi;
    NT              sin_phi, cos_phi;
    Point_2         op1;                 // The approximated offset point
                                         // corresponding to (x1, y1).
    Point_2         op2;                 // The approximated offset point
                                         // corresponding to (x2, y2).
    Line_2          l1, l2;              // Lines tangent at op1 and op2.
    Object          obj;
    bool            assign_success;
    Point_2         mid_p;               // The intersection of l1 and l2.
    Point_2         first_op;            // op1 for the first edge visited.
    Point_2         prev_op;             // op2 for the previous edge.

    unsigned int                    curve_index = 0;
    X_monotone_curve_2              seg1, seg2;
    bool                            dir_right1 = false, dir_right2 = false;
    int                             n_segments;

    Kernel                            ker;
    typename Kernel::Intersect_2      f_intersect = ker.intersect_2_object();
    typename Kernel::Construct_line_2 f_line = ker.construct_line_2_object();
    typename Kernel::Construct_perpendicular_line_2
                     f_perp_line = ker.construct_perpendicular_line_2_object();
    typename Kernel::Compare_xy_2     f_comp_xy = ker.compare_xy_2_object();

    Traits_2                        traits;
    std::list<Object>               xobjs;
    std::list<Object>::iterator     xobj_it;
    typename Traits_2::Make_x_monotone_2
                       f_make_x_monotone = traits.make_x_monotone_2_object();
    Curve_2                         arc;
    X_monotone_curve_2              xarc;

    do
    {
      // Get a circulator for the next vertex (in counterclockwise
      // orientation).
      if (forward)
	++next;
      else
	--next;

      // Compute the vector v = (delta_x, delta_y) of the current edge,
      // and compute the squared edge length.
      x1 = curr->x();
      y1 = curr->y();
      x2 = next->x();
      y2 = next->y();

      delta_x = x2 - x1;
      delta_y = y2 - y1;
      sqr_d = CGAL::square (delta_x) + CGAL::square (delta_y);

      sign_delta_x = CGAL::sign (delta_x);
      sign_delta_y = CGAL::sign (delta_y);

      if (sign_delta_x == CGAL::ZERO)
      {
        CGAL_assertion (sign_delta_y != CGAL::ZERO);

        // The edge [(x1, y1) -> (x2, y2)] is vertical. The offset edge lies
        // at a distance r to the right if y2 > y1, and to the left if y2 < y1.
        if (sign_delta_y == CGAL::POSITIVE)
        {
          op1 = Point_2 (x1 + r, y1);
          op2 = Point_2 (x2 + r, y2);
        }
        else
        {
          op1 = Point_2 (x1 - r, y1);
          op2 = Point_2 (x2 - r, y2);
        }

        // Create the offset segment [op1 -> op2].
        seg1 = X_monotone_curve_2 (op1, op2);
        dir_right1 = (sign_delta_y == CGAL::POSITIVE);

        n_segments = 1;
      }
      else if (sign_delta_y == CGAL::ZERO)
      {
        // The edge [(x1, y1) -> (x2, y2)] is horizontal. The offset edge lies
        // at a distance r to the bottom if x2 > x1, and to the top if x2 < x1.
        if (sign_delta_x == CGAL::POSITIVE)
        {
          op1 = Point_2 (x1, y1 - r);
          op2 = Point_2 (x2, y2 - r);
        }
        else
        {
          op1 = Point_2 (x1, y1 + r);
          op2 = Point_2 (x2, y2 + r);
        }

        // Create the offset segment [op1 -> op2].
        seg1 = X_monotone_curve_2 (op1, op2);
        dir_right1 = (sign_delta_x == CGAL::POSITIVE);