pm_overlayer.h

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

  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 ( 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;
    if ( is_isolated(v) ) {
      if ( mark(v) == mark(face(v)) ) delete_vertex_only(v);
      else set_isolated_vertex(face(v),v); 
    } else { // v not isolated
      Halfedge_handle e2 = first_out_edge(v), e1 = previous(e2);
      Point p1 = point(source(e1)), p2 = point(v), 
            p3 = point(target(e2));
      if ( has_outdeg_two(v) &&
           mark(v) == mark(e1) && mark(v) == mark(e2) &&
           (K.orientation(p1,p2,p3) == 0) ) 
        merge_halfedge_pairs_at_target(e1); 
    }
  }

  Face_iterator fn;
  for (f = this->faces_begin(); f != fend; f=fn) {
    fn=f; ++fn;
    Union_find_handle pit = Pitem[f];
    if ( unify_faces.find(pit) != pit ) delete_face(f);
  }


}

struct vertex_info {
  Mark                  m[2];
  Vertex_const_handle   v_supp[2];
  Halfedge_const_handle e_supp[2];
  Halfedge_handle       e_below;
  vertex_info() 
  { v_supp[0]=v_supp[1]=Vertex_const_handle(); 
    e_supp[0]=e_supp[1]=Halfedge_const_handle(); }
  LEDA_MEMORY(vertex_info)
};

void assoc_info(Vertex_handle v) const
{ geninfo<vertex_info>::create(info(v)); }

void discard_info(Vertex_handle v) const
{ geninfo<vertex_info>::clear(info(v)); }

vertex_info& ginfo(Vertex_handle v) const
{ return geninfo<vertex_info>::access(info(v)); }

Mark& mark(Vertex_handle v, int i) const
{ return ginfo(v).m[i]; }

Vertex_const_handle& supp_vertex(Vertex_handle v, int i) const
{ return ginfo(v).v_supp[i]; }

Halfedge_const_handle& supp_halfedge(Vertex_handle v, int i) const
{ return ginfo(v).e_supp[i]; }

Halfedge_handle& halfedge_below(Vertex_handle v) const
{ return ginfo(v).e_below; }

struct halfedge_info {
  Mark                  m[2];
  Mark                  mf[2];
  Halfedge_const_handle e_supp[2];
  bool                  forw;
  halfedge_info()
  { m[0]=m[1]=mf[0]=mf[1]=Mark(); 
    e_supp[0]=e_supp[1]=Halfedge_const_handle(); 
    forw=false; }
  LEDA_MEMORY(halfedge_info)
};

void assoc_info(Halfedge_handle e)  const
{ geninfo<halfedge_info>::create(info(e)); 
  geninfo<halfedge_info>::create(info(twin(e))); }

void discard_info(Halfedge_handle e)  const
{ geninfo<halfedge_info>::clear(info(e)); 
  geninfo<halfedge_info>::clear(info(twin(e))); }

halfedge_info& ginfo(Halfedge_handle e)  const
{ return geninfo<halfedge_info>::access(info(e)); }

Mark& mark(Halfedge_handle e, int i)  const
// uedge information we store in the smaller one 
{ if (&*e < &*(twin(e))) return ginfo(e).m[i]; 
  else                   return ginfo(twin(e)).m[i]; }

Halfedge_const_handle& supp_halfedge(Halfedge_handle e, int i) const
// uedge information we store in the smaller one 
{ if (&*e < &*(twin(e))) return ginfo(e).e_supp[i]; 
  else                   return ginfo(twin(e)).e_supp[i]; }

Mark& incident_mark(Halfedge_handle e, int i)  const
// biedge information we store in the halfedge
{ return ginfo(e).mf[i]; }

bool& is_forward(Halfedge_handle e) const
// biedge information we store in the halfedge
{ return ginfo(e).forw; }

struct face_info {
  Mark m[2];
  face_info() { m[0]=m[1]=Mark(); }
  LEDA_MEMORY(face_info)
};

void assoc_info(Face_handle f)  const
{ geninfo<face_info>::create(info(f)); }

void discard_info(Face_handle f)  const
{ geninfo<face_info>::clear(info(f)); }

face_info& ginfo(Face_handle f)  const
{ return geninfo<face_info>::access(info(f)); }

Mark& mark(Face_handle f, int i)  const
{ return ginfo(f).m[i]; }

void clear_associated_info_of_all_objects() const 
{
  Vertex_iterator vit;
  for (vit = this->vertices_begin(); vit != this->vertices_end(); ++vit)
    discard_info(vit);
  Halfedge_iterator hit;
  for (hit = this->halfedges_begin(); hit != this->halfedges_end(); ++hit) 
    discard_info(hit);
  Face_iterator fit;
  for (fit = this->faces_begin(); fit != this->faces_end(); ++fit) 
    discard_info(fit);
}

template <typename Below_info>
void create_face_objects(const Below_info& D) const
{
  CGAL_NEF_TRACEN("create_face_objects()");
  CGAL::Unique_hash_map<Halfedge_handle,int> FaceCycle(-1);
  std::vector<Halfedge_handle>  MinimalHalfedge;
  int i=0;
  Halfedge_iterator e, eend = this->halfedges_end();
  for (e=this->halfedges_begin(); e != eend; ++e) {
    if ( FaceCycle[e] >= 0 ) continue; // already assigned
    Halfedge_around_face_circulator hfc(e),hend(hfc);
    Halfedge_handle e_min = e;
    CGAL_NEF_TRACE("face cycle "<<i<<"\n");
    CGAL_For_all(hfc,hend) {
      FaceCycle[hfc]=i; // assign face cycle number
      if ( K.compare_xy(point(target(hfc)), point(target(e_min))) < 0 )
        e_min = hfc;
      CGAL_NEF_TRACE(PE(hfc));
    } 
    CGAL_NEF_TRACEN("");
    MinimalHalfedge.push_back(e_min); ++i;
  }

  Face_handle f_outer = this->new_face();
  for (int j=0; j<i; ++j) {
    Halfedge_handle e = MinimalHalfedge[j];
      CGAL_NEF_TRACEN("  face cycle "<<j);CGAL_NEF_TRACEN("  minimal halfedge "<<PE(e));
    Point p1 = point(source(e)), 
          p2 = point(target(e)), 
          p3 = point(target(next(e)));
    if ( K.left_turn(p1,p2,p3) ) { // left_turn => outer face cycle
        CGAL_NEF_TRACEN("  creating new face object");
      Face_handle f = this->new_face();
      link_as_outer_face_cycle(f,e);
    }
  }

  for (e = this->halfedges_begin(); e != eend; ++e) {
    if ( face(e) != Face_handle() ) continue;
    CGAL_NEF_TRACEN("linking hole "<<PE(e));
    Face_handle f = determine_face(e,MinimalHalfedge,FaceCycle,D);
    link_as_hole(f,e);
  }
  Vertex_iterator v, v_end = this->vertices_end();
  for (v = this->vertices_begin(); v != v_end; ++v) {
    if ( !is_isolated(v) ) continue;
    Halfedge_handle e_below = D.halfedge_below(v);
    if ( e_below == Halfedge_handle() ) 
      link_as_isolated_vertex(f_outer,v);
    else
      link_as_isolated_vertex(face(e_below),v);    
  }

}

template <typename Below_info>
Face_handle determine_face(Halfedge_handle e, 
  const std::vector<Halfedge_handle>& MinimalHalfedge,
  const CGAL::Unique_hash_map<Halfedge_handle,int>& FaceCycle,
  const Below_info& D) const
{ CGAL_NEF_TRACEN("determine_face "<<PE(e));
  Halfedge_handle e_min = MinimalHalfedge[FaceCycle[e]];
  Halfedge_handle e_below = D.halfedge_below(target(e_min));
  if ( e_below == Halfedge_handle() ) // below is nirwana
    return this->faces_begin();
  Face_handle f = face(e_below);
  if (f != Face_handle()) return f; // has face already
  f = determine_face(e_below, MinimalHalfedge, FaceCycle,D);
  link_as_hole(f,e_below);
  return f;
}

Segment segment(const Const_decorator& N, 
                Halfedge_const_handle e) const
{ return K.construct_segment(
    N.point(N.source(e)),N.point(N.target(e))); }

Segment segment(const Const_decorator& N, 
                Vertex_const_handle v) const
{ Point p = N.point(v); 
  return K.construct_segment(p,p); }

bool is_forward_edge(const Const_decorator& N, 
                     Halfedge_const_iterator hit) const
{ Point p1 = N.point(N.source(hit));
  Point p2 = N.point(N.target(hit));
  return (K.compare_xy(p1,p2) < 0); }

void assert_type_precondition() const
{ typename PM_decorator_::Point p1; Point p2;
  assert_equal_types(p1,p2); }



}; // PM_overlayer<PM_decorator_,Geometry_>



CGAL_END_NAMESPACE
#endif // CGAL_PM_OVERLAYER_H