partition_vertex_map.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_vertex_map.h $
// $Id: Partition_vertex_map.h 37861 2007-04-03 10:28:28Z afabri $
// 
//
// Author(s)     : Susan Hert <[e-mail]>

#ifndef CGAL_PARTITION_VERTEX_MAP_H
#define CGAL_PARTITION_VERTEX_MAP_H

#include <map>
#include <iostream>
#include <CGAL/circulator.h>
#include <cassert>

#include <sstream>

namespace CGAL {

const int PARTITION_VMAP_UNSHARED_EDGE = -1;

template<class Traits_>
class Vertex_info 
{
public:

  typedef Traits_                                       Traits;
  typedef typename Traits::Polygon_2                    Polygon_2 ; 
  typedef typename Traits::Polygon_2::Vertex_iterator   Vertex_iterator;
  typedef typename Traits::Less_xy_2                    Less_xy_2;

  Vertex_info ( Vertex_iterator const& vx_it, Polygon_2 const* poly_ptr )
   :
    m_vx_it(vx_it)
   ,m_poly_ptr(poly_ptr)
  {}

  Vertex_iterator  vertex_it() const { return m_vx_it ; }
  Polygon_2 const* poly_ptr () const { return m_poly_ptr ; }

  friend bool operator == ( Vertex_info const& a, Vertex_info const& b )
  {
    return a.poly_ptr() == b.poly_ptr() && a.vertex_it() == b.vertex_it() ;   
  }

  friend bool operator != ( Vertex_info const& a, Vertex_info const& b ) { return !(a==b); }

  friend bool operator < ( Vertex_info const& a, Vertex_info const& b )
  {
    return Traits().less_xy_2_object()(*a.vertex_it(), *b.vertex_it());
  }

private:

  Vertex_iterator  m_vx_it   ;
  Polygon_2 const* m_poly_ptr ;
} ;

template <class Traits_>
class Edge_info
{
public:

 typedef Traits_                    Traits;
 typedef CGAL::Vertex_info<Traits>  Vertex_info;

public:

   Edge_info(Vertex_info e_ref, int p_num1) : _endpoint_ref(e_ref),
      _poly_num1(p_num1), _poly_num2(PARTITION_VMAP_UNSHARED_EDGE)
   { }

   void set_poly_num2(int p_num)
   {
      _poly_num2 = p_num;
   }

   Vertex_info endpoint() const { return _endpoint_ref; }
   int poly_num1() const { return _poly_num1; }
   int poly_num2() const { return _poly_num2; }


private:
   Vertex_info _endpoint_ref;
   int _poly_num1;
   int _poly_num2;
};

template <class Traits>
class CW_indirect_edge_info_compare
{
public:

   typedef CGAL::Vertex_info<Traits> Vertex_info ;
   typedef CGAL::Edge_info<Traits>   Edge_info;

   typedef typename Vertex_info::Vertex_iterator Vertex_iterator ;

   typedef typename Traits::Left_turn_2 Left_turn_2;
   typedef typename Traits::Less_xy_2   Less_xy_2;
   typedef typename Traits::Point_2     Point_2;

   CW_indirect_edge_info_compare (Vertex_iterator v_info) : vertex_it(v_info),
      left_turn(Traits().left_turn_2_object()),
      less_xy(Traits().less_xy_2_object())
   {}

   bool operator()(Edge_info e1, Edge_info e2)
   {
      bool e1_less = less_xy((*e1.endpoint().vertex_it()), *vertex_it);
      bool e2_less = less_xy((*e2.endpoint().vertex_it()), *vertex_it);
      bool e1_to_e2_left_turn = left_turn((*e1.endpoint().vertex_it()), *vertex_it, 
                                (*e2.endpoint().vertex_it()));

      // if both edges are on the same side of the vertical line through 
      // _vertex then e1 comes before e2 (in CW order from the vertical line)
      // if one  makes a left turn going from e1 to e2
      if (e1_less == e2_less)
          return e1_to_e2_left_turn;
      else // e1 comes first if it is to the right of the vertical line
          return !e1_less;
   }

private:
   Vertex_iterator vertex_it;  
   Left_turn_2     left_turn;
   Less_xy_2       less_xy;
};




namespace Partition_2 {

template <class Traits_>
class Edge_list 
{
public:

  typedef Traits_                                       Traits;
  typedef Edge_list<Traits>                             Self;
  typedef typename Traits::Point_2                      Point_2;
  typedef typename Traits::Orientation_2                Orientation_pred;
  typedef typename Traits::Polygon_2                    Polygon_2 ; 
  typedef typename Traits::Polygon_2::Vertex_iterator   Vertex_iterator;

  typedef CGAL::Vertex_info<Traits> Vertex_info;
  typedef CGAL::Edge_info<Traits>   Edge_info;

  typedef std::list<Edge_info> List ;

  typedef typename List::iterator       Self_iterator;
  typedef typename List::const_iterator Self_const_iterator;
  typedef typename List::size_type      size_type ;

  typedef Circulator_from_iterator<Self_const_iterator> Self_const_circulator;

#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

  Self_const_iterator begin() const { return m_list.begin() ; }
  Self_iterator       begin()       { return m_list.begin() ; }
  Self_const_iterator end  () const { return m_list.end  () ; }
  Self_iterator       end  ()       { return m_list.end  () ; }

  size_type size() const { return m_list.size() ; }

  Edge_info const& front() const { return m_list.front() ; }
  Edge_info      & front()       { return m_list.front() ; }

  Edge_info const& back() const { return m_list.back() ; }
  Edge_info      & back()       { return m_list.back() ; }

  template<class Compare> void sort ( Compare c ) { m_list.sort(c); }

  void insert_next(Vertex_info endpoint_ref, int num)
  {

    Self_iterator e_it;

    for (e_it = m_list.begin();  e_it != m_list.end() && e_it->endpoint() != endpoint_ref ; e_it++) 
    {
    }

    if (e_it != m_list.end())
    {
      (*e_it).set_poly_num2(num);
    }
    else
    {
      m_list.push_back(Edge_info(endpoint_ref, num));
    }
  }

  void insert_prev(Vertex_info endpoint_ref, int num)
  {

    Self_iterator e_it;

    for (e_it = m_list.begin(); e_it != m_list.end() &&  e_it->endpoint() != endpoint_ref ; e_it++) 
    {
    }

    if (e_it != m_list.end())
    {
      (*e_it).set_poly_num2(num);
    }
    else
    {
       m_list.push_front(Edge_info(endpoint_ref, num));
    }
  }

  // PRE: polygons must be simple
  bool edges_overlap(Vertex_iterator vertex_it) 
  {

#ifdef CGAL_PARTITION_CHECK_DEBUG
    std::cout << "before sort: edges for " << *vertex_it << std::endl;
    std::cout << *this << std::endl;
#endif

    int num_unshared = 0;

    // 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 when you construct the union 
    // polygon.
    if (m_list.size() > 2)
    {
#ifdef CGAL_CFG_RWSTD_NO_MEMBER_TEMPLATES
      cw_indirect_edge_info_compare = 
        CW_indirect_edge_info_compare<Traits>(vertex_it);
      m_list.sort(&Self::compare);
#else
      m_list.sort
        (CW_indirect_edge_info_compare<Traits>(vertex_it));
#endif
    }

#ifdef CGAL_PARTITION_CHECK_DEBUG
    std::cout << "after sort: edges for " << *vertex_it  << std::endl;
    std::cout << *this << std::endl;
#endif

    Self_const_iterator prev_e_it = m_list.begin();
    Self_const_iterator e_it;

    for (e_it = m_list.begin(); e_it != m_list.end(); e_it++)
    {
       if ((*e_it).poly_num1() == PARTITION_VMAP_UNSHARED_EDGE) 
          num_unshared++;
       if ((*e_it).poly_num2() == PARTITION_VMAP_UNSHARED_EDGE) 
          num_unshared++;

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