partition_greene_approx_convex_2.h

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

// Copyright (c) 2000  Max-Planck-Institute Saarbruecken (Germany).
// 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/Partition_2/include/CGAL/Partition_2/partition_greene_approx_convex_2.h $
// $Id: partition_greene_approx_convex_2.h 31311 2006-05-29 08:30:22Z wein $
// 
//
// Author(s)     : Susan Hert <[e-mail]>

#ifndef CGAL_GREENE_APPROX_H
#define CGAL_GREENE_APPROX_H

#include<vector>
#include<algorithm>
#include<iterator>
#include<CGAL/Partition_2/Circulator_pair.h>
#include<CGAL/Partition_2/partition_y_monotone_2.h>
#include<CGAL/Partition_2/Turn_reverser.h>
#include<CGAL/IO/Tee_for_output_iterator.h>
#include<CGAL/Partition_2/partition_assertions.h>
#include<CGAL/partition_is_valid_2.h>
#include<CGAL/Partition_traits_2.h>
#include<CGAL/is_y_monotone_2.h>
#include<CGAL/Partition_2/is_degenerate_polygon_2.h>

// These things should be constant: 
//   front is where you add things to a chain 
//   top chain shares its back with front (top) of stack
//   bottom chain shares its back with the back (bottom) of the stack 
//   bottom of the stack has lower y value than top.
// ==> chain direction is cw, make ccw polygon from front to back
// and chain direction is ccw, make ccw polygon from back to front

namespace CGAL {

template <class BidirectionalCirculator>
bool is_adjacent_to(BidirectionalCirculator new_point_ref, 
                    BidirectionalCirculator old_point_ref)
{
#ifdef CGAL_GREENE_APPROX_DEBUG
   std::cout << "is_adjacent_to: new_point " << *new_point_ref 
             <<             " old_point " << *old_point_ref << std::endl;
#endif
   // find the old point in original list of points 
   if (*new_point_ref == *(++old_point_ref)) return true;  // check ccw
#ifdef CGAL_GREENE_APPROX_DEBUG
   std::cout << "is_adjacent_to:  next point is " << *old_point_ref 
             << std::endl;
#endif
   old_point_ref--;
#ifdef CGAL_GREENE_APPROX_DEBUG
   std::cout << "is_adjacent_to:  old_point is " << *old_point_ref 
             << std::endl;
#endif
   if (*new_point_ref == *(--old_point_ref)) return true;  // check cw
#ifdef CGAL_GREENE_APPROX_DEBUG
   std::cout << "is_adjacent_to:  previous points is " << *old_point_ref 
             << std::endl;
#endif
   return false;
}


// erases vertices in the range [first, last) (counterclockwise)
template<class BidirectionalCirculator, class Polygon>
void erase_vertices(BidirectionalCirculator first, 
                    BidirectionalCirculator last,
                    Polygon& polygon, 
                    bool& update_required)
{
   typedef typename Polygon::iterator  Vertex_iterator;
   Vertex_iterator it = polygon.begin();
   Vertex_iterator temp_it;
   update_required = false;

#ifdef CGAL_GREENE_APPROX_DEBUG
   std::cout << "before erasing polygon is ";
   for (Vertex_iterator v = polygon.begin(); v != polygon.end(); v++)
   {
      std::cout << " " << *v;
   }
   std::cout << std::endl;
   std::cout << "erasing from " << *first << " to " << *last << std::endl;
#endif
   it = first.current_iterator();

   CGAL_partition_assertion (it != polygon.end());

   while ( (it != polygon.end()) && (*it != *last) ) 
   {
      while ( (it != polygon.end()) && (*it != *last) ) 
      {
#ifdef CGAL_GREENE_APPROX_DEBUG
         std::cout << "erase_vertices: erasing " << *it << std::endl;
#endif
         temp_it = it;
         // when the beginning vertex of the polygon is deleted, all the
         // circulators for that polygon become invalid and must be updated.
         if (it == polygon.begin())
            update_required = true;
         it++;
#ifdef CGAL_GREENE_APPROX_DEBUG
         if (it != polygon.end())
            std::cout << "erase_vertices: next vertex is " << *it << std::endl;
#endif
         polygon.erase(temp_it);
      } 
      if (it == polygon.end())
         it = polygon.begin();
   }
   // Yes, both loops here are necessary in case the range of vertices
   // includes the last and first points.
}


template <class Polygon, class BidirectionalCirculator, 
          class OutputIterator, class Traits>
void visible(Polygon& polygon,
             const BidirectionalCirculator& new_point_ref, 
             Circ_pair< BidirectionalCirculator >& stack, 
             Circ_pair< BidirectionalCirculator >& bottom_chain, 
             Circ_pair< BidirectionalCirculator >& top_chain, 
             OutputIterator&  result, 
             const Traits& traits)
{

#ifdef CGAL_GREENE_APPROX_DEBUG
   std::cout << "visible: stack.back " << *stack.back() 
             << " stack.before_back " << *stack.before_back() << 
                " new_point_ref " << *new_point_ref << std::endl;
#endif

    typedef typename Traits::Point_2      Point_2;
    typedef typename Traits::Left_turn_2   Left_turn_2;
    Left_turn_2    left_turn = traits.left_turn_2_object();
    Turn_reverser<Point_2, Left_turn_2> right_turn(left_turn);

    if (((bottom_chain.direction() == CLOCKWISE) && 
        right_turn(*stack.back(), *stack.before_back(), *new_point_ref)) ||
        ((bottom_chain.direction() == COUNTERCLOCKWISE) &&
        left_turn(*stack.back(), *stack.before_back(), *new_point_ref)))
    {
       typedef typename Traits::Polygon_2 new_Polygon_2;
       new_Polygon_2 new_polygon;

       bool done = false;
       bool big_angle_at_stack = false;
       bool is_visible = false;
       bool update_required;

#ifdef CGAL_GREENE_APPROX_DEBUG
       std::cout << "visible: bottom_chain.front " << *bottom_chain.front() 
                 << std::endl;
#endif
       do 
       {
          new_Polygon_2 new_polygon;
          stack.pop_back();
#ifdef CGAL_GREENE_APPROX_DEBUG
          std::cout << "visible: stack.back " << *stack.back() << std::endl;
#endif
          if (bottom_chain.direction() == CLOCKWISE) 
          {
             std::copy(bottom_chain.front(), stack.before_back(),
                       std::back_inserter(new_polygon));
             erase_vertices(bottom_chain.before_front(), stack.back(), polygon,
                            update_required);
          }
          else 
          {
             std::copy(stack.back(), bottom_chain.after_front(),
                       std::back_inserter(new_polygon));
             erase_vertices(bottom_chain.back(), bottom_chain.front(), polygon,
                            update_required);
          }
          if (!is_degenerate_polygon_2(new_polygon.vertices_begin(),
                                       new_polygon.vertices_end(), traits))
          {
             *result = new_polygon; 
             result++;
          }
          bottom_chain.push_back(stack.back());
          if (stack.back() == stack.front())   // form new stack with previous
          {                                    // point and old stack top 
                                               // (still on stack)
               done = true;                
               typename Traits::Less_yx_2  less_yx = traits.less_yx_2_object();
               if (less_yx(*(stack.front()),*bottom_chain.front())) 
               {
#ifdef CGAL_GREENE_APPROX_DEBUG
                  std::cout << "visible:  reversing stack and swapping chains "
                            << std::endl;
#endif
                  stack.push_front(bottom_chain.front()); 
                                               // reverse stack direction
                  stack.change_dir();
                  bottom_chain = top_chain;         // swap chains
                  top_chain.initialize(stack.front());
                  top_chain.change_dir();
#ifdef CGAL_GREENE_APPROX_DEBUG
                  std::cout << "visible:  stack is now " << *stack.back() 
                            << " " << *stack.front() 
                            << " dir " << int(stack.direction()) 
                            << std::endl;
                  std::cout << "visible:  bottom_chain is now " 
                            << *bottom_chain.back() << " "
                            << *bottom_chain.front() 
                            << " dir " << int(bottom_chain.direction()) 
                            << std::endl;
                  std::cout << "visible:  top_chain is now " 
                            << *top_chain.back() << " " << *top_chain.front() 
                            << " dir " << int(top_chain.direction()) 
                            << std::endl;
#endif
               }
               else
               {
                  stack.push_back(bottom_chain.front());
                  bottom_chain.push_back(bottom_chain.front()); 
               }
            }
            else // stack size must be >= 2 here
            {  
#ifdef CGAL_GREENE_APPROX_DEBUG
               std::cout << "visible: stack.before_back " 
                         << *stack.before_back() << std::endl;
#endif
               // angle at stack > 180
               if (bottom_chain.direction() == CLOCKWISE)
                  big_angle_at_stack = right_turn(*bottom_chain.front(), 
                                                 *stack.back(),
                                                 *stack.before_back()); 
               else
                  big_angle_at_stack = left_turn(*bottom_chain.front(), 
                                                        *stack.back(),
                                                        *stack.before_back()); 
               if (bottom_chain.direction() == CLOCKWISE)
                  is_visible = !right_turn(*stack.back(), *stack.before_back(),
                                          *new_point_ref);
               else
                  is_visible = !left_turn(*stack.back(), *stack.before_back(),
                                         *new_point_ref);
               // point can see stack bottom
            }
        } while (!done && !big_angle_at_stack && !is_visible);
        if (big_angle_at_stack)  // previous point is placed on bottom of stack
        {
           stack.push_back(bottom_chain.front()); 
           bottom_chain.push_back(bottom_chain.front());
        }
    }
}


template <class Polygon, class BidirectionalCirculator, 
          class OutputIterator, class Traits>
void stack_extend(Polygon& polygon,
                  BidirectionalCirculator& point_ref, 
                  Circ_pair< BidirectionalCirculator >& stack, 
                  Circ_pair< BidirectionalCirculator >& top_chain,
                  OutputIterator& result, const Traits& traits)
{
#ifdef CGAL_GREENE_APPROX_DEBUG
   std::cout << "stack_extend" << std::endl;
   std::cout << "stack_extend:  stack.before_front() " << *stack.before_front()
    << " stack.front " << *stack.front() << " point_ref " << *point_ref 
    << std::endl;
#endif

   typedef typename Traits::Point_2      Point_2;
   typedef typename Traits::Left_turn_2   Left_turn_2;
   Left_turn_2    left_turn = traits.left_turn_2_object();
   Turn_reverser<Point_2, Left_turn_2> right_turn(left_turn);
   if (((stack.direction() == COUNTERCLOCKWISE) && 
        right_turn(*stack.before_front(), *stack.front(), *point_ref)) ||
       ((stack.direction() == CLOCKWISE) && 
        left_turn(*stack.before_front(), *stack.front(), *point_ref)))