refine_edges.h

来自「CGAL is a collaborative effort of severa」· C头文件 代码 · 共 685 行 · 第 1/2 页

// Copyright (c) 2004  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.
//
// $Source: /CVSROOT/CGAL/Packages/Mesh_2/include/CGAL/Mesh_2/Refine_edges.h,v $
// $Revision: 1.10 $ $Date: 2004/11/16 17:32:14 $
// $Name:  $
//
// 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 {

  template <typename Tr>
  class Refine_edges_triangulation_mesher_level_traits_2
  {
  public:
    typedef Tr Triangulation;
    typedef typename Tr::Point Point;
    typedef typename Tr::Face_handle Face_handle;
    typedef typename Tr::Edge Edge;
    typedef typename Tr::Vertex_handle Vertex_handle;
    typedef typename Tr::Locate_type Locate_type;

    typedef Triangulation_mesher_level_traits_2<Tr> Std_traits;

    typedef typename Std_traits::Zone Zone;

  private:
    Edge edge;

  public:
    void set_edge(const Edge e)
    {
      edge = e;
    }

    Zone get_conflicts_zone(Tr& t, const Point& p)
    {
      Zone zone;

      typedef std::back_insert_iterator<typename Zone::Faces> OutputItFaces;
      typedef std::back_insert_iterator<typename Zone::Edges> OutputItEdges;

      OutputItFaces faces_out(zone.faces);
      OutputItEdges edges_out(zone.boundary_edges);

      const Face_handle& f = edge.first;
      const int& i = edge.second;
      *faces_out++ = f;
      const Face_handle n = f->neighbor(i);
      *faces_out++ = n;
      const int ni = f->mirror_index(i);
      std::pair<OutputItFaces,OutputItEdges>
	pit = std::make_pair(faces_out,edges_out);
      pit = t.propagate_conflicts(p,f,t.ccw(i),pit);
      pit = t.propagate_conflicts(p,f,t. cw(i),pit);
      pit = t.propagate_conflicts(p,n,t.ccw(ni),pit);
      pit = t.propagate_conflicts(p,n,t. cw(ni),pit);
      return zone; 
    }

    static Vertex_handle insert(Tr&t, const Point& p, Zone& zone)
    {
      return Std_traits::insert(t, p, zone);
    }
    
  }; // end Refine_edges_triangulation_mesher_level_traits_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 typename Tr::Face_handle Face_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_really_a_constrained_edge {
        const Tr& tr;
      public:
        /** \param tr_ points to the triangulation. */
        explicit Is_really_a_constrained_edge(const Tr& tr_) : tr(tr_) {}

        bool operator()(const Constrained_edge& ce) const
        {
          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_really_a_constrained_edge>
                           Default_container;
    };

  }; // end namespace details


  /**
   * Predicate class that verifies that an edge is 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 trianglation.
   */
  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& ct,
                    const Face_handle& fh,
                    const int i) const
    {
      typedef typename Geom_traits::Angle_2 Angle_2;
      
      const Angle_2 angle = ct.geom_traits().angle_2_object();

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

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

      const Vertex_handle& vi = fh->vertex(i);
      const Vertex_handle& mvi = fh->mirror_vertex(i);

      return( ( ct.is_infinite(vi) || 
                angle(a, vi->point(), b) != OBTUSE)
              &&
              ( ct.is_infinite(mvi) || 
                angle(a, mvi->point(), b) != OBTUSE)
              );
    }

    /** Operator that takes an edge (\c va, \c vb). */
    bool operator()(Tr& ct,
                    const Vertex_handle& va,
                    const Vertex_handle& vb) const
    {
      Face_handle fh;
      int i;
      CGAL_assertion_code( bool should_be_true = )
      ct.is_edge(va, vb, fh, i);
      CGAL_assertion( should_be_true == true );
      
      return this->operator()(ct, 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& ct,
                    const Face_handle& fh,
                    const int i,
                    const Point& p) const
    {
      return this->operator()(ct,
                              fh->vertex(ct. cw(i)),
                              fh->vertex(ct.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& ct,
                    const Vertex_handle& va,
                    const Vertex_handle& vb,
                    const Point& p) const
      {
        typedef typename Geom_traits::Angle_2 Angle_2;

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

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

        return( angle(a, p, b) != OBTUSE );
      }
  };

  /**
   * Predicate class that verifies that an edge is locally conforming
   * Delaunay.
   * \param Tr The type of the trianglation.
   */
  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& ct,
                    const Face_handle& fh,
                    const int i) const
    {
      typedef typename Geom_traits::Side_of_oriented_circle_2
        Side_of_oriented_circle_2;

      Side_of_oriented_circle_2 in_circle =
        ct.geom_traits().side_of_oriented_circle_2_object();
      
      const Vertex_handle& vi = fh->vertex(i);
      const Vertex_handle& mvi = fh->mirror_vertex(i);

      if(ct.is_infinite(vi) || ct.is_infinite(mvi)){
        return true;
      }

      const Point& a = fh->vertex(ct. cw(i))->point();
      const Point& b = fh->vertex(ct.ccw(i))->point();
      const Point& c = vi->point();
      const Point& d = mvi->point();

      return( in_circle(c, b, a, d) == ON_NEGATIVE_SIDE );
    }

    /** Operator that takes an edge (\c va, \c vb). */
    bool operator()(Tr& ct,
                    const Vertex_handle& va,
                    const Vertex_handle& vb) const
    {
      typedef typename Geom_traits::Side_of_oriented_circle_2
        Side_of_oriented_circle_2;

      Side_of_oriented_circle_2 in_circle =
        ct.geom_traits().side_of_oriented_circle_2_object();

      Face_handle fh;
      int i;
      CGAL_assertion_code( bool test = )
        ct.is_edge(va, vb, fh, i);
      CGAL_assertion( test == true );

      const Vertex_handle& vi = fh->vertex(i);
      const Vertex_handle& mvi = fh->mirror_vertex(i);

      if(ct.is_infinite(vi) || ct.is_infinite(mvi)){
        return true;
      }

      const Point& a = va->point();
      const Point& b = vb->point();
      const Point& c = vi->point();
      const Point& d = mvi->point();

      return( in_circle(c, b, a, d) == ON_NEGATIVE_SIDE );
    }
  };

/**
 * 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:
  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 typename Triangulation_mesher_level_traits_2<Tr>::Zone Zone;

  typedef Refine_edges_triangulation_mesher_level_traits_2<Tr>
    Triangulation_traits;

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

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

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

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