// Copyright (c) 1997 Tel-Aviv University (Israel).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $Source: /CVSROOT/CGAL/Packages/Planar_map/include/CGAL/Topological_map.h,v $
// $Revision: 1.20 $ $Date: 2004/07/08 14:25:56 $
// $Name: $
//
// Author(s) : Iddo Hanniel <hanniel@math.tau.ac.il>
// Oren Nechushtan <theoren@math.tau.ac.il>
#ifndef CGAL_TOPOLOGICAL_MAP_H
#define CGAL_TOPOLOGICAL_MAP_H
#include <CGAL/HalfedgeDS_iterator.h>
#include <CGAL/Planar_map_2/Pm_traits_wrap_2.h>
CGAL_BEGIN_NAMESPACE
template <class Dcel >
class Topological_map {
protected:
typedef typename Dcel::Vertex dvertex;
typedef typename Dcel::Halfedge dedge;
typedef typename Dcel::Face dface;
public:
typedef typename Dcel::Size Size;
typedef typename Dcel::size_type size_type;
typedef typename Dcel::difference_type difference_type;
typedef typename Dcel::difference_type Difference;
typedef typename Dcel::iterator_category iterator_category;
// These extra (internal) typedefs are necessary to make
// SunPro CC 4.2 happy. (And they are used.)
typedef typename Dcel::Vertex_iterator TR_VI;
typedef typename Dcel::Vertex_const_iterator TR_C_VI;
typedef typename Dcel::Halfedge_iterator TR_HI;
typedef typename Dcel::Halfedge_const_iterator TR_C_HI;
typedef typename Dcel::Edge_iterator TR_EI;
typedef typename Dcel::Edge_const_iterator TR_C_EI;
typedef typename Dcel::Face_iterator TR_FI;
typedef typename Dcel::Face_const_iterator TR_C_FI;
typedef typename Dcel::Face::Holes_iterator TR_HOI;
typedef typename Dcel::Face::Holes_const_iterator TR_C_HOI;
public:
class Vertex;
class Halfedge;
class Face;
//in VC class's private members aren't available in nested classes
#if _MSC_VER>=1100
friend Face;
#endif
typedef I_HalfedgeDS_iterator<TR_VI, Vertex, Difference, iterator_category>
Vertex_iterator;
typedef I_HalfedgeDS_const_iterator<TR_C_VI, TR_VI, Vertex,
Difference, iterator_category>
Vertex_const_iterator;
typedef I_HalfedgeDS_iterator<TR_HI, Halfedge, Difference,
iterator_category>
Halfedge_iterator;
typedef I_HalfedgeDS_const_iterator<TR_C_HI, TR_HI, Halfedge, Difference,
iterator_category>
Halfedge_const_iterator;
typedef I_HalfedgeDS_iterator<TR_EI, Halfedge, Difference,
iterator_category>
Edge_iterator;
typedef I_HalfedgeDS_const_iterator<TR_C_EI, TR_EI, Halfedge,
Difference, iterator_category>
Edge_const_iterator;
typedef I_HalfedgeDS_iterator<TR_FI, Face, Difference, iterator_category>
Face_iterator;
typedef I_HalfedgeDS_const_iterator<TR_C_FI, TR_FI, Face, Difference,
iterator_category>
Face_const_iterator;
typedef _HalfedgeDS_facet_circ<Halfedge, Halfedge_iterator,
Forward_circulator_tag>
Ccb_halfedge_circulator;
typedef _HalfedgeDS_vertex_circ<Halfedge, Halfedge_iterator,
Forward_circulator_tag>
Halfedge_around_vertex_circulator;
typedef _HalfedgeDS_facet_const_circ<Halfedge, Halfedge_const_iterator,
Forward_circulator_tag>
Ccb_halfedge_const_circulator;
typedef _HalfedgeDS_vertex_const_circ<Halfedge, Halfedge_const_iterator,
Forward_circulator_tag>
Halfedge_around_vertex_const_circulator;
typedef I_HalfedgeDS_iterator<TR_HOI, Ccb_halfedge_circulator,
Difference, std::bidirectional_iterator_tag>
Holes_iterator;
typedef I_HalfedgeDS_const_iterator<TR_C_HOI, TR_HOI,
Ccb_halfedge_const_circulator,
Difference,
std::bidirectional_iterator_tag>
Holes_const_iterator;
typedef Vertex_iterator Vertex_handle;
typedef Halfedge_iterator Halfedge_handle;
typedef Face_iterator Face_handle;
typedef Vertex_const_iterator Vertex_const_handle;
typedef Halfedge_const_iterator Halfedge_const_handle;
typedef Face_const_iterator Face_const_handle;
/**************************************************************/
/********************* V e r t e x ****************************/
/**************************************************************/
/**************************************************************/
class Vertex : public Dcel::Vertex {
public:
typedef typename Dcel::Vertex Base;
Vertex() {}
Vertex(Base *v) : Base(*v) {}
Vertex(Base& v) : Base(v) {}
bool is_incident_edge(Halfedge_const_handle e) const
{
return (&(*(e->source())) == this) || (&(*(e->target())) == this);
}
bool is_incident_face(Face_const_handle f) const
{
// const typename Dcel::Halfedge* e_ptr=(dvertex::halfedge());
const typename Dcel::Halfedge* e_ptr=(Base::halfedge());
do {
if ( e_ptr->face() == &(*f) )
return true;
e_ptr = e_ptr->opposite()->next();
// } while (e_ptr != dvertex::halfedge());
} while (e_ptr != Base::halfedge());
return false;
}
unsigned int degree() const
{
// const typename Dcel::Halfedge* e=dvertex::halfedge();
const typename Dcel::Halfedge * e = Base::halfedge();
const typename Dcel::Halfedge * e1 = e;
int n = 0;
if (e1 != NULL) {
do {
n++;
e1 = e1->next()->opposite();
} while (e1 != e);
}
return n;
}
Halfedge_around_vertex_circulator incident_halfedges()
{
//return Halfedge_around_vertex_circulator(TR_HI(dvertex::halfedge()));
return Halfedge_around_vertex_circulator(TR_HI(Base::halfedge()));
}
Halfedge_around_vertex_const_circulator incident_halfedges() const
{
//return
//Halfedge_around_vertex_const_circulator(TR_C_HI(dvertex::halfedge()));
return
Halfedge_around_vertex_const_circulator(TR_C_HI(Base::halfedge()));
}
private:
// void set_halfedge(Halfedge* h) {dvertex::set_halfedge(h);}
void set_halfedge(Halfedge* h) {Base::set_halfedge(h);}
};
/**************************************************************/
/**************************************************************/
/********************* Halfedge *******************************/
/**************************************************************/
/**************************************************************/
class Halfedge : public Dcel::Halfedge {
public:
typedef typename Dcel::Halfedge Base;
Halfedge() {}
Halfedge(Base *e) : Base(*e) {}
Halfedge(Base& e) : Base(e) {}
Vertex_handle source()
{
return TR_VI(Base::opposite()->vertex());
}
Vertex_const_handle source() const
{
return TR_C_VI(Base::opposite()->vertex());
}
Vertex_handle target()
{
return TR_VI(Base::vertex());
}
Vertex_const_handle target() const
{
return TR_C_VI(Base::vertex());
}
Face_handle face()
{
return TR_FI(Base::face());
}
Face_const_handle face() const
{
return TR_C_FI(Base::face());
}
Halfedge_handle twin()
{
return TR_HI(Base::opposite());
}
Halfedge_const_handle twin() const
{
return TR_C_HI(Base::opposite());
}
Halfedge_handle next_halfedge()
{
return TR_HI(Base::next());
}
Halfedge_const_handle next_halfedge() const
{
return TR_C_HI(Base::next());
}
Ccb_halfedge_circulator ccb()
{
return Ccb_halfedge_circulator(TR_HI(this));
}
Ccb_halfedge_const_circulator ccb() const
{
return Ccb_halfedge_const_circulator(TR_C_HI(this));
}
private: //hide from users the underlying structure
void set_next( Halfedge* h) { Base::set_next(h);}
void set_vertex( Vertex* ve) { Base::set_vertex(ve);}
void set_face( Face* face) { Base::set_face(face);}
};
/**************************************************************/
/**************************************************************/
/********************* F a c e ********************************/
/**************************************************************/
/**************************************************************/
class Face : public Dcel::Face {
public:
typedef typename Dcel::Face Base;
#ifndef _MSC_VER
// the following two typedefs are needed for compilation on irix64 (CC7.30)
typedef typename Topological_map<Dcel>::Holes_iterator
Holes_iterator;
typedef typename Topological_map<Dcel>::Holes_const_iterator
Holes_const_iterator;
#endif
Face() {}
Face(Base *f) : Base(*f) {}
Face(Base& f) : Base(f) {}
bool is_unbounded() const
{
// face is not bounded iff it has no outer boundary
return (Base::halfedge() == NULL);
}
// must explicitly say Topological_map::Holes_iterator. Otherwise
// the CC compiler thinks we mean Base::Holes_iterator.
Holes_iterator holes_begin()
{
return TR_HOI(Base::holes_begin());
}
Holes_const_iterator holes_begin() const
{
return TR_C_HOI(Base::holes_begin());
}
Holes_iterator holes_end()
{
return TR_HOI(Base::holes_end());
}
Holes_const_iterator holes_end() const
{
return TR_C_HOI(Base::holes_end());
}
bool is_halfedge_on_inner_ccb(Halfedge_const_handle e)
#if !(_MSC_VER>=1100)
const
#endif
{
dedge* dummy;
return (/*Topological_map<Dcel>::*/
is_halfedge_on_inner_ccb(&(*e),
(typename Dcel::Face*)this,
dummy));
// oren corrections (dummy parameter - for bug in MSC)
}
bool is_halfedge_on_outer_ccb(Halfedge_const_handle e)
#if !(_MSC_VER>=1100)
const
#endif
{
dedge* dummy;
return /*Topological_map<Dcel>::*/
is_halfedge_on_outer_ccb(&(*e),this,dummy);
// oren corrections (dummy parameter - bug in MSC)
}
bool does_outer_ccb_exist() const
{
return Base::halfedge() != NULL;
}
Halfedge_handle halfedge_on_outer_ccb()
{
CGAL_precondition(does_outer_ccb_exist());
return TR_HI(Base::halfedge());
}
Halfedge_const_handle halfedge_on_outer_ccb() const
{
CGAL_precondition(does_outer_ccb_exist());
return TR_C_HI(Base::halfedge());
}
Ccb_halfedge_circulator outer_ccb()
{
CGAL_precondition(does_outer_ccb_exist());
return (halfedge_on_outer_ccb())->ccb();
}
Ccb_halfedge_const_circulator outer_ccb() const
{
CGAL_precondition(does_outer_ccb_exist());
return (halfedge_on_outer_ccb())->ccb();
}
private:
void set_halfedge( Halfedge* h) { Base::set_halfedge(h);}
void add_hole(Halfedge* h) {Base::add_hole(h);}
};
/*! Constructor */
Topological_map() : d()
{
u_face = d.new_face();
u_face->set_halfedge(NULL);
}
/*
* INSERTIONS
*
* insertion from vertices may invalidate the holes containers (since a new
* face can be created which contains some of the holes of the old face.
* to validate the containers the function move_hole should be called.
*
* if a new face is created, returns the halfedge on the new face.
* the new face will ALWAYS (by definition) be the one from v1->v2 (==e1)
* this sets a requirement on the user!!! (since a topological pm can't
* know if v1->v2 is on the new face or v2->v1)
*
* since there can be a number of edges from the vertices, and we can't
* now topologically which will be in the new face and which will be
* outside, this should be provided by the user - defining prev1 and
* prev2 (previous to v1,v2 resp.) the planar map will define this
* geometrically using the one previous to the curve clock wise.
*/
Halfedge_handle insert_at_vertices( Halfedge_handle previous1,
Halfedge_handle previous2) ;
//moves ONE hole from f1 to f2
void move_hole(Holes_iterator e, Face_handle f1, Face_handle f2);
Halfedge_handle insert_from_vertex(Halfedge_handle previous) ;
Halfedge_handle insert_in_face_interior(Face_handle f) ;
Halfedge_handle split_edge (Halfedge_handle e ) ;
Halfedge_handle merge_edge (Halfedge_handle e1, Halfedge_handle e2) ;
//returns the merged face after the deletion
Face_handle remove_edge(Halfedge_handle e) ;
Face_handle unbounded_face()
{
return TR_FI(u_face);
}
Face_const_handle unbounded_face() const {
return TR_C_FI(u_face);
}
Face_iterator faces_begin()
{
return TR_FI(d.faces_begin());
}
Face_const_iterator faces_begin() const
{
return TR_C_FI(d.faces_begin());
}
Face_iterator faces_end()
{
return TR_FI(d.faces_end());
}
Face_const_iterator faces_end() const
{
return TR_C_FI(d.faces_end());
}
Halfedge_iterator halfedges_begin()
{
return TR_HI(d.halfedges_begin());
}
Halfedge_const_iterator halfedges_begin() const
{
return TR_C_HI(d.halfedges_begin());
}
Halfedge_iterator halfedges_end()
{
return TR_HI(d.halfedges_end());
}
Halfedge_const_iterator halfedges_end() const
{
return TR_C_HI(d.halfedges_end());
}
Edge_iterator edges_begin()
{
return TR_EI(d.edges_begin());
}
Edge_const_iterator edges_begin() const
{
return TR_C_EI(d.edges_begin());
}
Edge_iterator edges_end()
{
return TR_EI(d.edges_end());
}
Edge_const_iterator edges_end() const
{
return TR_C_EI(d.edges_end());
}
Vertex_iterator vertices_begin()
{
return TR_VI(d.vertices_begin());
}
Vertex_const_iterator vertices_begin() const
{
return TR_C_VI(d.vertices_begin());
}
Vertex_iterator vertices_end()
{
return TR_VI(d.vertices_end());
}
Vertex_const_iterator vertices_end() const
{
return TR_C_VI(d.vertices_end());
}
void clear()
{
d.delete_all();
u_face = NULL;
u_face = d.new_face();
u_face->set_halfedge(NULL);
}
void assign(const Topological_map<Dcel> &tpm)
{
d.delete_all();
u_face = NULL;
u_face = (Face*)d.assign(tpm.d, tpm.u_face);
}
/**************************************************************/
/**************************************************************/
/*********** Topological_map_2 - validity checks ********/
/**************************************************************/
/**************************************************************/
bool is_valid(Vertex_const_handle v
#if _MSC_VER>=1100 // VC template bug
,Vertex* dummy=NULL
#endif
) const
{
bool valid = true;
// check if every edge from v has v as its target
Halfedge_around_vertex_const_circulator ec = v->incident_halfedges();
Halfedge_around_vertex_const_circulator start = ec;
do {
if ((*ec).target() != v)
{
valid = false;
}
++ec;
} while (ec != start);
return valid;
}
bool is_valid(Halfedge_const_handle e
#if _MSC_VER>=1100 // VC template bug
,Halfedge* dummy=NULL
#endif
) const
{
//check relations with next
if (e->target() != e->next_halfedge()->source())
return false;
return true;
}
bool is_valid(const Ccb_halfedge_const_circulator& start,
Face_const_handle f) const
{
bool valid = true;
Ccb_halfedge_const_circulator circ = start;
do {
if ((*circ).face() != f)
valid = false;
++circ;
} while (circ != start);
return valid;
}
bool is_valid(Face_const_handle f
#if _MSC_VER>=1100 // VC template bug
,Face* dummy=NULL
#endif
) const
{
bool valid = true;
// check if all edges of f (on all ccb's) refer to f (as their face)
Holes_const_iterator iccbit;
Ccb_halfedge_const_circulator ccb_circ;
if (f->does_outer_ccb_exist())
{
ccb_circ = f->outer_ccb();
if (!is_valid(ccb_circ, f))
valid = false;
}
for (iccbit = f->holes_begin(); iccbit != f->holes_end(); ++iccbit)
{
ccb_circ = *iccbit;
if (!is_valid(ccb_circ, f))
valid = false;
}
return valid;
}
/*! Chcecks whether the planar map is valid. In particular is_valid()
* checks the validity of each vertex, halfedge, and face
*/
bool is_valid() const
{
Vertex_const_iterator vi;
for (vi = vertices_begin(); vi != vertices_end(); ++vi) {
if (!is_valid(vi)) {
CGAL_warning("Invalid vertex!");
return false;
}
}
Halfedge_const_iterator ei;
for (ei = halfedges_begin(); ei != halfedges_end(); ++ei) {
if (!is_valid(ei)) {
CGAL_warning("Invalid halfedge!");
return false;
}
}
Face_const_iterator fi;
for (fi = faces_begin(); fi != faces_end(); ++fi) {
if (!is_valid(fi)) {
CGAL_warning("Invalid face!");
return false;
}
}
return true;
}
/******************************************************************/
/********************* counting functions ***********************/
/******************************************************************/
Size number_of_faces() const
{
return d.size_of_faces();
}
//counts every halfedge (i.e always even)
Size number_of_halfedges() const
{
return d.size_of_halfedges();
}
Size number_of_vertices() const
{
return d.size_of_vertices();
}
//---------------------------------------------------------------
//PRIVATE IMPLEMENTATIONS
//---------------------------------------------------------------
private:
//find previous halfedge of given halfedge
typename Dcel::Halfedge* get_prev( typename Dcel::Halfedge* de)
{
//find previous halfedge of de
typename Dcel::Halfedge* prev=de;
do {
if (prev->next()==de) break;
prev=prev->next();
}while (prev!=de); //assumes a loop to itself is unacceptable
CGAL_assertion(prev!=de);
return prev;
}
bool find_and_erase_hole(typename Dcel::Halfedge* e, typename Dcel::Face* f)
{
typename Dcel::Face::Holes_iterator it=f->holes_begin();
bool ret=false;
for (; it!=f->holes_end(); ++it) {
if ( (*it)==e ) {
f->erase_hole(it);
ret=true;
break;
}
}
return ret;
}
protected:
// forbid copy constructor and assignment
/*! Copy Constructor */
Topological_map(const Topological_map & tm)
{
// d = tm.d;
// u_face = tm.u_face;
}
/*! Assignment operator */
Topological_map & operator=(const Topological_map &)
{
// d = tm.d;
// u_face = tm.u_face;
return *this;
}
protected:
Dcel d;
dface* u_face;
};
/////////////////////////////////////////////////////////////////
// implementation
/////////////////////////////////////////////////////////////////
template <class Dcel>
bool is_halfedge_on_inner_ccb(const typename Dcel::Halfedge* e,
typename Dcel::Face* f,
typename Dcel::Halfedge* &iccb)
{
typedef typename Dcel::Vertex dvertex;
typedef typename Dcel::Halfedge dedge;
typedef typename Dcel::Face dface;
//move over all holes in face and check
for (typename dface::Holes_iterator dhi=f->holes_begin();
dhi!=f->holes_end();
++dhi)
{
iccb=(*dhi);
const typename Dcel::Halfedge* aux=iccb;
do
{
if (aux==e)
return true;
aux=aux->next() ;
} while (aux!=(*dhi));
}
iccb=NULL;
return false;
}
//returns the representative halfedge of outer ccb in occb, or false
template <class Dcel>
bool is_halfedge_on_outer_ccb(const typename Dcel::Halfedge* e,
typename Dcel::Face* f,
typename Dcel::Halfedge* &occb)
{
typedef typename Dcel::Vertex dvertex;
typedef typename Dcel::Halfedge dedge;
typedef typename Dcel::Face dface;
occb=f->halfedge();
if ( occb ) { //if f isn't the unbounded face
const typename Dcel::Halfedge* aux=occb;
do
{
if (aux==e)
return true;
aux=aux->next();
}while (aux!=f->halfedge());
}
occb=NULL;
return false;
}
//insertion from vertices may invalidate the holes containers (since a new
//face can be created which contains some of the holes of the old face.
//to validate the containers the function move_hole should be called.
//if a new face is created, returns the halfedge on the new face. the
//new face will ALWAYS (by definition) be the one from v1->v2
//(==previous1->e1->..) this sets a requirement on the user!!! (since
//a topological pm can't know if v1->v2 is on the new face or v2->v1)
//since there can be a number of edges from the vertices, and we can't
//know topologically which will be in the new face and which will be
//outside, this should be provided by the user - defining prev1 and
//prev2 (previous to v1,v2 resp.) the planar map will define this
//geometrically using the one previous to the curve clock wise.
//prev1->target() is v1
template<class Dcel>
typename Topological_map<Dcel>::Halfedge_handle
Topological_map<Dcel>::
insert_at_vertices(Halfedge_handle previous1, Halfedge_handle previous2)
{
// vertices should be distinct
CGAL_precondition(previous1->target()!=previous2->target());
typename Dcel::Halfedge *prev1=&(*previous1), *prev2=&(*previous2);
typename Dcel::Vertex* dv1=prev1->vertex();
typename Dcel::Vertex* dv2=prev2->vertex();
CGAL_precondition(prev1->face()==prev2->face());
typename Dcel::Face* df=prev1->face();
//will hold represantative halfedge of prev1/2
typename Dcel::Halfedge *ccb1,*ccb2;
if (!(is_halfedge_on_outer_ccb<Dcel>(prev1,df,ccb1)) )
is_halfedge_on_inner_ccb<Dcel>(prev1,df,ccb1);
if (!(is_halfedge_on_outer_ccb<Dcel>(prev2,df,ccb2)) )
is_halfedge_on_inner_ccb<Dcel>(prev2,df,ccb2);
bool ccb1_is_inner = !(ccb1==df->halfedge());
bool ccbs_equal = (ccb1 == ccb2);
typename Dcel::Halfedge* e1=d.new_edge();
typename Dcel::Halfedge* e2=e1->opposite();
e1->set_vertex(dv1);
e2->set_vertex(dv2);
e1->set_next(prev1->next());
e2->set_next(prev2->next());
prev1->set_next(e2);
prev2->set_next(e1);
//Cases:
//a. ccb1!=ccb2 (at least one is inner ccb) - no face added
if (!ccbs_equal) {
e1->set_face(df);
e2->set_face(df);
//remove ONE inner ccb from df
if (ccb1_is_inner) {
//ccb1 becomes part of ccb2
find_and_erase_hole(ccb1,df);
}
else {
//ccb2 becomes part of ccb1
find_and_erase_hole(ccb2,df);
}
return TR_HI(e2);
}
//b. ccb1==ccb2
//new face is created
//the new face will ALWAYS (by definition) be the one from v1->v2 (==e2)
//this sets a requirement on the user!!!
//the planar map will define this geometrically
//(by finding the leftmost halfedge
//(or left-down) when going from v1 to v2 (visiting v1 only once!!) and
//checking if it is up or down, if it is up then send v1->v2 else
//send v2->v1)
typename Dcel::Face* nf = d.new_face();
//b.1 the vertices are on outer ccb
if (! ccb1_is_inner) {
e2->set_face(nf);
e1->set_face(df);
nf->set_halfedge(e2); //set the represantative edge to be e2
df->set_halfedge(e1);
//set the face pointer for all halfedges of e2 to nf
ccb2=e2->next();
while (ccb2!=e2)
{
ccb2->set_face(nf);
ccb2=ccb2->next();
}
}
//b.2 the vertices are on an inner ccb
else {
e1->set_face(df);
e2->set_face(nf);
nf->set_halfedge(e2);
ccb2=e2->next();
while (ccb2!=e2) {
ccb2->set_face(nf);
ccb2=ccb2->next();
}
//remove ccb1 from holes_container (maybe it is now inside the new face)
find_and_erase_hole(ccb1,df);
df->add_hole(e1);
}
return TR_HI(e2);
}
template<class Dcel>
void Topological_map<Dcel>::
move_hole(Holes_iterator e, Face_handle f1, Face_handle f2)
{
//move hole from df1 to df2 and set face pointer of each edge on hole to df1
typename Dcel::Face* df1=&(*f1);
typename Dcel::Face* df2=&(*f2);
//set face pointers to df1
typename Dcel::Halfedge* last=&(*(*(e)));
typename Dcel::Halfedge* first=last;
do {
first->set_face(df2);
first=first->next();
} while (first!=last) ;
//copy to df2
df2->add_hole(first);
df1->erase_hole(e.current_iterator());
}
//returns halfedge which is previous->next
template<class Dcel>
typename Topological_map<Dcel>::Halfedge_handle
Topological_map<Dcel>::
insert_from_vertex(Halfedge_handle previous)
{
typename Dcel::Halfedge* prev=&(*previous);
typename Dcel::Face* df=prev->face();
typename Dcel::Vertex* dv1=prev->vertex();
typename Dcel::Vertex* dv2=d.new_vertex(); //the new vertex
typename Dcel::Halfedge* h1=d.new_edge();
typename Dcel::Halfedge* h2=h1->opposite();
h1->set_vertex(dv1);
h2->set_vertex(dv2);
h1->set_face(df);
h2->set_face(df);
dv2->set_halfedge(h2);
h2->set_next(h1);
h1->set_next(prev->next());
prev->set_next(h2);
return TR_HI(h2);
}
template<class Dcel>
typename Topological_map<Dcel>::Halfedge_handle
Topological_map<Dcel>::
insert_in_face_interior(Face_handle f)
{
typename Dcel::Vertex* v1=d.new_vertex();
typename Dcel::Vertex* v2=d.new_vertex();
typename Dcel::Halfedge* h1 = d.new_edge();
typename Dcel::Halfedge* h2 = h1->opposite();
typename Dcel::Face* fp =&(*f);
h1->set_next(h2);
h1->set_vertex(v1);
h1->set_face(fp);
h2->set_next(h1);
h2->set_vertex(v2);
h2->set_face(fp);
v1->set_halfedge(h1);
v2->set_halfedge(h2);
fp->add_hole(h1);
return TR_HI(h1);
}
template<class Dcel>
typename Topological_map<Dcel>::Halfedge_handle
Topological_map<Dcel>::split_edge (Halfedge_handle e)
{
typename Dcel::Halfedge* e1=&(*e);
typename Dcel::Halfedge* e2=e1->opposite();
//find previous halfedge of e2
typename Dcel::Halfedge* prev2=get_prev(e2);
typename Dcel::Vertex* v=d.new_vertex();
typename Dcel::Halfedge* e3=d.new_edge();
typename Dcel::Halfedge* e4=e3->opposite();
v->set_halfedge(e4);
if (e1->next()!=e2)
e3->set_next(e1->next());
else
e3->set_next(e4);
e4->set_vertex(v);
e3->set_face(e1->face());
e4->set_next(e2);
e3->set_vertex(e1->vertex());
e4->set_face(e2->face());
e1->vertex()->set_halfedge(e3); //makes the incident halfedge e3
//(so if e1 was the incident halfedge it comes instead ) - changed
if (prev2!=e1)
prev2->set_next(e4);
//otherwise e3->set_next(e4) - taken care above
e1->set_next(e3);
e1->set_vertex(v);
return TR_HI(e1);
}
/*! Merge 2 given halfedges into one
* \param e1 the first input halfedge
* \param e2 second input halfedge
* \return the merged halfedge
*/
template<class Dcel>
typename Topological_map<Dcel>::Halfedge_handle
Topological_map<Dcel>::merge_edge(Halfedge_handle e1, Halfedge_handle e2)
{
//check e1->e2 and that degree(e1.target)==2 (i.e no other edge connected)
//CGAL_assertion(e1->target()==e2->source());
CGAL_assertion((e1->target()==e2->source() && e1->target()->degree()==2 ) ||
(e2->target()==e1->source() && e2->target()->degree()==2 ) ||
(e1->target()==e2->target() && e1->target()->degree()==2 ) ||
(e2->source()==e1->source() && e1->source()->degree()==2 ));
//CGAL_assertion(e1->target()->degree()==2);
typename Dcel::Halfedge * de1 = 0;
typename Dcel::Halfedge * de1t = 0;
typename Dcel::Halfedge * de2 = 0;
typename Dcel::Halfedge * de2t = 0;
if (e1->target() == e2->source())
{
de1 = &(*e1);
de1t = de1->opposite();
de2 = &(*e2);
de2t = de2->opposite();
}
if (e1->source() == e2->source())
{
de1t = &(*e1);
de1 = de1t->opposite();
de2 = &(*e2);
de2t = de2->opposite();
}
if (e1->target() == e2->target())
{
de1 = &(*e1);
de1t = de1->opposite();
de2t = &(*e2);
de2 = de2t->opposite();
}
if (e1->source() == e2->target())
{
de1t = &(*e1);
de1 = de1t->opposite();
de2t = &(*e2);
de2 = de2t->opposite();
}
typename Dcel::Vertex * v = de1->vertex();
typename Dcel::Face * f = de2->face();
typename Dcel::Face * ft = de1t->face();
//typename Dcel::Face* ft=de2t->face();
//at the end de1 and de1t will remain and de2t,de2 will be deleted
//check if they are a "represantative" of a hole or outer ccb of face
if (f->halfedge()==de2)
f->set_halfedge(de1);
else {
if (find_and_erase_hole(de2,f))
f->add_hole(de1);
}
if (ft->halfedge()==de2t)
ft->set_halfedge(de1t);
else {
if (find_and_erase_hole(de2t,f))
f->add_hole(de1t);
}
//in case de2 is representative halfedge of the target vertex
de2->vertex()->set_halfedge(de1);
if (de2->next() != de2t) { //de2 is not a tip of antenna
//find previous halfedge of de2t
typename Dcel::Halfedge* prev2=get_prev(de2t);
de1->set_next(de2->next());
prev2->set_next(de1t);
}
else {
de1->set_next(de1t);
}
de1->set_vertex(de2->vertex());
d.delete_edge(de2);
d.delete_vertex(v);
return TR_HI(de1);
}
template<class Dcel>
typename Topological_map<Dcel>::Face_handle
Topological_map<Dcel>::remove_edge(Halfedge_handle e)
{
typename Dcel::Halfedge* de1=&(*e);
typename Dcel::Halfedge* de2=de1->opposite();
typename Dcel::Face* df1=de1->face();
typename Dcel::Face* df2=de2->face();
typename Dcel::Halfedge* prev1;
typename Dcel::Halfedge* prev2;
//CASES:
if (df1==df2) { //case a. antenna - no face deleted
if (de1->next()==de2 && de2->next()==de1) {
//a.1 only one edge as a hole
if (!find_and_erase_hole(de1,df1))
find_and_erase_hole(de2,df1);
d.delete_vertex(de2->vertex());
d.delete_vertex(de1->vertex());
d.delete_edge(de1);
return TR_FI(df1);
}
if (de1->next()==de2 || de2->next()==de1) {
//a.2 a tip of the antenna
if (de1->next()==de2) { //de1 points at the tip
prev1=get_prev(de1);
prev1->set_next(de2->next());
//check if they are a represantative halfedge if so exchange
if (df1->halfedge()==de2)
df1->set_halfedge(prev1);
else {
if (find_and_erase_hole(de2,df1))
df1->add_hole(prev1);
}
if (df1->halfedge()==de1)
df1->set_halfedge(prev1);
else {
if (find_and_erase_hole(de1,df1))
df1->add_hole(prev1);
}
//check if de2 is incident halfedge of de2->vertex and if so -
//change to prev1 (iddo 16/6)
if (de2->vertex()->halfedge() == de2)
de2->vertex()->set_halfedge(prev1);
d.delete_vertex(de1->vertex()); //changed to conform with HDS
}
else { //de2 points at the tip - find previous halfedge of de2
prev2=get_prev(de2);
prev2->set_next(de1->next());
//check if they are represantative halfedge if so exchange
if (df1->halfedge()==de2)
df1->set_halfedge(prev2);
else {
if (find_and_erase_hole(de2,df1))
df1->add_hole(prev2);
}
if (df1->halfedge()==de1)
df1->set_halfedge(prev2);
else {
if (find_and_erase_hole(de1,df1))
df1->add_hole(prev2);
}
//check if de1 is incident halfedge of de1->vertex and if so -
//change to prev2
if (de1->vertex()->halfedge() == de1)
de1->vertex()->set_halfedge(prev2) ;
d.delete_vertex(de2->vertex());
}
d.delete_edge(de1);
return TR_FI(df1);
}
//a.3 a middle of an antenna - a new hole is created
prev1=get_prev(de1);
prev2=get_prev(de2);
//find the ccb of de1/de2
typename Dcel::Halfedge *ccb1;
if (is_halfedge_on_outer_ccb<Dcel>(prev1,df1,ccb1)) {
//antenna is connected to outer ccb, split a hole from it.
//we assume in this case that de1->next is the hole
//(to be determined genoetrically by the user)
df1->add_hole(de1->next());
df1->set_halfedge(prev1);
}
else { //antenna is a hole - split it into two holes
is_halfedge_on_inner_ccb<Dcel>(prev1,df1,ccb1);
#if defined(CGAL_NO_ASSERTIONS) || defined(NDEBUG)
find_and_erase_hole(ccb1,df1);
#else
bool hole_found = find_and_erase_hole(ccb1,df1);
CGAL_assertion(hole_found); //ccb1 must be a hole in df1
#endif
df1->add_hole(prev1);
df1->add_hole(prev2);
}
prev1->set_next(de2->next());
prev2->set_next(de1->next());
//check if de1 is incident halfedge of de1->vertex() and if so change to
//prev2 same for de2
if (de1->vertex()->halfedge() == de1)
de1->vertex()->set_halfedge(prev2);
if (de2->vertex()->halfedge() == de2)
de2->vertex()->set_halfedge(prev1);
d.delete_edge(de1);
return TR_FI(df1);
}
else { //case b. edge between faces - merge faces
typename Dcel::Halfedge* ccb;
bool de1_is_on_hole=!(is_halfedge_on_outer_ccb<Dcel>(de1,df1,ccb));
bool de2_is_on_hole=!(is_halfedge_on_outer_ccb<Dcel>(de2,df2,ccb));
if ( !de1_is_on_hole && !de2_is_on_hole ) {
//b.1 both halfedges are on outer boundary
prev1=get_prev(de1);
prev2=get_prev(de2);
//arbitrarily df2 will be removed - change all edges so point to df1
//set the face pointer for all halfedges of df2 to df1
typename Dcel::Halfedge* aux=de2->next();
while (aux!=de2)
{
aux->set_face(df1);
aux=aux->next();
}
//move holes from df2 to df1 and set face pointer of each edge on
//hole to df1
typename Dcel::Face::Holes_iterator hi = df2->holes_begin();
for ( ; hi!=df2->holes_end(); ++hi) {
//set face pointers to df1
typename Dcel::Halfedge* aux1=(*hi);
do {
aux1->set_face(df1);
aux1=aux1->next();
} while (aux1!=(*hi)) ;
}
//copy the holes to the holes list of df1
for (hi = df2->holes_begin(); hi!=df2->holes_end(); ++hi) {
df1->add_hole(*hi);
}
df2->erase_holes(df2->holes_begin(),df2->holes_end());
//check if represantative edge
if (de1==df1->halfedge())
df1->set_halfedge(prev1);
//check if de1 is incident halfedge of de1->vertex() and if so change to
//prev2 same for de2
if (de1->vertex()->halfedge() == de1)
de1->vertex()->set_halfedge(prev2);
if (de2->vertex()->halfedge() == de2)
de2->vertex()->set_halfedge(prev1);
prev1->set_next(de2->next());
prev2->set_next(de1->next());
d.delete_face(df2);
d.delete_edge(de1);
return TR_FI(df1);
}
else { //edge is on a hole
prev1=get_prev(de1);
prev2=get_prev(de2);
if (de1_is_on_hole) { //df1 is the outer face df2 was the hole
//df2 will be removed - change all edges so point to df1
//set the face pointer for all halfedges of df2 to df1
typename Dcel::Halfedge* aux=de2->next();
while (aux!=de2) {
aux->set_face(df1);
aux=aux->next();
}
//move holes from df2 to df1 and set face pointer of each edge on
//hole to df1
typename Dcel::Face::Holes_iterator hi = df2->holes_begin();
for ( ; hi!=df2->holes_end(); ++hi) {
//set face pointers to df1
typename Dcel::Halfedge* aux1=(*hi);
do {
aux1->set_face(df1);
aux1=aux1->next();
} while (aux1!=(*hi)) ;
}
//copy to the holes list of df1
for (hi = df2->holes_begin(); hi!=df2->holes_end(); ++hi) {
df1->add_hole(*hi);
}
df2->erase_holes(df2->holes_begin(),df2->holes_end());
//check if de1 is a represantative hole of df1 (it is not on the outer)
if (find_and_erase_hole(de1,df1))
df1->add_hole(prev1);
//check if de1 is incident halfedge of de1->vertex() and if so change to
//prev2 same for de2
if (de1->vertex()->halfedge() == de1)
de1->vertex()->set_halfedge(prev2);
if (de2->vertex()->halfedge() == de2)
de2->vertex()->set_halfedge(prev1);
prev1->set_next(de2->next());
prev2->set_next(de1->next());
d.delete_face(df2);
d.delete_edge(de1);
return TR_FI(df1);
}
else { //df2 is the outer face
//erase df1
//df1 will be removed - change all edges so point to df2
typename Dcel::Halfedge* aux=de1->next();
while (aux!=de1) {
aux->set_face(df2);
aux=aux->next();
}
//move holes from df1 to df2 and set face pointer of each edge on
//hole to df1
typename Dcel::Face::Holes_iterator hi = df1->holes_begin();
for ( ; hi!=df1->holes_end(); ++hi) {
//set face pointers to df2
typename Dcel::Halfedge* aux1=(*hi);
do {
aux1->set_face(df2);
aux1=aux1->next();
} while (aux1!=(*hi)) ;
}
//copy to the holes list of df2
for (hi = df1->holes_begin(); hi!=df1->holes_end(); ++hi) {
df2->add_hole(*hi);
}
df1->erase_holes(df1->holes_begin(),df1->holes_end());
//check if de2 is a represantative hole of df2
if (find_and_erase_hole(de2,df2))
df2->add_hole(prev2);
//check if de1 is incident halfedge of de1->vertex() and if so change to
//to prev2 same for de2
if (de1->vertex()->halfedge() == de1)
de1->vertex()->set_halfedge(prev2);
if (de2->vertex()->halfedge() == de2)
de2->vertex()->set_halfedge(prev1);
prev1->set_next(de2->next());
prev2->set_next(de1->next());
d.delete_face(df1);
d.delete_edge(de1);
return TR_FI(df2);
} //df2 is outer..
} //edge is on a hole..
} //case b. (face deleted)
}
CGAL_END_NAMESPACE
#endif
syntax highlighted by Code2HTML, v. 0.9.1