pm_decorator.h

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

}

Face_handle new_face(const Face_base& fb = Face_base()) const
/*{\Mop creates a new face.}*/
{ Face_handle f = this->phds->faces_push_back(fb);
  return f;
}

 
void link_as_outer_face_cycle(Face_handle f, Halfedge_handle e) const
/*{\Mop makes |e| the entry point of the outer face cycle of |f| and
makes |f| the face of all halfedges in the face cycle of |e|.}*/
{
  Halfedge_around_face_circulator hfc(e), hend(hfc);
  CGAL_For_all(hfc,hend) hfc->set_face(f);
  f->set_halfedge(e);
} 

void link_as_hole(Face_handle f, Halfedge_handle e) const
/*{\Mop makes |e| the entry point of a hole face cycle of |f| and
    makes |f| the face of all halfedges in the face cycle of |e|.}*/
{
  Halfedge_around_face_circulator hfc(e), hend(hfc);
  CGAL_For_all(hfc,hend) hfc->set_face(f);
  f->store_fc(e);
} 

void link_as_isolated_vertex(Face_handle f, Vertex_handle v) const
/*{\Mop makes |v| an isolated vertex within |f|.}*/
{  f->store_iv(v); v->set_face(f); } 

void clear_face_cycle_entries(Face_handle f) const
/*{\Mop removes all isolated vertices and halfedges that
are entrie points into face cycles from the lists of |f|.}*/
{ f->clear_all_entries(); }


Halfedge_handle new_halfedge_pair(Vertex_handle v1, Vertex_handle v2,
                                  Halfedge_base hb = Halfedge_base()) const
/*{\Mop creates a new pair of edges |(e1,e2)| representing |(v1,v2)| 
  by appending the |ei| to |A(vi)| $(i=1,2)$.}*/
{ Halfedge_handle e1 = this->phds->edges_push_back(hb,hb);
  Halfedge_handle e2 = e1->opposite(); 
  e1->set_face(Face_handle()); e2->set_face(Face_handle());
  if ( ! is_isolated(v1) ) 
    set_adjacency_at_source_between(cap(first_out_edge(v1)),e1,
                                    first_out_edge(v1));
  else
    close_tip_at_source(e1,v1);
  if ( ! is_isolated(v2) )
    set_adjacency_at_source_between(cap(first_out_edge(v2)),e2,
                                    first_out_edge(v2));
  else 
    close_tip_at_source(e2,v2);
  return e1;
}


Halfedge_handle new_halfedge_pair(Halfedge_handle e1, 
                                  Halfedge_handle e2,
                                  Halfedge_base hb = Halfedge_base(),
                                  int pos1 = AFTER, int pos2 = AFTER) const
/*{\Mop creates a new pair of edges |(h1,h2)| representing 
  |(source(e1),source(e2))| by inserting the |hi| before or after |ei| 
  into the cyclic adjacency list of |source(ei)| depending on 
  |posi| $(i=1,2)$ from |\Mname::BEFORE, \Mname::AFTER|.}*/
{ 
  Halfedge_handle er = this->phds->edges_push_back(hb,hb);
  Halfedge_handle ero = er->opposite();
  er->set_face(Face_handle()); ero->set_face(Face_handle()); 
  if (pos1 < 0) { // before e1
    set_adjacency_at_source_between(cap(e1),er,e1);
    if ( e1 == first_out_edge(source(e1)) )
      make_first_out_edge(er); // added 22/8/00
  } else { // after e1
    set_adjacency_at_source_between(e1,er,cas(e1));
  }
  if (pos2 < 0) { // before e2
    set_adjacency_at_source_between(cap(e2),ero,e2);
    if ( e2 == first_out_edge(source(e2)) )
      make_first_out_edge(ero);
  } else { // after e2
    set_adjacency_at_source_between(e2,ero,cas(e2));
  }
  return er;
}

Halfedge_handle new_halfedge_pair(Halfedge_handle e, Vertex_handle v,
                                  Halfedge_base hb = Halfedge_base(),
                                  int pos = AFTER) const
/*{\Mop creates a new pair of edges  |(e1,e2)| representing |(source(e),v)| 
  by inserting |e1| before or after |e| into the cyclic adjacency list of
  |source(e)| depending on |pos| from |\Mname::BEFORE, \Mname::AFTER|
  and appending |e2| to |A(v)|.}*/
{
  Halfedge_handle e_new = this->phds->edges_push_back(hb,hb);
  Halfedge_handle e_opp = e_new->opposite();
  e_new->set_face(Face_handle()); e_opp->set_face(Face_handle()); 

  if (pos < 0) { // before e
    set_adjacency_at_source_between(cap(e),e_new,e);
    if ( e == first_out_edge(source(e)) )
      make_first_out_edge(e_new);
  } else  // after e
    set_adjacency_at_source_between(e,e_new,cas(e));
  
  if ( ! is_isolated(v) ) {
    Halfedge_handle e_first = first_out_edge(v);
    set_adjacency_at_source_between(cap(e_first),e_opp,e_first);
  } else
    close_tip_at_source(e_opp,v);

  return e_new;
}


Halfedge_handle new_halfedge_pair(Vertex_handle v, Halfedge_handle e,
                                  Halfedge_base hb = Halfedge_base(),
                                  int pos = AFTER) const
/*{\Mop symmetric to the previous one.}*/
{ return new_halfedge_pair(e,v,hb,pos)->opposite(); }




void delete_halfedge_pair(Halfedge_handle e) const
/*{\Mop deletes |e| and its twin and updates the adjacency at its source 
        and its target.}*/
{ remove_from_adj_list_at_source(e);
  remove_from_adj_list_at_source(e->opposite());
  this->phds->edges_erase(e);
}

void delete_vertex(Vertex_handle v) const
/*{\Mop deletes |v| and all outgoing edges |A(v)| as well as their twins. 
        Updates the adjacency at the targets of the edges in |A(v)|.}*/
{ 
  if ( ! is_isolated(v) ) {
    Halfedge_handle e = first_out_edge(v);
    while ( e != cap(e) ) 
      delete_halfedge_pair(cap(e));  
    delete_halfedge_pair(e); 
  }
  this->phds->vertices_erase(v);
}

void delete_face(Face_handle f) const
/*{\Mop deletes the face |f| without consideration of topological linkage.}*/
{ this->phds->faces_erase(f); }


bool has_outdeg_two(Vertex_handle v) const
/*{\Mop return true when |v| has outdegree two.}*/
{ if (v->is_isolated()) return false;
  Halfedge_handle e1 = v->halfedge();
  Halfedge_handle e2 = e1->next()->opposite();
  return (e1!=e2 && e2->next()->opposite()==e1);
}

void merge_halfedge_pairs_at_target(Halfedge_handle e) const
/*{\Mop merges the halfedge pairs at |v = target(e)|. |e| and
  |twin(e)| are preserved, |next(e)|, |twin(next(e))| and |v| are deleted
  in the merger. \precond |v| has outdegree two. The adjacency at |source(e)|
  and |target(next(e))| is kept consistent.}*/
{
  CGAL_NEF_TRACEN("merge_halfedge_pairs_at_target "<<PE(e));
  Halfedge_handle eo = e->opposite(), 
                  en = e->next(), eno = en->opposite(),
                  enn = en->next(), enno = eno->prev();
  Vertex_handle v = e->vertex(), vn = en->vertex();
  CGAL_assertion(has_outdeg_two(v));
  Face_handle f1 = en->face(), f2 = eno->face();
  // transfer the opposite face cycles e-en-enn to e-enn
  if ( enn != eno ) {
    e->set_next(enn); enn->set_prev(e);
    eo->set_prev(enno); enno->set_next(eo);
  } else {
    e->set_next(eo); eo->set_prev(e);
  }
  // set vertex of e and deal with vertex-halfedge incidence
  e->set_vertex(vn); 
  if (vn->halfedge()==en) vn->set_halfedge(e);
  if (en->is_hole_entry()) 
  { f1->remove_fc(en); f1->store_fc(e); }
  if (eno->is_hole_entry()) 
  { f2->remove_fc(eno); f2->store_fc(eo); }
  if (f1->halfedge() == en) f1->set_halfedge(e);
  if (f2->halfedge() == eno) f2->set_halfedge(eo);
  this->phds->vertices_erase(v);
  this->phds->edges_erase(en);
}

void flip_diagonal(Halfedge_handle e) const
{ Halfedge_handle r = twin(e);
  Halfedge_handle en = e->next(), enn= en->next();
  Halfedge_handle rn = r->next(), rnn= rn->next();
  CGAL_assertion( enn->next()==e && rnn->next()==r );
  remove_from_adj_list_at_source(e);
  remove_from_adj_list_at_source(r);
  set_adjacency_at_source_between(enn,e,twin(en));
  set_adjacency_at_source_between(rnn,r,twin(rn));
}


/*{\Mtext \headerline{Incomplete topological update primitives}}*/

Halfedge_handle new_halfedge_pair_at_source
  (Halfedge_handle e, int pos = AFTER, Halfedge_base hb = 
   Halfedge_base()) const
/*{\Xop creates a new pair of edges  |(e1,e2)| representing |(source(e),())| 
  by inserting |e1| before or after |e| into cyclic adjacency list of
  |source(e)| depending on |pos| from |\Mname::BEFORE, \Mname::AFTER|.}*/
{
  Halfedge_handle e_new = this->phds->edges_push_back(hb,hb);
  if (pos < 0) // before e
    set_adjacency_at_source_between(cap(e),e_new,e);
  else  // after e
    set_adjacency_at_source_between(e,e_new,cas(e));
  return e_new;
}

Halfedge_handle new_halfedge_pair_at_source
  (Vertex_handle v, int pos = AFTER, Halfedge_base hb = Halfedge_base()) const
/*{\Mop creates a new pair of edges  |(e1,e2)| representing |(v,())| 
  by inserting |e1| at the beginning (BEFORE) or end (AFTER)
  of adjacency list of |v|.}*/
{ Halfedge_handle e1 = this->phds->edges_push_back(hb,hb);
  Halfedge_handle e2 = e1->opposite(); 
  e1->set_face(Face_handle()); e2->set_face(Face_handle());
  if ( ! is_isolated(v) ) {
    Halfedge_handle ef = first_out_edge(v);
    set_adjacency_at_source_between(cap(ef),e1,ef);
    if ( pos == BEFORE ) v->set_halfedge(e2);
  } else
    close_tip_at_source(e1,v);
  return e1;
}

void delete_halfedge_pair_at_source(Halfedge_handle e) const
/*{\Mop deletes |e| and its twin and updates the adjacency at its 
  source.}*/
{ remove_from_adj_list_at_source(e);
  this->phds->edges_erase(e);
}

void link_as_target_and_append(Vertex_handle v, Halfedge_handle e) const
/*{\Mop makes |v| the target of |e| and appends |twin(e)| to $A(v)$.}*/
{ if ( ! is_isolated(v) ) 
    set_adjacency_at_source_between(cap(first_out_edge(v)),twin(e),
      first_out_edge(v));
  else
    close_tip_at_target(e,v);
}

Halfedge_handle new_halfedge_pair_without_vertices() const
/*{\Mop inserts an open edge pair, and inits all link slots to their default 
    handles.}*/
{
  Halfedge_handle e_new = this->phds->edges_push_back(Halfedge(),Halfedge());
  return e_new;
}

void delete_vertex_only(Vertex_handle v) const
/*{\Mop deletes |v| without consideration of adjacency.}*/
{ this->phds->vertices_erase(v); }

void delete_halfedge_pair_only(Halfedge_handle e) const
/*{\Mop deletes |e| and its twin without consideration of adjacency.}*/
{ this->phds->edges_erase(e); }

void link_as_target_of(Halfedge_handle e, Vertex_handle v) const
/*{\Mop makes |target(e) = v| and sets |e| as the first
        in-edge if |v| was isolated before.}*/
{ e->set_vertex(v);
  if (v->halfedge() == Halfedge_handle()) v->set_halfedge(e); }

void link_as_source_of(Halfedge_handle e, Vertex_handle v) const
/*{\Mop makes |source(e) = v| and sets |e| as the first
        out-edge if |v| was isolated before.}*/
{ link_as_target_of(e->opposite(),v); }

void make_first_out_edge(Halfedge_handle e) const
/*{\Mop makes |e| the first outgoing halfedge in the cyclic adjacency
    list of |source(e)|.}*/ 
{ source(e)->set_halfedge(e->opposite()); }


void set_adjacency_at_source_between(Halfedge_handle e, Halfedge_handle en) 
  const 
/*{\Mop makes |e| and |en| neigbors in the cyclic ordered adjacency list 
  around |v=source(e)|. \precond |source(e)==source(en)|.}*/
{ CGAL_assertion(source(e)==source(en));
  link_as_prev_next_pair(en->opposite(),e);
}

void set_adjacency_at_source_between(Halfedge_handle e1, 
                                     Halfedge_handle e_between, 
                                     Halfedge_handle e2) const 
/*{\Mop inserts |e_between| into the adjacency list around |source(e1)| 
  between |e1| and |e2| and makes |source(e1)| the source of |e_between|. 
  \precond |source(e1)==source(e2)|.}*/
{ e_between->opposite()->set_vertex(source(e1));
  set_adjacency_at_source_between(e1,e_between);
  set_adjacency_at_source_between(e_between,e2);
}

void close_tip_at_target(Halfedge_handle e, Vertex_handle v) const 
/*{\Mop sets |v| as target of |e| and closes the tip by setting the 
  corresponding pointers such that |prev(twin(e)) == e| and 
  |next(e) == twin(e)|.}*/
{ link_as_target_of(e,v);
  link_as_prev_next_pair(e,e->opposite()); }

void close_tip_at_source(Halfedge_handle e, Vertex_handle v) const 
/*{\Mop sets |v| as source of |e| and closes the tip by setting the 
  corresponding pointers such that |prev(e) == twin(e)| and
  |next(twin(e)) == e|.}*/
{ close_tip_at_target(e->opposite(),v); }


void remove_from_adj_list_at_source(Halfedge_handle e) const
/*{\Mop removes a halfedge pair |(e,twin(e)| from the adjacency list
        of |source(e)|. Afterwards |next(prev(e))==next(twin(e))|