refine_edges.h

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

  }

  void set_imperative_refinement(bool b)
  {
    imperatively = b;
  }

  /** \name Functions that this level must declare. */

  Tr& triangulation_ref_impl()
  {
    return tr;
  }

  const Tr& triangulation_ref_impl() const
  {
    return tr;
  }

  Zone conflicts_zone_impl(const Point& p, Edge edge)
  {
    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 = triangulation_ref_impl().tds().mirror_index(f, i);
    std::pair<OutputItFaces,OutputItEdges>
    pit = std::make_pair(faces_out,edges_out);
    pit = triangulation_ref_impl().propagate_conflicts(p,f,Tr::ccw(i),pit);
    pit = triangulation_ref_impl().propagate_conflicts(p,f,Tr:: cw(i),pit);
    pit = triangulation_ref_impl().propagate_conflicts(p,n,Tr::ccw(ni),pit);
    pit = triangulation_ref_impl().propagate_conflicts(p,n,Tr:: cw(ni),pit);
    return zone; 
  }

  Vertex_handle insert_impl(const Point& p, Zone& zone)
  {
    return triangulation_ref_impl().star_hole(p,
					      zone.boundary_edges.begin(),
					      zone.boundary_edges.end(),
					      zone.faces.begin(),
					      zone.faces.end()
					      );
  }

  /** Scans all constrained edges and put them in the queue if they are
      encroached. */
  void scan_triangulation_impl()
  {
    clear();
#ifndef CGAL_IT_IS_A_CONSTRAINED_TRIANGULATION_PLUS
    for(Finite_edges_iterator ei = tr.finite_edges_begin();
        ei != tr.finite_edges_end();
        ++ei)
      if(ei->first->is_constrained(ei->second) &&
         !is_locally_conform(tr, ei->first, ei->second) )
        add_constrained_edge_to_be_conformed(*ei);
    
#else
  for(typename Tr::Subconstraint_iterator it = tr.subconstraints_begin();
      it != tr.subconstraints_end(); ++it) 
    {
      const Vertex_handle& v1 = it->first.first;
      const Vertex_handle& v2 = it->first.second;
      
      if(fh->is_constrained(i) &&
         !is_locally_conform(tr, v1, v2) )
        add_constrained_edge_to_be_conformed(v1, v2);
    }
#endif
  } // end scan_triangulation_impl()

  /** Tells if the queue of edges to be conformed is empty or not. */
  bool no_longer_element_to_refine_impl()
  {
    return edges_to_be_conformed.empty();
  }

  /** Get the next edge to conform. */
  Edge get_next_element_impl() 
  {
    Constrained_edge edge = edges_to_be_conformed.get_next_element();

    Face_handle fh;
    int index;

    CGAL_assertion_code( bool should_be_true =)
    tr.is_edge(edge.first, edge.second, fh, index);
    CGAL_assertion( should_be_true == true );

    return Edge(fh, index);
  }

  /** Pop the first edge of the queue. */
  void pop_next_element_impl()
  {
    edges_to_be_conformed.remove_next_element();
  }

  /** This version computes the refinement point without handling
      clusters. The refinement point of an edge is just the middle point of
      the segment.
      Saves the handles of the edge that will be splitted.
      This function is overridden in class Refine_edge_with_clusters.
  */
  Point refinement_point_impl(const Edge& edge) 
  {
    typename Geom_traits::Construct_midpoint_2
      midpoint = tr.geom_traits().construct_midpoint_2_object();

    va = edge.first->vertex(tr.cw (edge.second));
    vb = edge.first->vertex(tr.ccw(edge.second));

    return midpoint(va->point(), vb->point());
  }

  /** Does nothing. */
  void before_conflicts_impl(const Edge&, const Point&)
  {
  }

  /**
   * Test if the edges of the boundary are locally conforming.
   * Push which that are not in the list of edges to be conformed.
   */
  Mesher_level_conflict_status
  test_point_conflict_from_superior_impl(const Point& p,
					 Zone& zone)
  {
    Mesher_level_conflict_status status = NO_CONFLICT;
    
    for(typename Zone::Edges_iterator eit = zone.boundary_edges.begin();
        eit != zone.boundary_edges.end(); ++eit)
      { 
        const Face_handle& fh = eit->first;
        const int& i = eit->second;

        if(fh->is_constrained(i) && !is_locally_conform(tr, fh, i, p))
          {
            add_constrained_edge_to_be_conformed(*eit);
	    status = CONFLICT_BUT_ELEMENT_CAN_BE_RECONSIDERED;
          }
      }

    return status;
  }

  /** Unmark as constrained. */
  void before_insertion_impl(const Edge& e, const Point&,
			     const Zone&)
  {
    const Face_handle& f = e.first;
    const int& i = e.second;

    f->set_constraint(i, false);
    (f->neighbor(i))->set_constraint(triangulation_ref_impl().tds().mirror_index(f, i), false);
  }

  /**
   * Scans the edges of the star boundary, to test if they are both
   * locally conforming. If not, push them in the list of edges to be
   * conformed.
   * 
   */
  void after_insertion_impl(const Vertex_handle& v)
  {
#ifdef CGAL_MESH_2_VERBOSE
    std::cerr << "E";
#endif
    // @todo Perhaps we should remove destroyed edges too.
    // @warning This code has been rewroten!

    Face_circulator fc = tr.incident_faces(v), fcbegin(fc);
    if( fc == 0 ) return;

    do {
      const int i = fc->index(v);
      CGAL_assertion( i>=0 && i < 4);
      if( fc->is_constrained(i) &&
          !is_locally_conform(tr, fc, i) )
        add_constrained_edge_to_be_conformed(Edge(fc, i));
      ++fc;
    } while( fc != fcbegin );

    Face_handle fh;
    int index;

    CGAL_assertion_code(bool is_edge = )
    tr.is_edge(va, v, fh, index);
    CGAL_assertion(is_edge == true);

    fh->set_constraint(index, true);
    fh->neighbor(index)->set_constraint(triangulation_ref_impl().tds().mirror_index(fh, index), true);

    CGAL_assertion_code( is_edge = )
    tr.is_edge(vb, v, fh, index);
    CGAL_assertion(is_edge == true);

    fh->set_constraint(index, true);
    fh->neighbor(index)->set_constraint(triangulation_ref_impl().tds().mirror_index(fh, index), true);

    if(!is_locally_conform(tr, va, v))
      add_constrained_edge_to_be_conformed(va, v);
    
    if(!is_locally_conform(tr, vb, v))
      add_constrained_edge_to_be_conformed(vb, v);
  } // end after_insertion_impl

protected:
  /** \name Auxiliary functions */

  /** Add an \c Edge \c e in the queue. */
  void add_constrained_edge_to_be_conformed(const Edge& e)
  {
    const Vertex_handle& va = e.first->vertex(tr. cw(e.second));
    const Vertex_handle& vb = e.first->vertex(tr.ccw(e.second));
    edges_to_be_conformed.add_element(std::make_pair(va, vb));
  }

  /** Add an edge (\c va,\c  vb) in the queue. */
  void add_constrained_edge_to_be_conformed(const Vertex_handle& va,
                                            const Vertex_handle& vb)
  {
    edges_to_be_conformed.add_element(std::make_pair(va, vb));
  }

private: /** \name DEBUGGING TYPES AND DATAS */
  class From_pair_of_vertex_to_edge 
    : public std::unary_function<Constrained_edge, Edge>
  {
    Tr& tr;
  public:
    From_pair_of_vertex_to_edge(Tr& t) : tr(t) {};

    const Edge operator()(const Constrained_edge edge) const
    {
      Face_handle fh;
      int index;
      tr.is_edge(edge.first, edge.second, fh, index);
      return Edge(fh, index);
    }
  }; // end From_pair_of_vertex_to_edge

  // -- private data member --
  From_pair_of_vertex_to_edge converter;

private:

  typedef boost::filter_iterator<Is_a_constrained_edge,
                                 typename Container::const_iterator>
    Aux_edges_filter_iterator;

public:  /** \name DEBUGGING FUNCTIONS */
  typedef boost::transform_iterator<
    From_pair_of_vertex_to_edge,
    Aux_edges_filter_iterator> Edges_const_iterator;

  Edges_const_iterator begin() const
  {
    return Edges_const_iterator(
       Aux_edges_filter_iterator(is_a_constrained_edge,
                                 this->edges_to_be_conformed.begin(),
                                 this->edges_to_be_conformed.end()),
       converter);
  }

  Edges_const_iterator end() const
  {
    return Edges_const_iterator(
       Aux_edges_filter_iterator(is_a_constrained_edge,
                                 this->edges_to_be_conformed.end(),
                                 this->edges_to_be_conformed.end()),
       converter);
  }
}; // end class Refine_edges_base

  namespace details {
    template <typename Tr, typename Self>
    struct Refine_edges_types
    {
      typedef Triangulation_mesher_level_traits_2<Tr> Triangulation_traits;

      typedef Mesher_level <
	Tr,
        Self,
        typename Tr::Edge,
        Null_mesher_level,
	Triangulation_traits> Edges_mesher_level;
    }; // end Refine_edges_types
  } // end namespace details

template <typename Tr,
          typename Is_locally_conform = Is_locally_conforming_Gabriel<Tr>,
          typename Base = Refine_edges_base<Tr, Is_locally_conform> >
struct Refine_edges : 
  public Base, 
  public details::Refine_edges_types<Tr, 
    Refine_edges<Tr, Is_locally_conform, Base> >::Edges_mesher_level
{
  typedef Refine_edges<Tr, Is_locally_conform, Base> Self;

  typedef typename details::Refine_edges_types<Tr,
					       Self> Types;

  typedef typename Types::Edges_mesher_level Mesher;
public:
  Refine_edges(Tr& t, 
	       Null_mesher_level& null_level)
    : Base(t), Mesher(null_level)
  {
  }
}; // end Refine_edges


} // end namespace Mesh_2

} // end namespace CGAL

#endif // CGAL_MESH_2_REFINE_EDGES_H