sm_decorator.h

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

void delete_edge_pair_only(SHalfedge_handle e)
/*{\Mop deletes |e| and its twin without any connectivity update.}*/
{ map()->delete_shalfedge_pair(e); }

void delete_halfedge_only(SHalfedge_handle e)
/*{\Mop deletes |e| without its twin and without any connectivity update.}*/
{ map()->delete_shalfedge(e); }

void delete_face_only(SFace_handle f) 
/*{\Mop deletes |f| without any connectivity update.}*/
{ map()->delete_sface(f); }

void delete_loop_only()
/*{\Mop deletes the loop and its twin without any connectivity update.}*/ 
{ map()->delete_shalfloop_pair(); }

template <typename H>
bool is_sm_boundary_object(H h) const
{ return map()->is_sm_boundary_object(h); }

template <typename H>
void store_sm_boundary_object(H h, SFace_handle f) {
  CGAL_assertion(!map()->is_sm_boundary_object(h));
  f->boundary_entry_objects().push_back(Object_handle(h));
  map()->store_sm_boundary_item(h, --(f->sface_cycles_end()));
}

template <typename H>
void undo_sm_boundary_object(H h, SFace_handle f)
{ CGAL_assertion(map()->is_sm_boundary_object(h));
  SFace_cycle_iterator it = map()->sm_boundary_item(h);
  map()->undef_sm_boundary_item(h);
  f->boundary_entry_objects().erase(it);
}

void link_as_face_cycle(SHalfedge_handle e, SFace_handle f)
/*{\Mop creates a new face cycle of |f| and 
   makes |e| the entry point of it.}*/
{
  SHalfedge_around_sface_circulator hfc(e), hend(hfc);
  CGAL_For_all(hfc,hend) hfc->incident_sface() = f;
  store_sm_boundary_object(e,f);
} 

void link_as_loop(SHalfloop_handle l, SFace_handle f)
/*{\Mop creates a new trivial face cycle of |f| and 
   makes |l| the singular object of it.}*/
{ store_sm_boundary_object(l,f); l->incident_sface() = f; } 

void link_as_isolated_vertex(SVertex_handle v, SFace_handle f)
/*{\Mop creates a new trivial face cycle of |f|.
   (makes |v| an isolated vertex within |f|).}*/
{ store_sm_boundary_object(v,f); v->incident_sface() = f; } 

void unlink_as_face_cycle(SHalfedge_handle e)
/*{\Mop removes the face cycle defined by |e| from |face(e)|.
    Does not update the face links of the corresponding face cycle
    edges. \precond |e| is the entry object of the face cycle.}*/
{ undo_sm_boundary_object(e,face(e)); }
  
void unlink_as_loop(SHalfloop_handle l)
/*{\Mop removes the trivial face cycle defined by |l| from
   |face(l)|. Does not update |l|'s face link.}*/
{ undo_sm_boundary_object(l,face(l)); }

void unlink_as_isolated_vertex(SVertex_handle v)
/*{\Mop removes the trivial face cycle defined by |v| from
   |face(v)|. Does not update |v|'s face link.
   \precond |v| is a trivial face cycle of |face(v)|.}*/
{ undo_sm_boundary_object(v,face(v)); }

void clear_face_cycle_entries(SFace_handle f)
{ map()->reset_sm_object_list(f->boundary_entry_objects());
  // removes entries of list and the hashed membership
}

SHalfedge_handle new_shalfedge_pair(SVertex_handle v1,
			            SVertex_handle v2)
/*{\Mop creates a new pair of edges |(e1,e2)| representing |(v1,v2)| 
  by appending the |ei| to |A(vi)| $(i=1,2)$.}*/
{ SHalfedge_handle e1 = new_shalfedge_pair();
  SHalfedge_handle e2 = twin(e1);
  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;
}


SHalfedge_handle new_shalfedge_pair(SHalfedge_handle e1, 
			            SHalfedge_handle e2,
			            int pos1 = AFTER, int pos2 = AFTER)
/*{\Mop creates a new pair of edges |(es1,es2)| representing the uedge
  |\{source(e1),source(e2)\}| by inserting the |esi| before or after |ei| 
  into the cyclic adjacency list of |source(ei)| depending on |posi| 
  $(i=1,2)$ from |\Mname::BEFORE|, |\Mname::AFTER|.}*/
{ 
  SHalfedge_handle er = new_shalfedge_pair();
  SHalfedge_handle ero = twin(er);
  if (pos1 < 0) { // before e1
    set_adjacency_at_source_between(cap(e1),er,e1);
    if ( e1 == first_out_edge(source(e1)) )
      set_first_out_edge(source(e1),er);
  } 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)) )
      set_first_out_edge(source(e2),ero);
  } else { // after e2
    set_adjacency_at_source_between(e2,ero,cas(e2));
  }
  return er;
}

SHalfedge_handle new_shalfedge_pair(SHalfedge_handle e, SVertex_handle v,
                               int pos = AFTER)
/*{\Mop creates a new pair of edges  |(e1,e2)| representing the uedge
  |\{source(e),v\}| by inserting |e1| before or after |e| into cyclic 
  adjacency list of |source(e)| depending on |pos| from |\Mname::BEFORE|,
  |\Mname::AFTER| and appending |e2| at |A(v)|.}*/
{
  SHalfedge_handle e_new = new_shalfedge_pair();
  SHalfedge_handle e_opp = twin(e_new);
  if (pos < 0) { // before e
    set_adjacency_at_source_between(cap(e),e_new,e);
    if ( e == first_out_edge(source(e)) )
      set_first_out_edge(source(e),e_new);
  } else  // after e
    set_adjacency_at_source_between(e,e_new,cas(e));
  
  if (!is_isolated(v)) {
    SHalfedge_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;
}


SHalfedge_handle new_shalfedge_pair(SVertex_handle v, SHalfedge_handle e,
                                    int pos = AFTER)
/*{\Mop symmetric to the previous one.}*/
{ return twin(new_shalfedge_pair(e,v,pos)); }

void delete_edge_pair(SHalfedge_handle e)
/*{\Mop deletes |e| and its twin and maintains the adjacency at its source 
        and its target.}*/
{ remove_from_adj_list_at_source(e);
  remove_from_adj_list_at_source(twin(e));
  delete_edge_pair_only(e);
}

void delete_vertex(SVertex_handle v)
/*{\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)) {
    SHalfedge_handle e = first_out_edge(v);
    while ( e != cap(e) ) 
      delete_edge_pair(cap(e));  
    delete_edge_pair(e); 
  }
  delete_vertex_only(v);
}

void delete_face(SFace_handle f)
/*{\Mop deletes the face |f| without consideration of topological 
   linkage.}*/
{ clear_face_cycle_entries(f); delete_face_only(f); }

bool has_outdeg_two(SVertex_handle v) const
/*{\Mop return true when |v| has outdegree two.}*/
// does this work for looping edges?
{ if (is_isolated(v)) return false;
  SHalfedge_handle e1 = first_out_edge(v);
  SHalfedge_handle e2 = last_out_edge(v);
  return (e1!=e2 && e2==cas(e1));
}

void link_as_prev_next_pair(SHalfedge_handle e1, SHalfedge_handle e2)
/*{\Xop makes |e1| and |e2| adjacent in the face cycle 
   $\ldots-|e1-e2|-\ldots$.
   Afterwards |e1 = previous(e2)| and |e2 = next(e1)|.}*/
{ e1->snext() = e2; e2->sprev() = e1; }

void merge_edge_pairs_at_target(SHalfedge_handle e)
/*{\Mop merges the edge 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.
  If |next(e)| was entry point of |face(e)| then |e| takes this role.
  The same holds for |twin(next(e))| and |face(twin(e))|.}*/
{
  CGAL_NEF_TRACEN("merge_edge_pairs_at_target "<<PH(e));
  SHalfedge_handle en = next(e), eno = twin(en), enn, enno,
               eo = twin(e) ;
  if ( is_closed_at_target(en) ) { enn = eo; enno=e; }
  else { enn = next(en), enno = previous(eno); }
  SVertex_handle v = target(e), vn = target(en);
  CGAL_assertion(has_outdeg_two(v));
  SFace_handle f1 = face(en), f2 = face(eno);
  // transfer the opposite face cycles e-en-enn to e-enn
  if ( enn != eno ) {
    link_as_prev_next_pair(e,enn);
    link_as_prev_next_pair(enno,eo);
  } else {
    link_as_prev_next_pair(e,eo);
  }
  // set vertex of e and deal with vertex-halfedge incidence
  eo->source() = vn;

  if ( first_out_edge(vn) == eno ) set_first_out_edge(vn,eo);
  if ( is_sm_boundary_object(en) )
  { undo_sm_boundary_object(en,f1); store_sm_boundary_object(e,f1); }
  if ( is_sm_boundary_object(eno) )
  { undo_sm_boundary_object(eno,f2); store_sm_boundary_object(eo,f2); }
  delete_vertex_only(v);
  delete_edge_pair_only(en);
  CGAL_NEF_TRACEN("END "<<PH(previous(e))<<PH(e)<<PH(next(e)));
}

void convert_edge_to_loop(SHalfedge_handle e)
/*{\Mop converts the edge at |v = target(e)| to the unique
  loop |l| of |\Mvar|. |e|, |twin(e)| and |v| are deleted
  in the conversion. \precond there was no loop in |\Mvar|.
  As |e| was entry point of |face(e)| then |l| takes this role.}*/
{ CGAL_NEF_TRACEN("convert_edge_to_loop "<<PH(e));
  CGAL_assertion( source(e)==target(e) );
  CGAL_assertion( !has_shalfloop() );
  SHalfloop_handle l = new_shalfloop_pair();
  SVertex_handle v = target(e);
  SFace_handle f1 = face(e), f2 = face(twin(e));
  if( is_sm_boundary_object(e)) {
    CGAL_assertion( is_sm_boundary_object(twin(e)));
    undo_sm_boundary_object(e,f1); undo_sm_boundary_object(twin(e),f2);
  }
  link_as_loop(l,f1), link_as_loop(twin(l),f2);
  circle(l) = circle(e); circle(twin(l)) = circle(twin(e));
  mark(l) = mark(twin(l)) = mark(e);
  delete_vertex_only(v);
  delete_edge_pair_only(e);
}

void flip_diagonal(SHalfedge_handle e)
{ SHalfedge_handle r = twin(e);
  SHalfedge_handle en = next(e), enn= next(en);
  SHalfedge_handle rn = next(r), rnn= next(rn);
  CGAL_NEF_TRACEN(PH(e)<<PH(en)<<PH(enn));
  CGAL_NEF_TRACEN(PH(r)<<PH(rn)<<PH(rnn));
  CGAL_assertion( next(enn)==e && next(rnn)==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}}*/

SHalfedge_handle new_shalfedge_pair_at_source
  (SHalfedge_handle e, int pos = AFTER) 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|.}*/
{ SHalfedge_handle e_new = new_shalfedge_pair();
  if (pos < 0) set_adjacency_at_source_between(cap(e),e_new,e);
  else         set_adjacency_at_source_between(e,e_new,cas(e));
  return e_new;
}

SHalfedge_handle new_shalfedge_pair_at_source
  (SVertex_handle v, int pos = AFTER)
/*{\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|.}*/
{ SHalfedge_handle e1 = new_shalfedge_pair();
  if (!is_isolated(v)) {
    SHalfedge_handle ef = first_out_edge(v);
    if (pos < 0) { // before e1
      set_adjacency_at_source_between(cap(ef),e1,ef);
      set_first_out_edge(v,e1);
    } else {
      set_adjacency_at_source_between(ef,e1,cas(ef));
    }
  } else
    close_tip_at_source(e1,v);
  return e1;
}

void delete_edge_pair_at_source(SHalfedge_handle e) const
/*{\Mop deletes |e| and its twin and maintains the adjacency at its 
  source.}*/
{ remove_from_adj_list_at_source(e);
  delete_edge_pair_only(e);
}

void link_as_target_and_append(SVertex_handle v, SHalfedge_handle e)
/*{\Mop makes |v| the target of |e| appends |twin(e)| to the adjacency list
   of |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);
}

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

void link_as_target_of(SHalfedge_handle e, SVertex_handle v) const
/*{\Mop makes |target(e) = v| and sets |e| as the first
  in edge if |v| was isolated before.}*/
{ link_as_source_of(twin(e),v); }

void set_adjacency_at_source_between(SHalfedge_handle e, SHalfedge_handle en)
/*{\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(twin(en),e);
}

void set_adjacency_at_source_between(SHalfedge_handle e1, 
                                     SHalfedge_handle e_between, 
                                     SHalfedge_handle e2)
/*{\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->source() = source(e1);
  set_adjacency_at_source_between(e1,e_between);
  set_adjacency_at_source_between(e_between,e2);