refine_edges.h

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

// Copyright (c) 2004-2006  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/Refine_edges.h $
// $Id: Refine_edges.h 35459 2006-12-07 15:57:16Z lrineau $
// 
//
// Author(s)     : Laurent RINEAU

#ifndef CGAL_MESH_2_REFINE_EDGES_H
#define CGAL_MESH_2_REFINE_EDGES_H

#include <CGAL/Mesher_level.h>
#include <CGAL/Mesh_2/Triangulation_mesher_level_traits_2.h>
#include <CGAL/Mesh_2/Filtered_queue_container.h>

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

namespace CGAL {

/**
 * \namespace Mesh_2
 *   Defines classes that are not yet documented.
 * 
 * \namespace Mesh_2::details
 *   Namespace for internal use.
 */

namespace Mesh_2 {

  namespace details {

    /** This class defines several auxiliary types for \c Refine_edges. */
    template <typename Tr>
    struct Refine_edges_base_types
    {
      typedef typename Tr::Vertex_handle Vertex_handle;

      typedef std::pair<Vertex_handle,
                        Vertex_handle> Constrained_edge;

      /** Object predicate that tests if a given \c Constrained_Edge is
          really an edge of the triangulation and is constrained.
      */
      class Is_a_constrained_edge {
        const Tr& tr;
      public:
        /** \param tr_ points to the triangulation. */
        explicit Is_a_constrained_edge(const Tr& tr_) : tr(tr_) {}

        bool operator()(const Constrained_edge& ce) const
        {
          typename Tr::Face_handle fh;
          int i;
          return tr.is_edge(ce.first, ce.second, fh,i) &&
            fh->is_constrained(i);
        }
      };

      typedef ::CGAL::Mesh_2::Filtered_queue_container<Constrained_edge,
                                               Is_a_constrained_edge>
                           Default_container;
    };

  }; // end namespace details


  /**
   * Predicate class that verifies that an edge is strictly locally
   * conforming Gabriel. Moreover, This classes defines a predicate that
   * test if an edge is encroached by a given point.
   * \param Tr The type of the triangulation.
   */
  template <typename Tr>
  struct Is_locally_conforming_Gabriel
  {
    typedef typename Tr::Vertex_handle Vertex_handle;
    typedef typename Tr::Face_handle Face_handle;
    typedef typename Tr::Point Point;
    typedef typename Tr::Geom_traits Geom_traits;

    /** Operator that takes an edge (\c fh, \c index). */
    bool operator()(Tr& tr,
                    const Face_handle& fh,
                    const int i) const
    {
      const Vertex_handle& va = fh->vertex(tr. cw(i));
      const Vertex_handle& vb = fh->vertex(tr.ccw(i));

      const Vertex_handle& vi = fh->vertex(i);
      const Vertex_handle& mvi = tr.tds().mirror_vertex(fh, i);

      return( ( tr.is_infinite(vi) || 
                this->operator()(tr, va, vb, vi->point()) )
              &&
              ( tr.is_infinite(mvi) || 
                this->operator()(tr, va, vb, mvi->point()) )
              );
    }

    /** Operator that takes an edge (\c va, \c vb). */
    bool operator()(Tr& tr,
                    const Vertex_handle& va,
                    const Vertex_handle& vb) const
    {
      Face_handle fh;
      int i;
      CGAL_assertion_code( bool should_be_true = )
      tr.is_edge(va, vb, fh, i);
      CGAL_assertion( should_be_true == true );
      
      return this->operator()(tr, fh, i);
    }

    /**
     * Operator that takes an edge (\c fh, \c index) and a point \c p.
     * Tests if the point encroached the edge.
     */
    bool operator()(Tr& tr,
                    const Face_handle& fh,
                    const int i,
                    const Point& p) const
    {
      return this->operator()(tr,
                              fh->vertex(tr. cw(i)),
                              fh->vertex(tr.ccw(i)),
                              p);
    }

    /**
     * Operator that takes an edge (\c va, \c vb) and a point \c p.
     * Tests if the point encroached the edge.
     */
    bool operator()(Tr& tr,
                    const Vertex_handle& va,
                    const Vertex_handle& vb,
                    const Point& p) const
      {
        typedef typename Geom_traits::Angle_2 Angle_2;

        const Angle_2 angle = tr.geom_traits().angle_2_object();

        const Point& a = va->point();
        const Point& b = vb->point();

        return( angle(a, p, b) == ACUTE );
      }
  };

  /**
   * Predicate class that verifies that an edge is strictly locally
   * conforming Delaunay.
   * \param Tr The type of the triangulation.
   */
  template <typename Tr>
  struct Is_locally_conforming_Delaunay
  {
    typedef typename Tr::Vertex_handle Vertex_handle;
    typedef typename Tr::Face_handle Face_handle;
    typedef typename Tr::Point Point;
    typedef typename Tr::Geom_traits Geom_traits;

    /** Operator that takes an edge (\c fh, \c index). */
    bool operator()(Tr& tr,
                    const Face_handle& fh,
                    const int i) const
    {
      Vertex_handle vi;
      Vertex_handle mvi;

      if(aux_get_vi_mvi(tr, fh, i, vi, mvi)) {
        return true;
      }

      const Vertex_handle& va = fh->vertex(tr. cw(i));
      const Vertex_handle& vb = fh->vertex(tr.ccw(i));

      return aux_outside_of_circle(tr, vi, vb, va, mvi);
    }

    /** Operator that takes an edge (\c va, \c vb). */
    bool operator()(Tr& tr,
                    const Vertex_handle& va,
                    const Vertex_handle& vb) const
    {
      Face_handle fh;
      int i;
      CGAL_assertion_code( bool test = )
        tr.is_edge(va, vb, fh, i);
      CGAL_assertion( test == true );

      Vertex_handle vi;
      Vertex_handle mvi;

      if(aux_get_vi_mvi(tr, fh, i, vi, mvi)) {
        return true;
      }

      return aux_outside_of_circle(tr, vi, vb, va, mvi);
    }

  private:
    /** Private function that computes the two vertex vi and mvi that are
	one each side of the edge (fh, i) (vi is in fh and mvi is in
	fh->neighbor(i)) and return true if one of them is infinite.
    */
    bool
    aux_get_vi_mvi(Tr& tr,
		   const Face_handle& fh,
		   const int i,
		   Vertex_handle& vi,
		   Vertex_handle& mvi) const
    {
      vi = fh->vertex(i);
      mvi = tr.tds().mirror_vertex(fh, i);

      return ( tr.is_infinite(vi) || tr.is_infinite(mvi) );
    }

    /** Private function that returns true if the vertex vs is outside the
	oriented circle passing through vp, vq and vr.
    */
    bool
    aux_outside_of_circle(Tr& tr,
			  const Vertex_handle& vp,
			  const Vertex_handle& vq,
			  const Vertex_handle& vr,
			  const Vertex_handle& vs) const
    {
      typedef typename Geom_traits::Side_of_oriented_circle_2
        Side_of_oriented_circle_2;

      Side_of_oriented_circle_2 in_circle =
        tr.geom_traits().side_of_oriented_circle_2_object();
      
      const Point& p = vp->point();
      const Point& q = vq->point();
      const Point& r = vr->point();
      const Point& s = vs->point();

      return ( in_circle(p, q, r, s) == ON_NEGATIVE_SIDE );
    }
  }; // end of struct Is_locally_conforming_Delaunay

/**
 * This class is the base for the first level of Mesh_2: the edge
 * conforming level. It does not handle clusters.
 *
 * \param Tr is the type of triangulation on which the level acts.
 * \param Is_locally_conform defines the locally conform criterion: Gabriel
 *        or Delaunay. It defaults to the Garbriel criterion.
 * \param Container is the type of container. It defaults to a filtered
 *        queue of \c Vertex_handle pair (see \c Filtered_queue_container).
 */
template <
  class Tr,
  class Is_locally_conform = Is_locally_conforming_Gabriel<Tr>,
  class Container = 
    typename details::Refine_edges_base_types<Tr>::Default_container
>
class Refine_edges_base :
    public No_private_test_point_conflict,
    public No_after_no_insertion
{
public:
  typedef typename Tr::Finite_edges_iterator Finite_edges_iterator;
  typedef typename Tr::Face_circulator Face_circulator;
  
  typedef typename Tr::Vertex_handle Vertex_handle;
  typedef typename Tr::Face_handle Face_handle;
  typedef typename Tr::Edge Edge;
  typedef typename Tr::Point Point;
  typedef typename Tr::Geom_traits Geom_traits;

  typedef Triangulation_mesher_level_traits_2<Tr> Triangulation_traits;

  typedef typename Triangulation_traits::Zone Zone;

  typedef typename details::Refine_edges_base_types<Tr>::Constrained_edge
                               Constrained_edge;

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

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

  /** Predicates to filter edges. */
  typedef typename details::Refine_edges_base_types<Tr>
     ::Is_a_constrained_edge Is_a_constrained_edge;

  const Is_a_constrained_edge is_a_constrained_edge;

  Container edges_to_be_conformed; /**< Edge queue */

  /** The object predicate that defines the locally conform criteria. */
  Is_locally_conform is_locally_conform;

  Vertex_handle va, vb;

  bool imperatively;

public:
  /** \name CONSTRUCTORS */

  Refine_edges_base(Tr& tr_) :
    tr(tr_), is_a_constrained_edge(tr_),
    edges_to_be_conformed(is_a_constrained_edge),
    is_locally_conform(), imperatively(false), converter(tr_)
  {
  }

  /** \name HELPING FUNCTIONS */

  void clear()
  {
    edges_to_be_conformed.clear();