partition_greene_approx_convex_2.h

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

#endif
       if (bottom_chain.direction() == CLOCKWISE) 
       {
         std::copy(high_point_ref, stack.before_back(), 
                   std::back_inserter(new_polygon));
         erase_vertices(bottom_chain.front(), stack.back(), polygon,
                        update_required);
         bottom_chain.initialize(stack.back());
       }
       else 
       {
         std::copy(stack.back(), next_point_ref, 
                   std::back_inserter(new_polygon));
         erase_vertices(bottom_chain.back(), high_point_ref, polygon,
                        update_required);
         bottom_chain.push_back(stack.back());
       }
       if (!is_degenerate_polygon_2(new_polygon.vertices_begin(),
                                    new_polygon.vertices_end(), traits))
       {
          *result = new_polygon; 
          result++;
       }
       stack.pop_back();  
   }
   // add remaining points from the top chain if there is more than one
   std::copy(polygon.begin(), polygon.end(), std::back_inserter(new_polygon));
   if (!is_degenerate_polygon_2(new_polygon.vertices_begin(),
                                new_polygon.vertices_end(), traits))
   {
      *result = new_polygon;
      result++;
   }
}

template<class BidirectionalCirculator, class Traits>
void find_smallest_yx(BidirectionalCirculator& first, const Traits& traits)
{
   BidirectionalCirculator current = first;
   current++;
   // find out which direction to go
   typename Traits::Less_yx_2     less_yx = traits.less_yx_2_object();
   if (less_yx(*current, *first))   // go foward
   {
      do 
      {
         first++;
         current++;
      } while (less_yx(*current, *first));
   }
   else 
   {
      current = first;
      current--;
      if (less_yx(*current, *first))    // go backward
      {
        do 
        {
          first--;
          current--;
        } while (less_yx(*current, *first));
      }
   } // otherwise both previous and next are larger, so no need to move
}

template <class BidirectionalCirculator, class Traits>
bool second_point_is_next(BidirectionalCirculator first, const Traits& traits)
{
   BidirectionalCirculator next = first;
   next++;
   BidirectionalCirculator previous = first;
   previous--;
   typename Traits::Less_yx_2        less_yx = traits.less_yx_2_object();
   return less_yx(*next, *previous);
}

template <class BidirectionalCirculator, class Traits>
BidirectionalCirculator next_vertex(BidirectionalCirculator& ccw_current, 
                                    BidirectionalCirculator& cw_current, 
                                    const Traits& traits)
{
  BidirectionalCirculator ccw_next = ccw_current;
  ccw_next++;
  BidirectionalCirculator cw_next = cw_current;
  cw_next--;
#ifdef CGAL_GREENE_APPROX_DEBUG
  std::cout << "next_vertex: ccw_next " << *ccw_next << " cw_next " << *cw_next
            << std::endl;
#endif
  
  if (ccw_next == cw_next) 
  {
     cw_current = cw_next;
     ccw_current = ccw_next;
     return cw_next; 
  }
  else 
  {
     typename Traits::Less_yx_2     less_yx = traits.less_yx_2_object();
     if (less_yx(*ccw_next,*cw_next))
     {
        ccw_current = ccw_next;
        return ccw_next;
     }
     else
     {
        cw_current = cw_next;
        return cw_next;
     }
  }
}


template <class ForwardIterator, class OutputIterator, class Traits>
void ga_convex_decomposition(ForwardIterator first, ForwardIterator beyond,
                             OutputIterator& result, const Traits& traits)
{
   if (first == beyond) return;

   typedef typename Traits::Point_2                        Point_2;
   typedef std::list<Point_2>                              Vertex_list;
   typedef Circulator_from_container<Vertex_list>         Vertex_circulator;

   Vertex_list  polygon(first, beyond);

   CGAL_partition_precondition(
    orientation_2(polygon.begin(), polygon.end(), traits) == COUNTERCLOCKWISE);
   CGAL_partition_precondition(
    is_y_monotone_2(polygon.begin(), polygon.end(), traits));

   Vertex_circulator point_ref(&polygon);
   Vertex_circulator circ = point_ref;

#ifdef CGAL_GREENE_APPROX_DEBUG
   std::cout << "before find_smallest_yx " << std::endl;
   do 
   {
      std::cout << *circ << std::endl;
   } while (++circ != point_ref);
#endif

   find_smallest_yx(point_ref, traits);

   circ = point_ref;
#ifdef CGAL_GREENE_APPROX_DEBUG
   std::cout << "after find_smallest_yx " << std::endl;
   do 
   {
      std::cout << *circ << std::endl;
   } while (++circ != point_ref);
#endif

   Vertex_circulator ccw_chain_ref = point_ref;
   Vertex_circulator cw_chain_ref = point_ref;

   Circ_pair< Vertex_circulator > stack(point_ref, COUNTERCLOCKWISE);
   Circ_pair< Vertex_circulator > bottom_chain(point_ref, CLOCKWISE);
   Circ_pair< Vertex_circulator > top_chain(point_ref, COUNTERCLOCKWISE);

   // discover which is the direction to the next point
   if (second_point_is_next(point_ref, traits)) 
   {
     ccw_chain_ref++;
     stack.push_front(ccw_chain_ref);
     stack.set_direction(COUNTERCLOCKWISE);
     top_chain.initialize(ccw_chain_ref);
     top_chain.set_direction(COUNTERCLOCKWISE);
     bottom_chain.set_direction(CLOCKWISE);
   }
   else 
   {
     cw_chain_ref--;
     stack.push_front(cw_chain_ref);
     stack.set_direction(CLOCKWISE);
     top_chain.initialize(cw_chain_ref);
     top_chain.set_direction(CLOCKWISE);
     bottom_chain.set_direction(COUNTERCLOCKWISE);
   }
#ifdef CGAL_GREENE_APPROX_DEBUG
   std::cout << "after inserting first two points: ccw_chain_ref " 
             << *ccw_chain_ref << " cw_chain_ref " << *cw_chain_ref 
             << std::endl;
#endif
   
   while (ccw_chain_ref != cw_chain_ref)
   {
      point_ref = next_vertex(ccw_chain_ref, cw_chain_ref, traits);

#ifdef CGAL_GREENE_APPROX_DEBUG
      std::cout << "after next_vertex: ccw_chain_ref " << *ccw_chain_ref 
                << " cw_chain_ref " << *cw_chain_ref << std::endl;
      std::cout << "current point: " << *point_ref << std::endl;
#endif
      if (is_adjacent_to(point_ref, bottom_chain.front()))
         visible(polygon, point_ref, stack, bottom_chain, top_chain, 
                 result, traits);
      if (ccw_chain_ref == cw_chain_ref)
      {
         make_polygons_from_stack(polygon, point_ref, stack, 
                                  bottom_chain, result, traits);
         return;
      }
      if (is_adjacent_to(point_ref, stack.front()))
         stack_extend(polygon, point_ref, stack, top_chain, 
                      result, traits);
      else if (is_adjacent_to(point_ref, top_chain.front()))
         change_top_chain(polygon, point_ref, stack, top_chain, 
                          result, traits);
      else
         change_bottom_chain(polygon, point_ref, stack, bottom_chain, 
                             top_chain, result, traits);
   }
}



// should change this so it is like the others in that it adds diagonals
// to a partition polygon and then calls partition
//   have to be able to go over the vertices again in order to check the
//   result, so they have to be stored somewhere else.
template <class InputIterator, class OutputIterator, class Traits>
OutputIterator partition_greene_approx_convex_2(InputIterator first, 
                                                InputIterator beyond,
                                                OutputIterator result, 
                                                const Traits& traits)
{
   if (first == beyond) return result;

   typedef typename Traits::Point_2                          Point_2;
   typedef typename Traits::Polygon_2                        Polygon_2;

#if defined(CGAL_PARTITION_NO_POSTCONDITIONS) || \
    defined(CGAL_NO_POSTCONDITIONS) || defined(NDEBUG)
   OutputIterator res(result);
#else

   Tee_for_output_iterator<OutputIterator, Polygon_2>    res(result);
#endif // no postconditions

   Polygon_2  polygon(first, beyond);
   CGAL_partition_precondition(
      orientation_2(polygon.vertices_begin(), polygon.vertices_end(),
                                               traits) == COUNTERCLOCKWISE);

   std::list<Polygon_2> MP_list;
   typename std::list<Polygon_2>::iterator MP_it;

   y_monotone_partition_2(polygon.vertices_begin(), polygon.vertices_end(), 
                          std::back_inserter(MP_list), traits);

   for(MP_it = MP_list.begin(); MP_it != MP_list.end(); MP_it++)
   {
      ga_convex_decomposition((*MP_it).vertices_begin(), 
                              (*MP_it).vertices_end(), res, traits);
   }

   CGAL_partition_postcondition(
       convex_partition_is_valid_2(polygon.vertices_begin(), 
                                   polygon.vertices_end(), 
                                   res.output_so_far_begin(),
                                   res.output_so_far_end(), traits));

#if defined(CGAL_PARTITION_NO_POSTCONDITIONS) || \
    defined(CGAL_NO_POSTCONDITIONS) || defined(NDEBUG)
   return res;
#else
   return res.to_output_iterator();
#endif // no postconditions
}

template <class InputIterator, class OutputIterator>
inline
OutputIterator partition_greene_approx_convex_2(InputIterator first, 
                                                InputIterator beyond,
                                                OutputIterator result)
{
   typedef typename std::iterator_traits<InputIterator>::value_type Point_2;
   typedef typename Kernel_traits<Point_2>::Kernel   K;
   return partition_greene_approx_convex_2(first, beyond, result,  
                                           Partition_traits_2<K>());
}

}

#endif // CGAL_GREENE_APPROX_H