partition_vertex_map.h

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

       }
       prev_e_it = e_it;
    }
    if ((*prev_e_it).poly_num1() != (*m_list.begin()).poly_num1() &&
        (*prev_e_it).poly_num1() != (*m_list.begin()).poly_num2() &&
        (*prev_e_it).poly_num2() != (*m_list.begin()).poly_num1() &&
        (*prev_e_it).poly_num2() != (*m_list.begin()).poly_num2())
    {
       return true;
    }

    return (num_unshared > 2);
  }


  // NOTE:  the edges here are sorted in CW order so the next CCW edge
  //        comes BEFORE the edge with endpoint v_info in the sorted list
  Edge_info next_ccw_edge_info(Vertex_info v_info) const
  {
    Self_const_circulator first_e(m_list.begin(), m_list.end(), m_list.begin());
    Self_const_circulator e_circ = first_e;

    do
    {
      if ((*e_circ).endpoint() == v_info)
      {
        e_circ--; // go to the previous endpoint 
        return *e_circ;
      }
    }
    while (++e_circ != first_e);
    return *first_e; // shouldn't get here unless v_info is not in list
  }

private :

  List m_list ;
};

#ifdef CGAL_CFG_RWSTD_NO_MEMBER_TEMPLATES
template <class Traits>
CW_indirect_edge_info_compare< Traits >
Edge_list<Traits>::cw_indirect_edge_info_compare;
#endif


template <class Traits>
std::ostream& operator<<(std::ostream& os, const Edge_list<Traits>& edges) 
{
   typename Edge_list<Traits>::const_iterator  e_it;

   for (e_it = edges.begin(); e_it != edges.end(); e_it++)
   {
    os << "edge with endpoint (" << (*(*e_it).endpoint().vertex_it())
             << ") from poly #" << (*e_it).poly_num1() 
             << " and poly #" << (*e_it).poly_num2() 
             << std::endl;
   }
   return os;
}

} // namesapce Partition_2

template <class Traits_>
class Partition_vertex_map  
{
public:

   typedef Traits_                         Traits;
   typedef CGAL::Vertex_info<Traits>       Vertex_info;
   typedef CGAL::Edge_info<Traits>         Edge_info;
   typedef Partition_2::Edge_list<Traits>  Edge_list;  

   typedef Partition_vertex_map<Traits> Self;

   typedef std::map<Vertex_info, Edge_list> Map ;

   typedef typename Map::const_iterator Self_const_iterator;
   typedef typename Map::iterator       Self_iterator;

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

   typedef typename Polygon_2::Vertex_iterator Vertex_iterator;

   Partition_vertex_map() {}

#ifdef CGAL_CFG_RWSTD_NO_MEMBER_TEMPLATES
  static CW_indirect_edge_info_compare<Traits> cw_indirect_edge_info_compare;
  static bool compare(const Edge_info & e1, const Edge_info& e2)
  {
    return cw_indirect_edge_info_compare(e1, e2);
  }
#endif

   template <class InputIterator>
   Partition_vertex_map(InputIterator first_poly, InputIterator last_poly)
   {  _build(first_poly, last_poly); }
  
   Self_const_iterator begin() const { return m_map.begin() ; }
   Self_iterator       begin()       { return m_map.begin() ; }
   Self_const_iterator end  () const { return m_map.end  () ; }
   Self_iterator       end  ()       { return m_map.end  () ; }

   bool polygons_overlap()
   {
      Self_iterator v_info;
      for (v_info = m_map.begin(); v_info != m_map.end(); v_info++)
      {
         if ((*v_info).second.edges_overlap((*v_info).first.vertex_it())) 
            return true;
      }
      return false;
   }

   template <class OutputIterator>
   OutputIterator union_vertices(OutputIterator result)
   {
       if (m_map.empty()) 
         return result;
   
       Self_iterator m_it = m_map.begin();
   
       // find a vertex with degree 2 (there must be at least one)
       while (m_it != m_map.end() && (*m_it).second.size() != 2)
          m_it++;
       CGAL_assertion (m_it != m_map.end());

       // insert this vertex and the two around it
       Vertex_info first_v_info = (*m_it).second.front().endpoint();
       Vertex_info prev_v_info = first_v_info ;
#ifdef CGAL_PARTITION_CHECK_DEBUG
       std::cout << "union_vertices: inserting " << (*prev_v_info.vertex_it()) << std::endl;
#endif
       *result = *prev_v_info.vertex_it();
       result++;
#ifdef CGAL_PARTITION_CHECK_DEBUG
       std::cout << "union_vertices: inserting "<< *(*m_it).first.vertex_it() << std::endl;
#endif
       *result = *(*m_it).first.vertex_it();
       result++;
       Vertex_info next_v_info = (*m_it).second.back().endpoint();
#ifdef CGAL_PARTITION_CHECK_DEBUG
       std::cout << "union_vertices: inserting " << *next_v_info.vertex_it() << std::endl;
#endif
       *result = *next_v_info.vertex_it();
       result++;

       // find the map iterator corresponding to the next vertex 
       prev_v_info  = (*m_it).first;
       Vertex_info v_info = next_v_info;
       m_it = m_map.find(v_info);
       
       while (v_info != first_v_info && m_it != m_map.end())
       {
#ifdef CGAL_PARTITION_CHECK_DEBUG
          std::cout << "union_vertices: prev_v_info " << (*prev_v_info.vertex_it())
                    << " v_info " << (*v_info.vertex_it()) << " next_v_info "
                    << (*next_v_info.vertex_it()) << std::endl;
#endif
    // Don't want to sort the edges for vertices of degree 2 because they
    // are already in CCW order (since the partition polygons were in CCW
    // order), and this is what you need to begin the construction 
    // of the union polygon.
          if ((*m_it).second.size() > 2)
          {

#ifdef CGAL_CFG_RWSTD_NO_MEMBER_TEMPLATES
            cw_indirect_edge_info_compare = 
              CW_indirect_edge_info_compare<Traits>((*m_it).first.vertex_it());
           (*m_it).second.sort(&Self::compare);
#else
            (*m_it).second.sort(
              CW_indirect_edge_info_compare<Traits>((*m_it).first.vertex_it()));
#endif
       	  }

          // find the previous vertex in this vertex's list
          next_v_info=(*m_it).second.next_ccw_edge_info(prev_v_info).endpoint();
          if (next_v_info != first_v_info)
          {
#ifdef CGAL_PARTITION_CHECK_DEBUG
             std::cout << "union_vertices: inserting "
                       << *next_v_info.vertex_it() << std::endl;
#endif
             *result = *next_v_info.vertex_it();
             result++;
          }
          prev_v_info  = v_info;
          v_info = next_v_info;
          m_it = m_map.find(v_info);
          CGAL_assertion (m_it == m_map.end() || (*m_it).first == v_info);
       }
#ifdef CGAL_PARTITION_CHECK_DEBUG
       if (v_info == first_v_info)
          std::cout << "union_vertices: stopped because first was reached "
                    << std::endl;
       else
          std::cout << "union_vertices: stopped because end was reached "
                    << std::endl;
#endif
       return result;
   }

private :

   template <class InputIterator>
   void _build(InputIterator poly_first, InputIterator poly_last)
   {

      typedef std::pair<Self_iterator, bool>          Location_pair;
      typedef std::pair<Vertex_info, Edge_list>   P_Vertex;
   
      Location_pair v_loc_pair;
      Location_pair begin_v_loc_pair;
      Location_pair prev_v_loc_pair;
   
      Vertex_iterator vtx_begin;
      Vertex_iterator vtx_end;
      Vertex_iterator v_it;
   
      int poly_num = 0;
      for (; poly_first != poly_last; poly_first++, poly_num++)
      {

        Polygon_2 const* poly_ptr = &(*poly_first);

        vtx_begin = (*poly_first).vertices_begin();
        vtx_end   = (*poly_first).vertices_end();
        begin_v_loc_pair = m_map.insert(P_Vertex( Vertex_info(vtx_begin,poly_ptr), Edge_list()));
  
        prev_v_loc_pair = begin_v_loc_pair;
        v_it = vtx_begin;

        for (v_it++; v_it != vtx_end; v_it++)
        {

           v_loc_pair = m_map.insert(P_Vertex( Vertex_info(v_it,poly_ptr), Edge_list()));

           insert_next_edge(prev_v_loc_pair.first,  v_loc_pair.first, poly_num);

           insert_prev_edge(v_loc_pair.first, prev_v_loc_pair.first, poly_num);

           prev_v_loc_pair = v_loc_pair;
        }
        insert_next_edge(prev_v_loc_pair.first, begin_v_loc_pair.first, 
                         poly_num);
        insert_prev_edge(begin_v_loc_pair.first, prev_v_loc_pair.first, 
                         poly_num);
      }
   }


   void insert_next_edge(Self_iterator& v1_ref, Self_iterator& v2_ref, int num)
   {
      (*v1_ref).second.insert_next((*v2_ref).first, num);
   }

   void insert_prev_edge(Self_iterator& v1_ref, Self_iterator& v2_ref, int num)
   {
      (*v1_ref).second.insert_prev((*v2_ref).first, num);
   }

private :

  Map m_map ;
};

#ifdef CGAL_CFG_RWSTD_NO_MEMBER_TEMPLATES
template <class Traits>
CW_indirect_edge_info_compare<Traits>
Partition_vertex_map<Traits>::cw_indirect_edge_info_compare;
#endif

}


#endif // CGAL_PARTITION_VERTEX_MAP_H