sm_decorator.h

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

  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 |e->incident_sface()|.
    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,e->incident_sface()); }
  
void unlink_as_loop(SHalfloop_handle l)
/*{\Mop removes the trivial face cycle defined by |l| from
   |l->incident_sface()|. Does not update |l|'s face link.}*/
{ undo_sm_boundary_object(l,l->incident_sface()); }

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

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 = e1->twin();
  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
  |\{e1->source(),e2->source()\}| by inserting the |esi| before or after |ei| 
  into the cyclic adjacency list of |ei->source()| depending on |posi| 
  $(i=1,2)$ from |\Mname::BEFORE|, |\Mname::AFTER|.}*/
{ 
  SHalfedge_handle er = new_shalfedge_pair();
  SHalfedge_handle ero = er->twin();
  if (pos1 < 0) { // before e1
    set_adjacency_at_source_between(cap(e1),er,e1);
    if ( e1 == first_out_edge(e1->source()) )
      set_first_out_edge(e1->source(),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(e2->source()) )
      set_first_out_edge(e2->source(),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
  |\{e->source(),v\}| by inserting |e1| before or after |e| into cyclic 
  adjacency list of |e->source()| 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 = e_new->twin();
  if (pos < 0) { // before e
    set_adjacency_at_source_between(cap(e),e_new,e);
    if ( e == first_out_edge(e->source()) )
      set_first_out_edge(e->source(),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 new_shalfedge_pair(e,v,pos)->twin(); }

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(e->twin());
  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 = e2->sprev()| and |e2 = e1->snext()|.}*/
{ e1->snext() = e2; e2->sprev() = e1; }

void merge_edge_pairs_at_target(SHalfedge_handle e)
/*{\Mop merges the edge pairs at |v = e->target()|. |e| and |twin(e)| 
  are preserved, |e->snext()|, |twin(e->snext())| and |v| are deleted
  in the merger. \precond |v| has outdegree two. The adjacency at 
  |e->source()| and |target(e->snext())| is kept consistent.
  If |e->snext()| was entry point of |e->incident_sface()| then |e| takes this role.
  The same holds for |twin(e->snext())| and |face(twin(e))|.}*/
{
  CGAL_NEF_TRACEN("merge_edge_pairs_at_target "<<PH(e));
  SHalfedge_handle en = e->snext(), eno = en->twin(), enn, enno,
               eo = e->twin() ;
  if ( is_closed_at_target(en) ) { enn = eo; enno=e; }
  else { enn = en->snext(), enno = eno->sprev(); }
  SVertex_handle v = e->target(), vn = en->target();
  CGAL_assertion(has_outdeg_two(v));
  SFace_handle f1 = en->incident_sface(), f2 = eno->incident_sface();
  // 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(e->sprev())<<PH(e)<<PH(e->snext()));
}

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

void flip_diagonal(SHalfedge_handle e)
{ SHalfedge_handle r = e->twin();
  SHalfedge_handle en = e->snext(), enn= en->snext();
  SHalfedge_handle rn = r->snext(), rnn= rn->snext();
  CGAL_NEF_TRACEN(PH(e)<<PH(en)<<PH(enn));
  CGAL_NEF_TRACEN(PH(r)<<PH(rn)<<PH(rnn));
  CGAL_assertion( enn->snext()==e && rnn->snext()==r );
  remove_from_adj_list_at_source(e);
  remove_from_adj_list_at_source(r);
  set_adjacency_at_source_between(enn,e,en->twin());
  set_adjacency_at_source_between(rnn,r,rn->twin());
}
     

/*{\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 |(e->source(),())| 
  by inserting |e1| before or after |e| into cyclic adjacency list of
  |e->source()| 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(cap(ef),e1,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, int pos = AFTER)
/*{\Mop makes |v| the target of |e| appends |e->twin()| to the adjacency list
   of |v|.}*/
{ if (!is_isolated(v)) {
    SHalfedge_handle ef = first_out_edge(v);
    set_adjacency_at_source_between(cap(ef), e->twin(), ef);
    if(pos<0)
      set_first_out_edge(v,e->twin());
  } else
    close_tip_at_target(e,v);
}

void link_as_source_of(SHalfedge_handle e, SVertex_handle v) const
/*{\Mop makes |e->source() = 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 |e->target() = v| and sets |e| as the first
  in edge if |v| was isolated before.}*/
{ link_as_source_of(e->twin(),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=e->source()|. \precond |e->source()==en->source()|.}*/
{ CGAL_assertion(e->source()==en->source());
  link_as_prev_next_pair(en->twin(),e);
}