partition_optimal_convex_2.h

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

             << std::endl;
   std::cout << "decompose(" << edge_num1 << ", " << edge_num2 
             << "): returning " << num_pieces << std::endl;
   partition_opt_cvx_debug_list_count--;
#endif
   return num_pieces;
}

//
// implementation of the naive n^3 visibility algorithm
//
template <class Polygon, class Traits>
bool partition_opt_cvx_is_visible_n3(const Polygon& polygon, unsigned int i,
                                     unsigned int j, const Traits& traits)
{
   typedef typename Traits::Segment_2     Segment_2;
   typedef typename Polygon::size_type    size_type;
   typedef typename Traits::Left_turn_2    Left_turn_2;
   typedef typename Traits::Point_2       Point_2;
   typedef typename Traits::Construct_segment_2 Construct_segment_2;

   static Construct_segment_2 construct_segment_2 = 
                                 traits.construct_segment_2_object();

   Segment_2 segment = construct_segment_2(polygon[i], polygon[j]);
   size_type prev_i = (i == 0)? polygon.size()-1: i - 1;
   size_type next_i = (i + 1)% polygon.size();
   size_type prev_j = (j == 0)? polygon.size()-1: j - 1;

   // determine if the edge goes through the interior of the polygon or not
   Left_turn_2 left_turn = traits.left_turn_2_object();
   Turn_reverser<Point_2, Left_turn_2> right_turn(left_turn);
   if (right_turn(polygon[prev_i], polygon[i], polygon[next_i]))
                                                      // concave angle
   {
     if (right_turn(polygon[prev_i], polygon[i], polygon[j]) &&
         right_turn(polygon[j], polygon[i], polygon[next_i]))
       return false;
   }
   else // left turn or straight
     if (right_turn(polygon[prev_i], polygon[i], polygon[j]) ||
         right_turn(polygon[j], polygon[i], polygon[next_i]))
       return false;

   size_type next_e;
   for (size_type e = 0; e < polygon.size(); e++) {
      if (e != i && e != prev_i && e != j && e != prev_j) {
         next_e = (e == polygon.size()-1)? 0 : e+1;
         Segment_2  edge = construct_segment_2(polygon[e], polygon[next_e]);
         if (do_intersect(segment, edge))
            return false;
      }
   }
   return true;
}

// when consecutive sequence of vertices are collinear, they must all be 
// visible to each other as if there were no vertices in between.
template <class Polygon, class Traits>
void make_collinear_vertices_visible(Polygon& polygon, 
                                     Matrix<Partition_opt_cvx_edge>& edges, 
                                     const Traits& traits)
{
    typedef typename Polygon::size_type                   size_type;
    typedef typename Traits::Orientation_2                Orientation_2;
    Orientation_2 orientation = traits.orientation_2_object();

    size_type i; 
    size_type prev_j, j;
    size_type k, next_k;

    // start at the beginning, move backwards as long as the points are
    // collinear; move forward as long as the points are collinear;
    // when you find the extremes make the larger one visible to the smaller 
    // one loop until you reach the larger one each time starting again at the
    // larger
    i = polygon.size() - 1;
    prev_j = 0;
    j = 1;
    int start_i = 0;
    while (i > 0 && 
           orientation(polygon[i], polygon[prev_j], polygon[j]) == COLLINEAR)
    {
       prev_j = i;
       start_i = i;
       i--;
    }
    i = 0;
    prev_j = 1;
    j = 2;
    while (j < polygon.size() &&
           orientation(polygon[i], polygon[prev_j], polygon[j]) == COLLINEAR)
    {
       i++;
       prev_j++;
       j++;
    }
    // all points between start_i and prev_j are collinear so they must all
    // be visible to each other
    for (k = start_i; k != prev_j; )
    {
       next_k = k;
       do
       {
         next_k = (next_k == polygon.size() - 1) ? 0 : next_k+1;
         // the matrix should be upper triangular.
         if (k < next_k)
            edges[k][next_k].set_visible(true);
         else
            edges[next_k][k].set_visible(true);
       }
       while ( next_k != prev_j );
       k = (k == polygon.size() - 1) ? 0 : k+1;
    }
    i = prev_j;
    while (i < polygon.size())
    {
       prev_j = i+1;
       j = i+2;
       while (j < polygon.size() &&
              orientation(polygon[i], polygon[prev_j], polygon[j]) == 
              COLLINEAR)
       {
           j++;
           prev_j++;
       }
       // the edge from the first collinear vertex to the last has
       // the same validity as the edge ending at the last collinear vertex
       if (prev_j < polygon.size())
          for (k = i; k != prev_j; k++)
          {
             next_k = k;
             do
             {
               next_k++; 
               edges[k][next_k].set_visible(true);
             }
             while ( next_k != prev_j );
          }
       i = prev_j;
    }
}

template <class Polygon, class Traits>
void partition_opt_cvx_preprocessing(Polygon& polygon, 
                                     Matrix<Partition_opt_cvx_edge>& edges, 
                                     const Traits& traits)
{
    typedef typename Polygon::size_type                   size_type;

    typedef typename Polygon::iterator                    Vertex_iterator;
    typedef Vertex_visibility_graph_2<Traits>             Vis_graph;
    typedef typename Traits::Point_2                      Point_2;
    typedef std::pair<Point_2, Point_2>                   Point_pair;

    Vis_graph graph(polygon.begin(), polygon.end());

    size_type prev_i, i, next_i, next_next_i;
    size_type prev_j, j, next_j;

    for (i = 0; i < polygon.size(); i++) 
    {
       prev_i = (i == 0)?polygon.size()-1:i-1;
       next_i = (i + 1)% polygon.size();
       next_next_i = (next_i + 1)% polygon.size();
       edges[i][i].set_visible(true);      
       if (next_i != 0) 
       {                                     // endpoints of edges are visible
          edges[i][next_i].set_visible(true);// and done (value == 0)
          edges[i][next_i].set_done(true);   // except for the last edge used
       }
       edges[i][next_i].set_valid(polygon[prev_i], polygon[i], polygon[next_i],
                             polygon[i], polygon[next_i], polygon[next_next_i],
                             traits);

       for (j = i + 2 ; j < polygon.size(); j++)
       {
          prev_j = j-1;
          if (graph.is_an_edge(Point_pair(polygon[i], polygon[j])))
          {
             next_j = (j + 1)% polygon.size();
             edges[i][j].set_visible(true);
             edges[i][j].set_valid(polygon[prev_i],polygon[i],polygon[next_i],
                                   polygon[prev_j],polygon[j],polygon[next_j],
                                   traits);
             if (j == i+2) 
             {
                 edges[i][j].set_value(1); 
                 Partition_opt_cvx_diagonal_list d;
                 d.push_back(Partition_opt_cvx_diagonal(i,j));
                 edges[i][j].set_solution(d); 
                 edges[i][j].set_done(true); 
             }
             // triangles are a base case.
          }
       }
    }
    make_collinear_vertices_visible(polygon, edges, traits);
}


template <class InputIterator, class OutputIterator, class Traits>
OutputIterator partition_optimal_convex_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 typename P_Polygon_2::value_type                V;
   typedef typename P_Polygon_2::size_type                 S;
   typedef typename P_Polygon_2::difference_type           D;
   typedef Bidirectional_circulator_from_iterator<I,V,S,D> 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 postconditions

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

#ifdef CGAL_PARTITION_OPTIMAL_CONVEX_DEBUG
   std::cout << "The polygon: " << std::endl;
   for (S i = 0; i < polygon.size(); i++)
      std::cout << polygon[i] << " ";
   std::cout << std::endl;
#endif

   Matrix<Partition_opt_cvx_edge> edges(polygon.size(), polygon.size());
   partition_opt_cvx_preprocessing(polygon, edges, traits);
#ifdef CGAL_PARTITION_OPTIMAL_CONVEX_DEBUG
   std::cout << "after preprocessing edges are (done, valid, visible, value): "
             << std::endl;
   std::cout << edges << std::endl;
#endif
   
   Partition_opt_cvx_diagonal_list diag_list;
   if (polygon.size() > 0) 
   {
      partition_opt_cvx_decompose(0, polygon.size()-1, polygon, edges, 
                                  traits, diag_list);

      diag_list.pop_back(); // the last diagonal added is the edge from last 
                            // to first vertex (i.e., it is not a diagonal)
      Partition_opt_cvx_diagonal_list::const_iterator it;
      for (it = diag_list.begin(); it != diag_list.end(); it++) 
      {
         Circulator source(polygon.begin(), polygon.end(), 
                           polygon.begin() + (*it).first);
         Circulator target(polygon.begin(), polygon.end(),
                           polygon.begin() + (*it).second);
         polygon.insert_diagonal(source, target);
      }
      // the 1 is needed here to indicate that unnecessary edges should
      // be pruned away.  These crop up when there are collinear vertices.
      // See explanation at top of file.
      polygon.partition(res, 1);
      CGAL_partition_postcondition(
             convex_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_optimal_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_optimal_convex_2(first, beyond, result, 
                                     Partition_traits_2<K>());
}

}

#endif // CGAL_PARTITION_OPTIMAL_CONVEX_H