pm_overlayer.h

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

    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(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;
      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>
void create_face_objects_pl(const Below_info& D) const
{
  CGAL_NEF_TRACEN("create_face_objects_pl()");
  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(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;
      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");
      Halfedge_around_face_circulator hfc(e),hend(hfc);
      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);
  }
}

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