partition_y_monotone_2.h

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

      partition_poly.insert_diagonal(c, (*it).second);
   }
   tree.erase(it);
   
   partition_y_mono_edge_directly_left(c, tree, it);
   if (it != tree.end()) 
   {
      if (partition_y_mono_vertex_type((*it).second,traits) == 
             PARTITION_Y_MONO_MERGE_VERTEX) 
      {
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
      std::cout << "partition_y_mono_handle_merge_vertex 2: diagonal " 
                << *(*it).second << " to " << *c << std::endl;
#endif
         partition_poly.insert_diagonal(c, (*it).second);
      }
      BidirectionalCirculator ej = (*it).first;
      tree.erase(it);
      tree.insert(ValuePair(ej,c));
   }
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
   std::cout << "partition_y_mono_handle_merge_vertex: after erase(s) tree is "
             << std::endl;
   partition_y_mono_print_tree(tree);
#endif
   // 1. if helper(e_{i-1}) is a merge vertex
   //       insert the diagonal connecting v_i to helper(e_{i-1})
   // 2.  delete e_{i-1} from tree
   // 3.  find the edge e_j in tree directly to the left of v_i
   // 4.  if helper(e_j) is a merge vertex
   //        insert diagonal connecting v_i to helper(e_j) in polygon
   // 5.  helper(e_j) = v_i
}

template <class BidirectionalCirculator, class Traits>
bool partition_y_mono_interior_to_right(BidirectionalCirculator c,
                                        const Traits& traits)
{
   typename Traits::Compare_y_2 compare_y_2 = traits.compare_y_2_object();

   BidirectionalCirculator previous = c; previous--;

   Comparison_result cmp_y = compare_y_2(*previous, *c);
   if (cmp_y == LARGER) return true;

   BidirectionalCirculator next = c; next++;

   if (cmp_y == EQUAL && compare_y_2(*next, *c) == SMALLER) return true;

   return false;
}

template <class BidirectionalCirculator, class Tree, class Partition_Poly,
          class Traits>
void partition_y_mono_handle_regular_vertex(BidirectionalCirculator c, 
                                            Tree& tree, 
                                            Partition_Poly& partition_poly, 
                                            const Traits& traits )
{
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
   std::cout << *c << " is a regular vertex " << std::endl;
#endif
   typedef typename Tree::iterator     tree_iterator;
   typedef typename Tree::value_type   ValuePair;
   tree_iterator it;

   BidirectionalCirculator previous = c;
   previous--;

   if (partition_y_mono_interior_to_right(c, traits))  
   {
      it = tree.find(previous);
      CGAL_assertion( it != tree.end() );

      if (partition_y_mono_vertex_type((*it).second, traits) == 
             PARTITION_Y_MONO_MERGE_VERTEX)
      {
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
         std::cout << "partition_y_mono_handle_regular_vertex 1: diagonal " 
                   << *(*it).second << " to " << *c << std::endl;
#endif
         partition_poly.insert_diagonal(c, (*it).second);
      }
      tree.erase(it);
      tree.insert(ValuePair(c,c));
   }
   else 
   {
      partition_y_mono_edge_directly_left(c, tree, it);
      CGAL_assertion (it != tree.end());

      if (partition_y_mono_vertex_type((*it).second, traits) == 
             PARTITION_Y_MONO_MERGE_VERTEX)
      {
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
         std::cout << "partition_y_mono_handle_regular_vertex 2: diagonal " 
                   << *c << " to " << *(*it).second << std::endl;
#endif
         partition_poly.insert_diagonal(c, (*it).second);
      }
      BidirectionalCirculator ej = (*it).first;
      tree.erase(it);
      tree.insert(ValuePair(ej,c));
   }
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
   std::cout << "partition_y_mono_handle_regular_vertex: "
             << "after erase and insert tree is" << std::endl;
   partition_y_mono_print_tree(tree);
#endif
   //  if interior of polygon lies to the right of v_i
   //     if helper(e_{i-1}) is a merge vertex
   //        insert diagonal connecting v_i to helper(e_{i-1}) in polygon
   //     delete e_{i-1} from tree
   //     insert e_i in tree and set helper(e_i) to v_i
   //  else
   //     find the edge e_j in tree directly left of v_i
   //     if helper(e_j) is a merge vertex
   //        insert diagonal connecting v_i to helper(e_j) in D
   //     helper(e_j) = v_i
}

template <class BidirectionalCirculator, class Tree>
void partition_y_mono_handle_collinear_vertex(BidirectionalCirculator c, 
                                              Tree& tree)
{
   typedef typename Tree::iterator     tree_iterator;
   typedef typename Tree::value_type   ValuePair;
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
   std::cout << *c << " is a collinear vertex " << std::endl;
#endif

   tree_iterator it;

   BidirectionalCirculator previous = c;
   previous--;
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
   std::cout << *previous << " is the previous vertex " << std::endl;
#endif

   it = tree.find(previous);
   if ( it != tree.end() )
   {
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
      std::cout << "partition_y_mono_handle_collinear_vertex : removing " 
                << *(*it).first << std::endl;
#endif
      tree.erase(it);
   }
   tree.insert(ValuePair(c,c));
}


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

   typedef Partitioned_polygon_2< Traits >                 P_Polygon_2;
   typedef typename P_Polygon_2::iterator                  I;
   typedef Circulator_from_iterator<I>                     Circulator;

#if defined(CGAL_PARTITION_NO_POSTCONDITIONS) || \
    defined(CGAL_NO_POSTCONDITIONS) || defined(NDEBUG)
   OutputIterator res(result);
#else
   typedef typename Traits::Polygon_2                      Polygon_2;
   Tee_for_output_iterator<OutputIterator, Polygon_2>      res(result);
#endif // no postcondition

   P_Polygon_2 polygon(first, beyond);
   CGAL_partition_precondition(
    orientation_2(polygon.begin(), polygon.end(), traits) == COUNTERCLOCKWISE);

   Circulator circ(polygon.begin(), polygon.end()), done = circ;
   std::vector<Circulator>  circulators;
   CGAL_For_all(circ, done){
     circulators.push_back(circ);
   }
   std::sort(circulators.begin(), circulators.end(), Indirect_not_less_yx_2<Traits>(traits));

#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
   std::cout << "Initial vertex list: "<< circulators << std::endl;
   for(std::vector<Circulator>::const_iterator it = circulators.begin();
       it != circulators.end();
       it++){
     std::cout << **it << " " ; 
   }
   std::cout << std::endl;
#endif

   typedef std::map<Circulator, Circulator, 
                    Indirect_edge_compare<Circulator, Traits> > Tree;
   Tree tree;

   typename std::vector<Circulator>::iterator it = circulators.begin();
   for (; it != circulators.end(); it++) {
      switch (partition_y_mono_vertex_type(*it, traits)) 
      {
         case PARTITION_Y_MONO_START_VERTEX:
            partition_y_mono_handle_start_vertex(*it, tree);
            break;
         case PARTITION_Y_MONO_SPLIT_VERTEX:
            partition_y_mono_handle_split_vertex(*it, tree, polygon);
            break;
         case PARTITION_Y_MONO_END_VERTEX:
            partition_y_mono_handle_end_vertex(*it, tree, polygon, traits);
            break;
         case PARTITION_Y_MONO_MERGE_VERTEX:
            partition_y_mono_handle_merge_vertex(*it, tree, polygon, traits);
            break;
         case PARTITION_Y_MONO_REGULAR_VERTEX:
            partition_y_mono_handle_regular_vertex(*it, tree, polygon, traits);
            break;
         case PARTITION_Y_MONO_COLLINEAR_VERTEX:
            partition_y_mono_handle_collinear_vertex(*it, tree);
            break;
      }
   }
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
   I v_it;
   for (v_it = polygon.begin(); v_it != polygon.end(); v_it++) 
   {
      (*v_it).print_diagonals();
   }
#endif
   polygon.partition(res, 0);

   CGAL_partition_postcondition(
       y_monotone_partition_is_valid_2(polygon.begin(), polygon.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_y_monotone_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_y_monotone_2(first, beyond, result, 
                                 Partition_traits_2<K>());
}

}

#endif // CGAL_PARTITION_Y_MONOTONE_H