pm_overlayer.h

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

  // C++ is really friendly:
  #define USECMARK(t) const Mark& mark(t h) const { return Base::mark(h); }
  #define USEMARK(t)  Mark& mark(t h) const { return Base::mark(h); }
  USEMARK(Vertex_handle)
  USEMARK(Halfedge_handle)
  USEMARK(Face_handle)
  USECMARK(Vertex_const_handle)
  USECMARK(Halfedge_const_handle)
  USECMARK(Face_const_handle)
  #undef USEMARK
  #undef USECMARK

    enum Creation {POLYGON=0, POLYLINE=1};

  /*{\Moperations 1.1 1}*/

  struct Seg_info { // to transport information from input to output
    Halfedge_const_handle e;
    Vertex_const_handle   v;
    int                   i;

    Seg_info() : i(-1) {}
    Seg_info(Halfedge_const_handle e_, int i_) 
    { e=e_; i=i_; }
    Seg_info(Vertex_const_handle v_, int i_) 
    { v=v_; i=i_; }
    Seg_info(const Seg_info& si) 
    { e=si.e; v=si.v; i=si.i; }
    Seg_info& operator=(const Seg_info& si) 
    { e=si.e; v=si.v; i=si.i; return *this; }
    LEDA_MEMORY(Seg_info)
  };

  typedef std::list<Segment>                   Seg_list;
  typedef typename Seg_list::const_iterator    Seg_iterator;
  typedef std::pair<Seg_iterator,Seg_iterator> Seg_it_pair;


/*{\Mcreation 6}*/
PM_overlayer(Plane_map& P, const Geometry& g = Geometry()) : 
/*{\Mcreate |\Mvar| is a decorator object manipulating |P|.}*/
  Base(P), K(g) {}


template <typename Forward_iterator, typename Object_data_accessor>
void create(Forward_iterator start, Forward_iterator end, 
            Object_data_accessor& A, Creation cr = POLYGON) const
/*{\Mop produces in |P| the plane map consistent with the overlay
of the segments from the iterator range |[start,end)|. The data accessor 
|A| allows to initialize created vertices and edges with respect to the
segments in the iterator range. |A| requires the following methods:\\
[[void supporting_segment(Halfedge_handle e, Forward_iterator it)]]\\
[[void trivial_segment(Vertex_handle v, Forward_iterator it)]]\\
[[void starting_segment(Vertex_handle v, Forward_iterator it)]]\\
[[void passing_segment(Vertex_handle v, Forward_iterator it)]]\\
[[void ending_segment(Vertex_handle v, Forward_iterator it)]]\\
where |supporting_segment| is called for each non-trivial segment |*it|
supporting a newly created edge |e|, |trivial_segment| is called for
each trivial segment |*it| supporting a newly created vertex |v|, and
the three last operations are called for each non-trivial segment
|*it| starting at/passing through/ending at the embedding of a newly
created vertex |v|. 
\precond |Forward_iterator| has value type |Segment|.}*/
{
  CGAL_NEF_TRACEN("creating from iterator range");
  CGAL_assertion(cr == POLYGON || cr == POLYLINE);
  typedef PMO_from_segs<Self,Forward_iterator,Object_data_accessor> 
    Output_from_segments;
  typedef Segment_overlay_traits<
    Forward_iterator, Output_from_segments, Geometry> seg_overlay;
  typedef generic_sweep< seg_overlay > seg_overlay_sweep;
  typedef typename seg_overlay::INPUT input_range;
  Output_from_segments Out(*this, A);
  seg_overlay_sweep SOS( input_range(start, end), Out, K);
  SOS.sweep();
  if(cr==POLYGON)
    create_face_objects(Out);
  else
    create_face_objects_pl(Out);
  Out.clear_temporary_vertex_info();
}

void subdivide(const Plane_map& P0, const Plane_map& P1) const
/*{\Mop constructs the overlay of the plane maps |P0| and |P1| in
|P|, where all objects (vertices, halfedges, faces) of |P| are
\emph{enriched} by the marks of the supporting objects of the two
input structures: e.g. let |v| be a vertex supported by a node |v0| in
|P0| and by a face |f1| in |P1| and |D0|, |D1| be decorators of
type |PM_decorator| on |P0|,|P1|. Then |\Mvar.mark(v,0) = D0.mark(v0)|
and |\Mvar.mark(v,1) = D1.mark(f1)|.}*/
{
  Const_decorator PI[2];
  PI[0] = Const_decorator(P0); PI[1] = Const_decorator(P1);
  Seg_list Segments; int i;
  CGAL::Unique_hash_map<Seg_iterator,Seg_info> From;
  for (i=0; i<2; ++i) {
    Vertex_const_iterator v;
    for(v = PI[i].vertices_begin(); v != PI[i].vertices_end(); ++v)
      if ( PI[i].is_isolated(v) ) {
        Segments.push_back(segment(PI[i],v));
        From[--Segments.end()] = Seg_info(v,i);
      }
    Halfedge_const_iterator e;
    for(e = PI[i].halfedges_begin(); e != PI[i].halfedges_end(); ++e)
      if ( is_forward_edge(PI[i],e) ) {
        Segments.push_back(segment(PI[i],e));
        From[--Segments.end()] = Seg_info(e,i);
      }
  }


  typedef PMO_from_pm<Self,Seg_iterator,Seg_info> Output_from_plane_maps;
  typedef Segment_overlay_traits<
    Seg_iterator, Output_from_plane_maps, Geometry> pm_overlay;
  typedef generic_sweep< pm_overlay > pm_overlay_sweep;
  Output_from_plane_maps Out(*this,&PI[0],&PI[1],From);
  pm_overlay_sweep SOS(Seg_it_pair(Segments.begin(),Segments.end()),Out,K);
  SOS.sweep();
  create_face_objects(Out);


  CGAL_NEF_TRACEN("transfering marks");
  Face_iterator f = this->faces_begin(); assoc_info(f);
  for (i=0; i<2; ++i) mark(f,i) = PI[i].mark(PI[i].faces_begin());

  Vertex_iterator v, vend = this->vertices_end();
  for (v = this->vertices_begin(); v != vend; ++v) {
    CGAL_NEF_TRACEN("mark at "<<PV(v));
    Halfedge_handle e_below = halfedge_below(v);
    Mark m_below[2];
    if ( e_below != Halfedge_handle() ) {
      for (int i=0; i<2; ++i) {
        m_below[i] = incident_mark(e_below,i); 
      }
    } else { // e_below does not exist
      for (int i=0; i<2; ++i) 
        m_below[i] = PI[i].mark(PI[i].faces_begin());
    }

    for (i=0; i<2; ++i) 
      if ( supp_halfedge(v,i) != Halfedge_const_handle() ) {
        mark(v,i) = PI[i].mark(supp_halfedge(v,i));
      } else if ( supp_vertex(v,i) != Vertex_const_handle() ) {
        mark(v,i) = PI[i].mark(supp_vertex(v,i));
      } else {
        mark(v,i) = m_below[i];
      }

    if ( is_isolated(v) ) continue;
    Halfedge_around_vertex_circulator 
      e(first_out_edge(v)), hend(e);
    CGAL_For_all(e,hend) {
      if ( is_forward(e) ) {
        CGAL_NEF_TRACEN("   halfedge "<<PE(e));
        Halfedge_const_handle ei;
        bool supported;
        for (int i=0; i<2; ++i) {
          supported = ( supp_halfedge(e,i) != Halfedge_const_handle() );
          if ( supported ) {
            ei = supp_halfedge(e,i);
            CGAL_NEF_TRACEN("   supp halfedge "<<i<<" "<<PE(ei));
            incident_mark(twin(e),i) = 
              PI[i].mark(PI[i].face(PI[i].twin(ei)));
            mark(e,i) = PI[i].mark(ei);
            incident_mark(e,i) = m_below[i] =
              PI[i].mark(PI[i].face(ei));
          } else { // no support from input PI[i]
            incident_mark(twin(e),i) = mark(e,i) = incident_mark(e,i) = 
              m_below[i];
          }
        }
      } else break;
    }

  }
  for (f = ++this->faces_begin(); f != this->faces_end(); ++f) { // skip first face
    assoc_info(f);
    for (i=0; i<2; ++i) mark(f,i) = incident_mark(halfedge(f),i);
  }


}



template <typename Selection>
void select(Selection& predicate) const
/*{\Mop sets the marks of all objects according to the selection
predicate |predicate|. |Selection| has to be a function object type
with a function operator\\ [[Mark operator()(Mark m0, Mark m1)]]\\ For
each object |u| of |P| enriched by the marks of the supporting objects
according to the previous procedure |subdivide|, after this operation
|\Mvar.mark(u) = predicate ( \Mvar.mark(u,0),\Mvar.mark(u,1) )|. The
additional marks are invalidated afterwards. }*/
{ 
  Vertex_iterator vit = this->vertices_begin(),
                  vend = this->vertices_end();
  for( ; vit != vend; ++vit) {
    mark(vit) = predicate(mark(vit,0),mark(vit,1));
    discard_info(vit); 
  }
  Halfedge_iterator hit = this->halfedges_begin(),
                    hend = this->halfedges_end();
  for(; hit != hend; ++(++hit)) {
    mark(hit) = predicate(mark(hit,0),mark(hit,1));
    discard_info(hit);
  }
  Face_iterator fit = this->faces_begin(),
                fend = this->faces_end();
  for(; fit != fend; ++fit) {
    mark(fit) = predicate(mark(fit,0),mark(fit,1));
    discard_info(fit);
  }
}


template <typename Keep_edge>
void simplify(const Keep_edge& keep) const
/*{\Mop simplifies the structure of |P| according to the marks of
its objects. An edge |e| separating two faces |f1| and |f2| and equal
marks |mark(e) == mark(f1) == mark(f2)| is removed and the faces are
unified.  An isolated vertex |v| in a face |f| with |mark(v)==mark(f)|
is removed.  A vertex |v| with outdegree two, two collinear out-edges
|e1|,|e2| and equal marks |mark(v) == mark(e1) == mark(e2)| is removed
and the edges are unified. The data accessor |keep| requires the function
call operator\\[[bool operator()(Halfedge_handle e)]]\\that allows to
avoid the simplification for edge pairs referenced by |e|.}*/
{
  CGAL_NEF_TRACEN("simplifying"); 
  typedef typename CGAL::Union_find<Face_handle>::handle Union_find_handle;
  CGAL::Unique_hash_map< Face_iterator, Union_find_handle> Pitem;
  CGAL::Union_find<Face_handle> unify_faces;

  Face_iterator f, fend = this->faces_end();
  for (f = this->faces_begin(); f!= fend; ++f) { 
     Pitem[f] = unify_faces.make_set(f);
     clear_face_cycle_entries(f);
  }


  Halfedge_iterator e = this->halfedges_begin(), en,
                    eend = this->halfedges_end();
  for(; en=e, ++(++en), e != eend; e=en) { 
    if ( keep(e) ) continue;
    if ( mark(e) == mark(face(e)) &&
         mark(e) == mark(face(twin(e))) ) {
        CGAL_NEF_TRACEN("deleting "<<PE(e));
      if ( !unify_faces.same_set(Pitem[face(e)],
                                 Pitem[face(twin(e))]) ) {
        unify_faces.unify_sets( Pitem[face(e)],
                                Pitem[face(twin(e))] );
        CGAL_NEF_TRACEN("unioning disjoint faces");
      }
      if ( is_closed_at_source(e) )       set_face(source(e),face(e));
      if ( is_closed_at_source(twin(e)) ) set_face(target(e),face(e));
      delete_halfedge_pair(e);
    }
  }
  
  CGAL::Unique_hash_map<Halfedge_handle,bool> linked(false);
  for (e = this->halfedges_begin(); e != eend; ++e) {
    if ( linked[e] ) continue;
    Halfedge_around_face_circulator hfc(e),hend(hfc);
    Halfedge_handle e_min = e;
    Face_handle f = *(unify_faces.find(Pitem[face(e)]));
    CGAL_For_all(hfc,hend) {
      set_face(hfc,f);
      if(target(hfc) == target(e_min)) {
	Point p1 = point(source(hfc)), 
          p2 = point(target(hfc)), 
          p3 = point(target(next(hfc)));
	if (!K.left_turn(p1,p2,p3) )
	  e_min = hfc;
      } else if ( K.compare_xy(point(target(hfc)), point(target(e_min))) < 0 )
        e_min = hfc;
      linked[hfc]=true;
    }
    Point p1 = point(source(e_min)),
          p2 = point(target(e_min)),
          p3 = point(target(next(e_min)));
    if ( K.orientation(p1,p2,p3) > 0 ) set_halfedge(f,e_min); // outer
    else set_hole(f,e_min); // store as inner
  }


  Vertex_iterator v, vn, vend = this->vertices_end();
  for(v = this->vertices_begin(); v != vend; v=vn) { CGAL_NEF_TRACEN("at vertex "<<PV(v));
    vn=v; ++vn;