partition_y_monotone_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_y_monotone_2.h $
// $Id: partition_y_monotone_2.h 31311 2006-05-29 08:30:22Z wein $
// 
//
// Author(s)     : Susan Hert <[e-mail]>

//
// Implementaion of the algorithm from pp 49--55 of "Computational Geometry 
// Algorithms and  Applications" by de Berg, van Kreveld, Overmars, and 
// Schwarzkopf for producing a partitioning of a polygon into y-monotone
// pieces.
//
// NOTE:  e_i = (v_i, v_{i+1})
//
// TREE:
//   "Therefore we store the edges of P intersecting the sweep line in the 
//    leaves of a dynamic binary search tree T.  The left-to-right order of
//    the leaves of T corresponds to the left-to-right order of the edges.
//    Because we are only interested in edges to the left of split and merge
//    vertices we only need to store edges in T that have the interior of P
//    to their right.  With each edge in T we store its helper."
//
//

#ifndef CGAL_PARTITION_Y_MONOTONE_H
#define CGAL_PARTITION_Y_MONOTONE_H

#include <CGAL/Partition_2/Indirect_not_less_yx_2.h>
#include <CGAL/Partition_2/Indirect_edge_compare.h>
#include <CGAL/Segment_2_Ray_2_intersection.h>
#include <CGAL/Object.h>
#include <CGAL/Partition_2/Partitioned_polygon_2.h>
#include <CGAL/ch_selected_extreme_points_2.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 <map>

namespace CGAL {

enum Partition_y_mono_vertex_type {PARTITION_Y_MONO_START_VERTEX, 
                                   PARTITION_Y_MONO_SPLIT_VERTEX, 
                                   PARTITION_Y_MONO_REGULAR_VERTEX, 
                                   PARTITION_Y_MONO_COLLINEAR_VERTEX, 
                                   PARTITION_Y_MONO_MERGE_VERTEX, 
                                   PARTITION_Y_MONO_END_VERTEX};


//
// assumes CCW orientation of vertices
//
template <class BidirectionalCirculator, class Traits>
Partition_y_mono_vertex_type partition_y_mono_vertex_type(
                                BidirectionalCirculator c, 
                                const Traits& traits)
{
   BidirectionalCirculator previous = c;
   previous--;
   BidirectionalCirculator next = c;
   next++;
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
   std::cout << "partition_y_mono__vertex_type: previous " << *previous 
             << " c " << *c << " next " << *next  << std::endl;
#endif
   typename Traits::Compare_y_2 compare_y_2 = traits.compare_y_2_object();

   if (compare_y_2(*previous, *c) == EQUAL &&
       compare_y_2(*next, *c) == EQUAL)
      return PARTITION_Y_MONO_COLLINEAR_VERTEX;

   typename Traits::Less_yx_2   less_yx = traits.less_yx_2_object();
   typename Traits::Left_turn_2  left_turn = traits.left_turn_2_object();

   if (less_yx(*previous, *c)) 
   {
      if (less_yx(*next, *c))                // previous and next both less_yx
         if (left_turn(*previous, *c, *next)) // interior angle less than pi
             return PARTITION_Y_MONO_START_VERTEX;
         else                                // interior angle greater than pi
             return PARTITION_Y_MONO_SPLIT_VERTEX;
      else                                   // previous less_yx and next not
         return PARTITION_Y_MONO_REGULAR_VERTEX;
   }
   else 
   {
      if (less_yx(*c, *next))           // previous and next both not less_yx
        if (left_turn(*previous, *c, *next)) // interior angle less than pi
           return PARTITION_Y_MONO_END_VERTEX; 
        else                                // interior angle greater than pi
           return PARTITION_Y_MONO_MERGE_VERTEX;
      else                                 // next less_yx and previous not
        return PARTITION_Y_MONO_REGULAR_VERTEX;
   }
}

template <class Tree>
void partition_y_mono_print_tree(Tree tree)
{
   typedef typename Tree::iterator iterator;

   iterator it = tree.begin();
   for (; it != tree.end(); it++) {
    std::cout << "edge node " << *(*it).first << " helper " << *(*it).second 
              << std::endl;
   }
   std::cout << std::endl;
}

template <class BidirectionalCirculator, class Tree>
void partition_y_mono_handle_start_vertex(BidirectionalCirculator c, 
                                          Tree& tree)
{
   typedef typename Tree::value_type ValuePair;

#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
   std::cout << *c << " is a start vertex " << std::endl;
#endif
   tree.insert(ValuePair(c, c));
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
   std::cout << "partition_handle_start_vertex: after insert tree is " 
             << std::endl;
   partition_y_mono_print_tree(tree);
#endif
   // insert e_i (edge from *c to *++c) into "tree" with helper(e_i) = v_i
}

template <class BidirectionalCirculator, class Tree, 
          class Partition_Poly, class Traits>
void partition_y_mono_handle_end_vertex(BidirectionalCirculator c, Tree& tree, 
                                        Partition_Poly& partition_poly, 
                                        const Traits& traits )
{ 

#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
   std::cout << *c << " is an end vertex " << std::endl;
#endif

   typedef typename Tree::iterator   tree_iterator;
   tree_iterator it;
   BidirectionalCirculator previous = c;
   previous--;

#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
   std::cout << "partition_y_mono_handle_end_vertex: previous " << *previous 
             << std::endl;
#endif
   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_end_vertex: diagonal " 
                 << *(*it).second << " to " << *c << std::endl;
#endif
       partition_poly.insert_diagonal(c, (*it).second);
   }
   tree.erase(it);
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
   std::cout << "partition_y_mono_handle_end_vertex: after erase tree is " 
             << std::endl;
   partition_y_mono_print_tree(tree);
#endif
   // if helper(e_{i-1}) is a merge vertex
   //    insert diagonal connecting v_i to helper(e_{i-1})
   // delete e_{i-1} from tree
}

template<class BidirectionalCirculator, class Iterator, class Tree>
inline
void partition_y_mono_edge_directly_left(BidirectionalCirculator c, Tree& tree,
                                         Iterator& it)
{
   it = tree.lower_bound(c);  // edge directly to the left of v_i since the
                              // items in the tree are sorted from right to
                              // left
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
   if (it != tree.end())
   std::cout << "partition_y_mono_edge_directly_left: lower_bound  edge node: "
             << *((*it).first) << " helper " << *((*it).second) << std::endl;
#endif
}

template <class BidirectionalCirculator, class Tree, class Partition_Poly>
void partition_y_mono_handle_split_vertex(BidirectionalCirculator c, 
                                          Tree& tree,
                                          Partition_Poly& partition_poly)
{
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
   std::cout << *c << " is a split vertex " << std::endl;
#endif

   typedef typename Tree::iterator     tree_iterator;
   typedef typename Tree::value_type ValuePair;
   tree_iterator it;
   partition_y_mono_edge_directly_left(c, tree, it);
   if (it != tree.end()) 
   {
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
      std::cout << "partition_y_mono_handle_split_vertex: 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));
   }
   tree.insert(ValuePair(c, c));
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
   std::cout << "partition_y_mono_handle_split_vertex: "
             << "after erase and inserts tree is" << std::endl;
   partition_y_mono_print_tree(tree);
#endif
   // 1. find the edge e_j in tree directly to the left of v_i
   // 2. insert the diagonal connecting v_i to helper(e_j) 
   // 3. helper(e_j) = v_i
   // 4. Insert e_i in tree and set helper(e_i) to v_i
}

template <class BidirectionalCirculator, class Tree, 
          class Partition_Poly, class Traits>
void partition_y_mono_handle_merge_vertex(BidirectionalCirculator c, 
                                          Tree& tree,
                                          Partition_Poly& partition_poly, 
                                          const Traits& traits)
{
#ifdef CGAL_PARTITION_Y_MONOTONE_DEBUG
   std::cout << *c << " is a merge vertex " << std::endl;
#endif

   typedef typename Tree::iterator     tree_iterator;
   typedef typename Tree::value_type   ValuePair;
   BidirectionalCirculator prev = c;
   prev--;
   tree_iterator it = tree.find(prev);
   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_merge_vertex 1: diagonal " 
                << *(*it).second << " to " << *c << std::endl;
#endif