clusters.h

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

// Copyright (c) 2004-2005  INRIA Sophia-Antipolis (France).
// 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/Mesh_2/include/CGAL/Mesh_2/Clusters.h $
// $Id: Clusters.h 32781 2006-07-30 13:09:30Z afabri $
// 
//
// Author(s)     : Laurent RINEAU

#ifndef CGAL_MESH_2_CLUSTERS_H
#define CGAL_MESH_2_CLUSTERS_H

#include <CGAL/Filter_circulator.h>

#include <utility>
#include <boost/iterator/transform_iterator.hpp>

namespace CGAL {

namespace Mesh_2 
{

  namespace details 
  {
    template <class Tr>
    class Is_edge_constrained {
      const Tr* tr_;
    public:
      typedef Is_edge_constrained<Tr> Self;
      typedef typename Tr::Edge_circulator Edge_circulator;
      
      Is_edge_constrained(const Tr& tr) : tr_(&tr)
      {}

      bool operator()(const Edge_circulator& ec) const
      {
        return tr_->is_constrained(*ec);
      }
    };
  } // end namespace details

template <class Tr>
class Clusters
{
  typedef typename Tr::Vertex_handle          Vertex_handle;
  typedef typename Tr::Point                  Point;
  typedef typename Tr::Geom_traits Geom_traits;
  typedef typename Geom_traits::FT FT;
  typedef FT      Squared_length; /**<This typedef is used to remind that
                                     the lenght is squared. */
  typedef typename Tr::Edge_circulator Edge_circulator;
  
  /**
   *  Special type: filtered circulator that returns only constrained
   *  edges.
   */
  typedef Filter_circulator<Edge_circulator,
                            details::Is_edge_constrained<Tr> >
    Constrained_edge_circulator;

public:
  /** \name Clusters public types */

  /**
   * \c Cluster register several informations about clusters.
   * A cluster is a set of vertices v_i incident to one vertice
   * v_0, so that angles between segments [v_0, v_i] is less than 60
   * degres.
   */
  struct Cluster {
    bool reduced ; /**< Is the cluster reduced? */

    /** 
     * Smallest_angle gives the two vertices defining the
     * smallest angle in the cluster.
     */
    std::pair<Vertex_handle, Vertex_handle> smallest_angle;

    FT rmin; // @fixme: rmin has no meaning if reduced=false!!!
    Squared_length minimum_squared_length;

    /**
     * The following map tells what vertices are in the cluster and if
     * the corresponding segment has been splitted once.
     */
    typedef std::map<Vertex_handle, bool> Vertices_map;
    Vertices_map vertices;

    bool is_reduced() const {
      return reduced;
    }

    bool is_reduced(const Vertex_handle v) {
      return vertices[v];
    }
  };
private:
  /** \name Clusters associated types */

  typedef std::multimap<Vertex_handle, Cluster> Cluster_map;
  typedef typename Cluster_map::value_type Cluster_map_value_type;

  template <class Pair>
  struct Pair_get_first: public std::unary_function<Pair,
                                                    typename Pair::first_type>
  {
    typedef typename Pair::first_type result;
    const result& operator()(const Pair& p) const
    {
      return p.first;
    }
  };

  typedef typename Cluster::Vertices_map Cluster_vertices_map;

private:
  /* --- protected datas --- */

  Tr& tr; /**< The triangulation itself. */

  /**
   * Multimap \c Vertex_handle -> \c Cluster
   * Each vertex can have several clusters. 
   */
  Cluster_map cluster_map;

public:
  typedef typename Cluster_map::const_iterator const_iterator;
  typedef typename Cluster_map::iterator iterator;

  Clusters(Tr& tr_) : tr(tr_)
  {
  }

  /** For all vertices, calls create_clusters_of_vertex(). */
  void create_clusters();

private:
  /**
   * Computes clusters of the vertex \c v, using the auxiliary function
   * construct_cluster().
   */
  void create_clusters_of_vertex(const Vertex_handle v);

  /**
   * Adds the sequence [\c begin, \c end] to the cluster \c c and adds it 
   * to the clusters of the vertex \c v.
   */
  void construct_cluster(const Vertex_handle v,
                         Constrained_edge_circulator begin,
                         const Constrained_edge_circulator& end,
                         Cluster c = Cluster());

public:
  /** \name Functions to manage clusters during the refinement process. */

  /** 
   * Update the cluster of [\c va,\c vb], putting \c vm instead of \c vb.
   * If reduction=false, the edge [va,vm] is not set reduced. 
   */
  void update_cluster(Cluster& c, iterator it,
                      const Vertex_handle va, const Vertex_handle vb,
                      const Vertex_handle vm,
                      bool reduction = true);

  /**
   * Returns the cluster of [\c va,\c vb] in \c c and return true
   * if it is in a cluster. Returns also a const_iterator in \c it.
   */
  bool get_cluster(const Vertex_handle va, const Vertex_handle vb,
                   Cluster& c, iterator& it);

  /** Const version of get_cluster(). */
  bool get_cluster(const Vertex_handle va, const Vertex_handle vb,
                   Cluster& c, const_iterator& it) const;

  /** \name Auxiliary functions that return a boolean. */

  /**
   * Tells if the angle <pleft, pmiddle, pright> is less than 60 degres.
   * Uses squared_cosine_of_angle_times_4() and used by
   * create_clusters_of_vertex().
   */
  bool is_small_angle(const Point& pleft,
                      const Point& pmiddle,
                      const Point& pright) const;

private:
  /** \name Helping computing functions */

  /** Returns the squared cosine of the angle <pleft, pmiddle, pright>
      times 4. */
  FT squared_cosine_of_angle_times_4(const Point& pleft,
                                     const Point& pmiddle,
                                     const Point& pright) const;

  /** Helper functions to access the two vertices of an Edge
      source is the vertex around which the circulator turns. */
  //@{
  Vertex_handle source(const Edge_circulator& ec) const
  {
    return ec->first->vertex(tr.cw(ec->second));
  }

  Vertex_handle target(const Edge_circulator& ec) const
  {
    return ec->first->vertex(tr.ccw(ec->second));
  }
  //@}

public:
  /** \name CONST ACCESS FUNCTIONS */
  typedef typename boost::transform_iterator<
    Pair_get_first<typename Cluster_map::value_type>,
    typename Cluster_map::const_iterator>
  Cluster_vertices_iterator;

  typedef typename boost::transform_iterator<
    Pair_get_first<typename Cluster_vertices_map::value_type>,
    typename Cluster_vertices_map::const_iterator>
  Vertices_in_cluster_iterator;

  int size() const
  {
    return cluster_map.size();
  }

  Cluster_vertices_iterator clusters_vertices_begin() const
  {
    return Cluster_vertices_iterator(cluster_map.begin());
  }

  Cluster_vertices_iterator clusters_vertices_end() const
  {
    return Cluster_vertices_iterator(cluster_map.end());
  }

  unsigned int number_of_clusters_at_vertex(const Vertex_handle& vh) const 
  {
    typedef typename Cluster_map::const_iterator Iterator;
    typedef std::pair<Iterator, Iterator> Range;
    Range range = cluster_map.equal_range(vh);
    return std::distance(range.first, range.second);
  }

  // returns the sequence of vertices bellonging to the n-th cluster of vh
  std::pair<Vertices_in_cluster_iterator, Vertices_in_cluster_iterator>
  vertices_in_cluster_sequence(const Vertex_handle& vh,
                               const unsigned int n) const
  {
    typedef typename Cluster_map::const_iterator Iterator;
    typedef std::pair<Iterator, Iterator> Range;
    typedef typename Range::first_type Clusters_iterator;
    typedef Pair_get_first<typename Cluster_vertices_map::value_type>
      Get_first;

    Range range = cluster_map.equal_range(vh);
    Iterator first = range.first;
    std::advance(first, n);
    const Cluster& c = first->second;

    return
      std::make_pair(Vertices_in_cluster_iterator(c.vertices.begin()),
                     Vertices_in_cluster_iterator(c.vertices.end()));
  }

}; // end class Clusters

template <typename Tr>
void Clusters<Tr>::