partition_greene_approx_convex_2.h

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

   {
      // new stack top becomes new first (and only) element of top chain
      stack.push_front(point_ref);
      top_chain.initialize(point_ref);
#ifdef CGAL_GREENE_APPROX_DEBUG
      std::cout << "stack_extend: top_chain.front " 
                << *top_chain.front() << std::endl;
#endif
   }
   else
      change_top_chain(polygon, point_ref, stack, top_chain, result, traits);
}

template <class Polygon, class BidirectionalCirculator, 
          class OutputIterator, class Traits>
void change_top_chain(Polygon& polygon, 
                      BidirectionalCirculator new_point_ref,
                      Circ_pair< BidirectionalCirculator >& stack,
                      Circ_pair< BidirectionalCirculator >& top_chain, 
                      OutputIterator& result, const Traits& traits)
{
   BidirectionalCirculator next_point_ref = new_point_ref;
   if (top_chain.direction() == COUNTERCLOCKWISE)
      next_point_ref++;
   else
      next_point_ref--;

#ifdef CGAL_GREENE_APPROX_DEBUG
   std::cout << "change_top_chain: top_chain.front " << *top_chain.front() 
             << " new_point_ref " << *new_point_ref 
             << " next_point_ref " << *next_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 (((top_chain.direction() == COUNTERCLOCKWISE) &&
       !right_turn(*top_chain.front(), *new_point_ref, *next_point_ref)) ||
      ((top_chain.direction() == CLOCKWISE) &&
       !left_turn(*top_chain.front(), *new_point_ref, *next_point_ref)))
   {
      top_chain.push_front(new_point_ref);
   }
   else 
   {
      typedef typename Traits::Polygon_2 new_Polygon_2;

      BidirectionalCirculator old_top_ref;
      bool done = false;
      bool big_angle_at_stack = false;
      bool small_angle_at_point = false;
      bool update_required;

      // pop off element already on top chain
      old_top_ref = stack.front();
      stack.pop_front();

      do 
      {
         new_Polygon_2 new_polygon;
#ifdef CGAL_GREENE_APPROX_DEBUG
         std::cout << "change_top_chain: stack.front " 
                   << *stack.front() << std::endl;
#endif
         if (top_chain.direction() == COUNTERCLOCKWISE) 
         {
            std::copy(stack.front(), next_point_ref, 
                      std::back_inserter(new_polygon));
            erase_vertices(old_top_ref, new_point_ref, polygon,
                           update_required);
         }
         else 
         {
            std::copy(new_point_ref, stack.before_front(), 
                      std::back_inserter(new_polygon));
            typedef typename Polygon::iterator iterator;
            erase_vertices(top_chain.front(), stack.front(), polygon,
                           update_required);
            top_chain.push_front(stack.front());
         }
         if (!is_degenerate_polygon_2(new_polygon.vertices_begin(),
                                      new_polygon.vertices_end(), traits))
         {
            *result = new_polygon; 
            result++;
         }
         if (stack.front() == stack.back())          // the "stack empty" case
         {
            done = true;
            stack.push_front(new_point_ref);
#ifdef CGAL_GREENE_APPROX_DEBUG
            std::cout << "change_top_chain: stack is empty. New stack top is "
                      << *stack.front() << std::endl;
            std::cout << "stack.back is " << *stack.back() << std::endl;
            std::cout << "stack.before_back is " << *stack.before_back() 
                      << std::endl;
#endif
            top_chain.initialize(new_point_ref); 
            // top chain should share top of stack
         }
         else    // stack size must be >= 2 here
         {
#ifdef CGAL_GREENE_APPROX_DEBUG
            std::cout << "change_top_chain: stack.front " 
                      << *stack.front() << std::endl;
#endif
            if (top_chain.direction() == COUNTERCLOCKWISE)
               big_angle_at_stack = !left_turn(*stack.before_front(), 
                                              *stack.front(), *new_point_ref);
            else
               big_angle_at_stack = !right_turn(*stack.before_front(), 
                                             *stack.front(), *new_point_ref);
            if (top_chain.direction() == COUNTERCLOCKWISE)
               small_angle_at_point = left_turn(*stack.front(), *new_point_ref,
                                               *next_point_ref);
            else
               small_angle_at_point = right_turn(*stack.front(), 
                                                 *new_point_ref,
                                                 *next_point_ref);
            if (!big_angle_at_stack && !small_angle_at_point) 
            {
               old_top_ref = stack.front();
               stack.pop_front();
            }
         }
      } while (!done && !big_angle_at_stack && !small_angle_at_point);
      if (big_angle_at_stack)  // promote point to stack
      {
         stack.push_front(new_point_ref);
         top_chain.initialize(new_point_ref); 
         // top chain shares top of stack
      }
      else if (small_angle_at_point) 
      {
         top_chain.push_back(stack.front());
         top_chain.push_front(new_point_ref);
      }
   }
}

template <class Polygon, class BidirectionalCirculator, class OutputIterator,
          class Traits>
void change_bottom_chain(Polygon& polygon, 
                         BidirectionalCirculator new_point_ref, 
                         Circ_pair< BidirectionalCirculator >& stack,
                         Circ_pair< BidirectionalCirculator >& bottom_chain, 
                         Circ_pair< BidirectionalCirculator >& top_chain, 
                         OutputIterator& result, const Traits& traits)
{
   BidirectionalCirculator next_point_ref = new_point_ref;
   if (bottom_chain.direction() == COUNTERCLOCKWISE)
      next_point_ref++;
   else
      next_point_ref--;
#ifdef CGAL_GREENE_APPROX_DEBUG
   std::cout << "change_bottom_chain: bottom_chain.front " 
             << *bottom_chain.front() << " new_point_ref " << *new_point_ref 
             << " next_point_ref " << *next_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) &&
        !left_turn(*bottom_chain.front(), *new_point_ref, 
                          *next_point_ref)) ||
       ((bottom_chain.direction() == COUNTERCLOCKWISE) &&
        !right_turn(*bottom_chain.front(), *new_point_ref, *next_point_ref)))
   {
      bottom_chain.push_front(new_point_ref);
   }
   else 
   {
      typedef typename Traits::Polygon_2 new_Polygon_2;

      bool done = false;
      bool small_angle_at_point = false;
      bool update_required;

      do 
      {
         new_Polygon_2 new_polygon;
         stack.pop_back();  // remove old bottom of stack
#ifdef CGAL_GREENE_APPROX_DEBUG
         std::cout << "change_bottom_chain: stack.front " << *stack.front()
                   << " stack.back " << *stack.back() << std::endl;
#endif
         if (bottom_chain.direction() == CLOCKWISE) 
         {
            std::copy(new_point_ref, stack.before_back(), 
                      std::back_inserter(new_polygon));
            erase_vertices(bottom_chain.front(), stack.back(), polygon,
                           update_required);
         }
         else 
         {
            std::copy(stack.back(), next_point_ref, 
                      std::back_inserter(new_polygon));
            erase_vertices(bottom_chain.back(), new_point_ref, polygon,
                           update_required);
         }
         if (!is_degenerate_polygon_2(new_polygon.vertices_begin(),
                                      new_polygon.vertices_end(), traits))
         {
            *result = new_polygon;  
            result++;
         }
         bottom_chain.initialize(stack.back());
         if (stack.back() == stack.front())   // form new stack with new 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()),*new_point_ref)) 
            {
#ifdef CGAL_GREENE_APPROX_DEBUG
               std::cout << "change_bottom_chain: reversing stack and "
                         << "swapping chains" << std::endl;
#endif
               stack.push_front(new_point_ref);  // reverse stack direction
               stack.change_dir();
               bottom_chain = top_chain;     // swap the chains
               top_chain.initialize(stack.front());
               top_chain.change_dir();
#ifdef CGAL_GREENE_APPROX_DEBUG
               std::cout << "change_bottom_chain:  stack is now " 
                    << *stack.back() << " " << *stack.front() 
                    << " dir " << int(stack.direction()) << std::endl;
               std::cout << "change_bottom_chain:  bottom_chain is now " 
                    << *bottom_chain.back() << " " << *bottom_chain.front() 
                    << " dir " << int(bottom_chain.direction()) << std::endl;
               std::cout << "change_bottom_chain:  top_chain is now " 
                    << *top_chain.back() << " " << *top_chain.front() 
                    << " dir " << int(top_chain.direction()) << std::endl;
#endif
            }
            else
               stack.push_back(new_point_ref); 
         }
         else    // stack size must be >= 2 here
         {
            // angle at new point is < 180
            if (bottom_chain.direction() == CLOCKWISE)
               small_angle_at_point = right_turn(*stack.back(), *new_point_ref,
                                                *next_point_ref);
            else
               small_angle_at_point = left_turn(*stack.back(), *new_point_ref,
                                               *next_point_ref);
         }
      } while (!done && !small_angle_at_point);

      if (small_angle_at_point)
      {
         bottom_chain.push_back(stack.back());
         bottom_chain.push_front(new_point_ref);
      }
   }
}

template <class Polygon, class BidirectionalCirculator, 
          class OutputIterator, class Traits>
void make_polygons_from_stack(Polygon& polygon,
                            const BidirectionalCirculator& high_point_ref, 
                            Circ_pair< BidirectionalCirculator >& stack,
                            Circ_pair< BidirectionalCirculator >& bottom_chain,
                            OutputIterator& result, const Traits& traits)
{
   bool update_required;
   // make polygons by connecting the high point to every point on the stack
   // except the first and the last. 
#ifdef CGAL_GREENE_APPROX_DEBUG
   std::cout << "make_polygons_from_stack: high_point_ref " << *high_point_ref 
        << " stack.back " << *stack.back() 
        << " stack.before_back " << *stack.before_back() << std::endl;
#endif
   typedef typename Traits::Polygon_2 new_Polygon_2;
   new_Polygon_2 new_polygon;
   BidirectionalCirculator next_point_ref = high_point_ref;
   if (bottom_chain.direction() == COUNTERCLOCKWISE)
      next_point_ref++;

   stack.pop_back();  
   while (stack.front() != stack.back()) 
   {
       new_Polygon_2 new_polygon;
#ifdef CGAL_GREENE_APPROX_DEBUG
       std::cout << "make_polygons_from_stack: stack.back " << *stack.back()
                 << std::endl;