// Copyright (c) 1999 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/Arrangement/include/CGAL/Arrangement_2.h,v $
// $Revision: 1.38 $ $Date: 2004/09/23 19:37:53 $
// $Name: $
//
// Author(s) : Iddo Hanniel,
// Eti Ezra <estere@post.tau.ac.il>,
// Shai Hirsch <shaihi@post.tau.ac.il>
#ifndef CGAL_ARRANGEMENT_2_H
#define CGAL_ARRANGEMENT_2_H
//for now, since the arrangement default ctr is currently with the walk pl.
#include <CGAL/Pm_walk_along_line_point_location.h>
#include <CGAL/Planar_map_2.h>
#include <CGAL/Arr_2_bases.h>
#include <CGAL/In_place_list.h>
//for circulators
#include <CGAL/Arr_iterators.h>
#include <CGAL/IO/Verbose_ostream.h>
#include <CGAL/Pm_with_intersections.h>
#include <CGAL/Planar_map_2/Pm_traits_wrap_2.h>
#include <CGAL/IO/Arr_file_scanner.h>
#include <CGAL/HalfedgeDS_default.h>
#include <vector>
CGAL_BEGIN_NAMESPACE
template <class _Dcel, class _Traits,
class Base_node =
Arr_base_node<typename _Traits::Curve_2,
typename _Traits::X_monotone_curve_2> >
class Arrangement_2 {
public:
typedef _Dcel Dcel;
typedef _Traits Traits;
typedef Pm_traits_wrap_2<Traits> Traits_wrap;
typedef Planar_map_2<Dcel,Traits> Planar_map;
typedef Pm_walk_along_line_point_location<Planar_map> WalkPL;
typedef Planar_map_with_intersections_2<Planar_map> Pmwx;
typedef typename Pmwx::Change_notification Change_notification;
typedef Arrangement_2<_Dcel,_Traits,Base_node> Self;
typedef typename Traits::Point Point_2;
typedef typename Traits::X_curve X_monotone_curve_2;
typedef typename Traits::Curve Curve_2;
typedef typename Planar_map::Halfedge_handle Pm_halfedge_handle;
typedef typename Planar_map::Face_handle Pm_face_handle;
//for size and stuff
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;
// Obsolete, for backward compatability
typedef Change_notification Pmwx_change_notification;
typedef Point_2 Point;
typedef X_monotone_curve_2 X_curve;
typedef Curve_2 Curve;
enum Locate_type {
VERTEX = Planar_map::VERTEX,
EDGE = Planar_map::EDGE,
FACE = Planar_map::FACE,
UNBOUNDED_VERTEX = Planar_map::UNBOUNDED_VERTEX,
UNBOUNDED_EDGE = Planar_map::UNBOUNDED_EDGE,
UNBOUNDED_FACE = Planar_map::UNBOUNDED_FACE
};
//forward declerations
class Subcurve_node;
class Curve_node;
class Edge_node;
class Vertex;
class Halfedge;
class Face;
///////////////////////////////////////////////////////////////////////
// ITERATOR DEFINITIONS
//for heirarchy tree (H...)
typedef typename In_place_list<Subcurve_node,true>::size_type HSize;
typedef typename In_place_list<Subcurve_node,true>::size_type Hsize_type;
typedef typename In_place_list<Subcurve_node,true>::difference_type
Hdifference_type;
typedef typename In_place_list<Subcurve_node,true>::difference_type
HDifference;
typedef std::bidirectional_iterator_tag Hiterator_category;
// typedefs for iterators (for curve nodes, edge_nodes, sub_curve_nodes and
// HVF)
typedef typename In_place_list<Subcurve_node,true>::iterator
Subcurve_iterator;
typedef typename In_place_list<Subcurve_node,true>::const_iterator
Subcurve_const_iterator;
typedef I_HalfedgeDS_iterator<
Subcurve_iterator,
Curve_node,
HDifference, Hiterator_category> Curve_iterator;
typedef I_HalfedgeDS_const_iterator<
Subcurve_const_iterator, Subcurve_iterator,
Curve_node,
HDifference, Hiterator_category> Curve_const_iterator;
typedef I_HalfedgeDS_iterator<
Subcurve_iterator,
Edge_node,
HDifference, Hiterator_category> Edge_iterator;
typedef I_HalfedgeDS_const_iterator<
Subcurve_const_iterator, Subcurve_iterator,
Edge_node,
HDifference, Hiterator_category> Edge_const_iterator;
//wrappers for planar map iterators
typedef I_HalfedgeDS_iterator<
typename Planar_map::Vertex_iterator,
Vertex,
Difference, typename Planar_map::iterator_category> Vertex_iterator;
typedef I_HalfedgeDS_const_iterator<
typename Planar_map::Vertex_const_iterator,
typename Planar_map::Vertex_iterator,
Vertex,
Difference, typename Planar_map::iterator_category> Vertex_const_iterator;
typedef I_HalfedgeDS_iterator<
typename Planar_map::Halfedge_iterator,
Halfedge,
Difference, typename Planar_map::iterator_category> Halfedge_iterator;
typedef I_HalfedgeDS_const_iterator<
typename Planar_map::Halfedge_const_iterator,
typename Planar_map::Halfedge_iterator,
Halfedge,
Difference, typename Planar_map::iterator_category>
Halfedge_const_iterator;
typedef I_HalfedgeDS_iterator<
typename Planar_map::Face_iterator,
Face,
Difference, typename Planar_map::iterator_category> Face_iterator;
typedef I_HalfedgeDS_const_iterator<
typename Planar_map::Face_const_iterator,
typename Planar_map::Face_iterator,
Face,
Difference, typename Planar_map::iterator_category> Face_const_iterator;
//the following define the overlap circulators
//(might be changed to iterators)
typedef Arr_overlap_circulator<
Edge_node,Edge_iterator,Bidirectional_circulator_tag>
Overlap_circulator;
typedef Arr_overlap_const_circulator<
Edge_node,
Edge_const_iterator,
Bidirectional_circulator_tag> Overlap_const_circulator;
//handles
typedef Vertex_iterator Vertex_handle;
typedef Vertex_const_iterator Vertex_const_handle;
typedef Halfedge_iterator Halfedge_handle;
typedef Halfedge_const_iterator Halfedge_const_handle;
typedef Face_iterator Face_handle;
typedef Face_const_iterator Face_const_handle;
typedef _Arr_face_circ<
Halfedge,
Halfedge_iterator,
Forward_circulator_tag> Ccb_halfedge_circulator;
typedef _Arr_face_const_circ<
Halfedge,
Halfedge_const_iterator,
Forward_circulator_tag> Ccb_halfedge_const_circulator;
typedef _Arr_vertex_circ<
Halfedge,
Halfedge_iterator,
Forward_circulator_tag> Halfedge_around_vertex_circulator;
typedef _Arr_vertex_const_circ<
Halfedge,
Halfedge_const_iterator,
Forward_circulator_tag> Halfedge_around_vertex_const_circulator;
typedef I_HalfedgeDS_iterator<
typename Planar_map::Holes_iterator,
Ccb_halfedge_circulator,
Difference, std::bidirectional_iterator_tag> Holes_iterator;
typedef I_HalfedgeDS_const_iterator<
typename Planar_map::Holes_const_iterator,
typename Planar_map::Holes_iterator,
Ccb_halfedge_const_circulator,
Difference, std::bidirectional_iterator_tag> Holes_const_iterator;
//TREE NODES:
//subcurve_node : Base_node + hides pointers - returns handles/iterators
//curve_node : sub_curve_node + adds levels
//edge_node : sub_curve_node + adds halfedges
///////////////////////////////////////////////////////////////////////////
// SUBCURVE_NODE
///////////////////////////////////////////////////////////////////////////
class Subcurve_node : public Base_node,
public In_place_list_base<Subcurve_node>
{
#ifndef CGAL_CFG_USING_BASE_MEMBER_BUG_3
protected:
using Base_node::cv_wrap;
#endif
public:
friend class Arrangement_2<Dcel,Traits,Base_node>;
//to enable access of Overlap_iterators into begin_child and past_end_child
//friend class Overlap_circulator;
//friend class Overlap_const_circulator;
//the above are not recognized by MSVC, so we use this instead
friend class
Arr_overlap_circulator<Edge_node,Edge_iterator,
Bidirectional_circulator_tag>;
friend class
Arr_overlap_const_circulator<Edge_node,Edge_const_iterator,
Bidirectional_circulator_tag>;
Subcurve_node(int construct_curve=1) : ftr(0),begin_child(0),
past_end_child(0)
{
if(construct_curve)
cv_wrap.x_cv=new X_monotone_curve_2;
}
virtual ~Subcurve_node() {}
virtual bool is_edge_node() const { return false; }
Subcurve_iterator parent() { return Subcurve_iterator(ftr); }
Subcurve_const_iterator parent() const
{ return Subcurve_const_iterator(ftr); }
Subcurve_iterator children_begin()
{ return Subcurve_iterator(begin_child); }
Subcurve_const_iterator children_begin() const
{ return Subcurve_const_iterator(begin_child); }
Subcurve_iterator children_end()
{ return Subcurve_iterator(past_end_child); }
Subcurve_const_iterator children_end() const
{ return Subcurve_const_iterator(past_end_child); }
Curve_iterator curve_node()
{
Subcurve_node * curr = this;
while (curr->ftr)
curr = curr->ftr;
return Curve_iterator(curr);
}
Curve_const_iterator curve_node() const
{
const Subcurve_node * curr = this;
while (curr->ftr)
curr = curr->ftr;
return Curve_const_iterator(curr);
}
Edge_iterator edges_begin() {
Subcurve_node* curr=this;
while (!curr->is_edge_node())
curr = curr->begin_child;
return Edge_iterator(curr);
}
Edge_const_iterator edges_begin() const
{
const Subcurve_node * curr = this;
while (!curr->is_edge_node())
curr = curr->begin_child;
return Edge_const_iterator(curr);
}
Edge_iterator edges_end()
{
Subcurve_node * curr = this;
while (!curr->is_edge_node())
//curr will never be a past_end_value:
curr = curr->past_end_child->prev_link;
return Edge_iterator(curr->next_link);
}
Edge_const_iterator edges_end() const
{
const Subcurve_node * curr = this;
while (!curr->is_edge_node())
curr=curr->past_end_child->prev_link;
return Edge_const_iterator(curr->next_link);
}
//the set_curve is not protected. how do I protect it? (maybe friend the
//arrangement and make it protected?)
protected:
Subcurve_node * ftr;
Subcurve_node * begin_child;
Subcurve_node * past_end_child;
};
////////////////////////////////////////////////////////////////////
// EDGE_NODE
////////////////////////////////////////////////////////////////////
class Edge_node : public Subcurve_node
{
public:
friend class Arrangement_2<Dcel,Traits,Base_node>;
//need to make them friend of Subcurve_node and not Edge_node
//friend class Overlap_circulator;
//friend class Overlap_const_circulator;
Edge_node() : Subcurve_node(), hdg()
{
//the following is needed for the circular overlap list (see the function
//push_in_edge_list below). if we want to implement a linear list
//it needs to be removed (begin_child and past_end_child should then be
//NULL)
this->begin_child = this;
this->past_end_child = this;
}
~Edge_node() {} //overrides the virtual dtr in Subcurve node
Halfedge_handle halfedge() { return hdg; }
Halfedge_const_handle halfedge() const { return hdg; }
bool is_edge_node() const { return true; }
private: //maybe protected
// void set_halfedge(Halfedge_const_handle h) {hdg=h;}
void set_halfedge(Halfedge_handle h) { hdg = h; }
private:
Halfedge_handle hdg;
};
///////////////////////////////////////////////////////////////////////////
// CURVE_NODE
///////////////////////////////////////////////////////////////////////////
class Curve_node : public Subcurve_node
{
public:
friend class Arrangement_2<Dcel,Traits,Base_node>;
Curve_node() : Subcurve_node(0), levels(), edge_level()
{
this->cv_wrap.cv = new Curve_2;
}
~Curve_node() {} //overrides the virtual dtr in Subcurve_node
//number of subcurve levels (not including curve level and edge level)
unsigned int number_of_sc_levels() const {
return levels.size();
}
Subcurve_iterator level_begin(unsigned int i)
{
CGAL_precondition(i<number_of_sc_levels());
return levels[i].begin();
}
Subcurve_const_iterator level_begin(unsigned int i) const
{
CGAL_precondition(i<number_of_sc_levels());
return levels[i].begin();
}
Subcurve_iterator level_end(unsigned int i)
{
CGAL_precondition(i<number_of_sc_levels());
return levels[i].end();
}
Subcurve_const_iterator level_end(unsigned int i) const
{
CGAL_precondition(i<number_of_sc_levels());
return levels[i].end();
}
//we override the function to make it more efficient when called from
//Curve_node
Edge_iterator edges_begin() { return edge_level.begin(); }
Edge_const_iterator edges_begin() const { return edge_level.begin(); }
Edge_iterator edges_end() { return edge_level.end(); }
Edge_const_iterator edges_end() const { return edge_level.end(); }
private:
std::vector<In_place_list<Subcurve_node,true> > levels;
//level0 is the one beneath the root
In_place_list<Subcurve_node,true> edge_level;
};
//Planar map wrappers
//halfedge : Pm::Halfedge + hides pointer into iterator (and adds curve node)
//face : Pm::Face + returns Arr::Halfedge and not Pm::Halfedge etc.
//Vertex : Pm::Vertex + returns Arr::Halfedge and not Pm::Halfedge etc.
//////////////////////////////////////////////////////////////////////
// VERTEX
//////////////////////////////////////////////////////////////////////
class Vertex : public Planar_map::Vertex
{
public:
typedef typename Planar_map::Vertex PmVertex;
Vertex() : PmVertex() {}
//can also be PmVertex(v)
Vertex(PmVertex * v) : PmVertex(*v) {}
Vertex(PmVertex & v) : PmVertex(v) {}
bool is_incident_edge(Halfedge_const_handle e) const
{ return (PmVertex::is_incident_edge(e.current_iterator())); }
bool is_incident_face(Face_const_handle f) const
{ return (PmVertex::is_incident_face(f.current_iterator())); }
/*redundant - use inheritance
int degree() const
{
return PmVertex::degree();
}*/
Halfedge_around_vertex_circulator incident_halfedges()
{
return Halfedge_around_vertex_circulator
(Halfedge_handle(PmVertex::incident_halfedges()));
}
Halfedge_around_vertex_const_circulator incident_halfedges() const
{
return Halfedge_around_vertex_const_circulator
(Halfedge_const_handle(PmVertex::incident_halfedges()));
}
};
///////////////////////////////////////////////////////////////////////
// HALFEDGE
//////////////////////////////////////////////////////////////////////
class Halfedge : public Planar_map::Halfedge
{
public:
friend class Arrangement_2<Dcel,Traits,Base_node>;
typedef typename Planar_map::Halfedge PmHalfedge;
Halfedge() : Planar_map::Halfedge() {}
Halfedge(typename Planar_map::Halfedge *e) : Planar_map::Halfedge(*e) {}
Halfedge(typename Planar_map::Halfedge& e) : Planar_map::Halfedge(e) {}
Vertex_handle source()
{ return Vertex_handle(PmHalfedge::source()); }
Vertex_const_handle source() const
{ return Vertex_const_handle(PmHalfedge::source()); }
Vertex_handle target()
{ return Vertex_handle(PmHalfedge::target()); }
Vertex_const_handle target() const
{ return Vertex_const_handle(PmHalfedge::target()); }
Face_handle face()
{ return Face_handle(PmHalfedge::face()); }
Face_const_handle face() const
{ return Face_const_handle(PmHalfedge::face()); }
Halfedge_handle twin()
{ return Halfedge_handle(PmHalfedge::twin()); }
Halfedge_const_handle twin() const
{ return Halfedge_const_handle(PmHalfedge::twin()); }
Halfedge_handle next_halfedge()
{ return Halfedge_handle(PmHalfedge::next_halfedge()); }
Halfedge_const_handle next_halfedge() const
{ return Halfedge_const_handle(PmHalfedge::next_halfedge()); }
Ccb_halfedge_circulator ccb()
{ return Ccb_halfedge_circulator(Halfedge_handle(PmHalfedge::ccb())); }
Ccb_halfedge_const_circulator ccb() const
{
return Ccb_halfedge_const_circulator
(Halfedge_const_handle(PmHalfedge::ccb()));
}
Edge_iterator edge_node()
{
return Edge_iterator
(Subcurve_iterator
(static_cast<Subcurve_node*>(PmHalfedge::edge_node())));
}
Edge_const_iterator edge_node() const
{
return Edge_const_iterator
(Subcurve_const_iterator
(static_cast<const Subcurve_node*>(PmHalfedge::edge_node())));
}
//Overlap traversal
Overlap_circulator overlap_edges()
{ return Overlap_circulator(edge_node()); }
Overlap_const_circulator overlap_edges() const
{ return Overlap_const_circulator(edge_node()); }
//the curve and set curve functions in the base classes
//will be required to be blank. maybe thats a problem with
//other functions of the pm that we use here (check it out)
//is there a better solution ?
protected: //(private?)
void set_edge_node(Edge_node* b) {PmHalfedge::set_edge_node(b);}
private:
//disallow this function - allowed only for an Edge_node
//this overloading works for egcs, if doesn't work for other
//compilers then this will be the only version .
void set_edge_node(Base_node* b) {PmHalfedge::set_edge_node(b);}
};
///////////////////////////////////////////////////////////////////
// FACE
//////////////////////////////////////////////////////////////////
class Face : public Planar_map::Face
{
public:
typedef typename Planar_map::Face PmFace;
#ifndef _MSC_VER
// the following two typedefs are needed for compilation on irix64 (CC7.30)
typedef typename Arrangement_2<_Dcel,_Traits,Base_node>::Holes_iterator
Holes_iterator;
typedef typename
Arrangement_2<_Dcel,_Traits,Base_node>::Holes_const_iterator
Holes_const_iterator;
#endif
Face() : PmFace() {}
Face(PmFace *f) : PmFace(*f) {}
Face(PmFace& f) : PmFace(f) {}
/* redundant - use inheritance
bool is_unbounded() const
{
// face is not bounded iff it has no outer boundary
return (dface::halfedge() == NULL);
}
*/
Holes_iterator holes_begin()
{ return Holes_iterator(PmFace::holes_begin()); }
Holes_const_iterator holes_begin() const
{ return Holes_const_iterator(PmFace::holes_begin()); }
Holes_iterator holes_end()
{ return Holes_iterator(PmFace::holes_end()); }
Holes_const_iterator holes_end() const
{ return Holes_const_iterator(PmFace::holes_end()); }
bool is_halfedge_on_inner_ccb(Halfedge_const_handle e) const
{ return PmFace::is_halfedge_on_inner_ccb(e.current_iterator()); }
bool is_halfedge_on_outer_ccb(Halfedge_const_handle e) const
{ return PmFace::is_halfedge_on_outer_ccb(e.current_iterator()); }
//redundant - use inheritance
/*
bool does_outer_ccb_exist() const
{
return PmFace::does_outer_ccb_exist();
}*/
Halfedge_handle halfedge_on_outer_ccb()
{
typename Planar_map::Halfedge_handle pmh =
PmFace::halfedge_on_outer_ccb();
return Halfedge_handle(pmh);
}
Halfedge_const_handle halfedge_on_outer_ccb() const
{
typename Planar_map::Halfedge_const_handle pmh =
PmFace::halfedge_on_outer_ccb();
return Halfedge_const_handle(pmh);
}
Ccb_halfedge_circulator outer_ccb()
{ return (halfedge_on_outer_ccb())->ccb(); }
Ccb_halfedge_const_circulator outer_ccb() const
{ return (halfedge_on_outer_ccb())->ccb(); }
};
//////////////////////////////////////////////////////////
// ARRANGEMENT 2
///////////////////////////////////////////////////////////
public:
//in future need to arrange for the pl to be an Arr_pl,
//and public for the arrangement
/*
//for the first public release we use the default ctr below (with walk pl) -
//currently it is faster
Arrangement_2(const Traits& tr=Traits()) : traits(tr), pm(tr),
//do_update(true) {
last_updated=curve_node_end();
}
*/
//default ctr with the walk as default point location
Arrangement_2() : pm(Traits(), new WalkPL), do_update(true)
{
//new Traits_wrap(tr)
last_updated=curve_node_end();
use_delete_pl=true; //a bool flag for dtr
traits = (Traits_wrap *)(&pm.get_traits());
use_delete_traits = false;
}
Arrangement_2(const Traits& tr, Pm_point_location_base<Planar_map> * pl_ptr)
: pm(Traits(), pl_ptr), do_update(true)
{
last_updated=curve_node_end();
use_delete_pl = false; //a bool flag for dtr
traits = (Traits_wrap *)(&pm.get_traits());
use_delete_traits = false;
}
Arrangement_2(Pm_point_location_base<Planar_map> * pl_ptr)
: pm(pl_ptr), do_update(true)
{
last_updated = curve_node_end();
use_delete_pl=false;
traits = (Traits_wrap *)(&pm.get_traits());
use_delete_traits = false;
}
/*! Copy constructor.
*/
Arrangement_2(const Self & arr) : pm(arr.pm), do_update(true)
{
last_updated = curve_node_end();
use_delete_pl = false; //a bool flag for dtr
// these traits is the newly allocated traits for pm.
traits = (Traits_wrap *)(&pm.get_traits());
use_delete_traits = false;
copy_hierarchy_tree(arr);
}
/*
Arrangement_2(Traits_wrap * tr_ptr, Pm_point_location_base<Self> * pl_ptr)
: pm(tr_ptr, pl_ptr, NULL), do_update(true)
{
last_updated=curve_node_end();
traits = (Traits_wrap *)(&pm.get_traits());
use_delete_pl = false;
use_delete_traits = false;
}
*/
/*! Destructor
* need to delete the walk
*/
~Arrangement_2()
{
if (use_delete_pl)
//casting away the constness before deletion :
delete(const_cast<Pm_point_location_base<Planar_map>*>
(pm.get_point_location()));
if (use_delete_traits)
delete traits;
}
Self & operator=(const Self & arr)
{
pm = arr.pm;
copy_hierarchy_tree(arr);
return *this;
}
/////////////////////////////////////////////////////////////////////////////
// Reading Arrangement functions.
////////////////////////////////////////////////////////////////////////////
bool read (std::istream & in)
{
clear();
Arr_file_scanner<Self> scanner(in);
return scan_arr(scanner);
}
template <class Scanner>
bool read (std::istream & in, Scanner & scanner)
{
clear();
return scan_arr(scanner);
}
Traits & get_traits(){return * traits;}
const Traits & get_traits() const {return * traits;}
const Pmwx & get_planar_map() const {return pm;}
public:
Curve_iterator curve_node_begin()
{ return Curve_iterator(curve_list.begin()); }
Curve_const_iterator curve_node_begin() const
{ return Curve_const_iterator(curve_list.begin()); }
Curve_iterator curve_node_end()
{ return Curve_iterator(curve_list.end()); }
Curve_const_iterator curve_node_end() const
{ return Curve_const_iterator(curve_list.end()); }
Halfedge_iterator halfedges_begin()
{ return Halfedge_iterator(pm.halfedges_begin()); }
Halfedge_const_iterator halfedges_begin() const
{ return Halfedge_const_iterator(pm.halfedges_begin()); }
Halfedge_iterator halfedges_end()
{ return Halfedge_iterator(pm.halfedges_end()); }
Halfedge_const_iterator halfedges_end() const
{ return Halfedge_const_iterator(pm.halfedges_end()); }
Vertex_iterator vertices_begin()
{ return Vertex_iterator(pm.vertices_begin()); }
Vertex_const_iterator vertices_begin() const
{ return Vertex_const_iterator(pm.vertices_begin()); }
Vertex_iterator vertices_end()
{ return Vertex_iterator(pm.vertices_end()); }
Vertex_const_iterator vertices_end() const
{ return Vertex_const_iterator(pm.vertices_end()); }
Face_iterator faces_begin()
{ return Face_iterator(pm.faces_begin()); }
Face_const_iterator faces_begin() const
{ return Face_const_iterator(pm.faces_begin()); }
Face_iterator faces_end()
{ return Face_iterator(pm.faces_end()); }
Face_const_iterator faces_end() const
{ return Face_const_iterator(pm.faces_end()); }
Size number_of_faces() const { return pm.number_of_faces(); }
//counts every halfedge (i.e always even)
Size number_of_halfedges() const { return pm.number_of_halfedges(); }
Size number_of_vertices() const { return pm.number_of_vertices(); }
Size number_of_curve_nodes() const { return curve_list.size(); }
Face_handle unbounded_face() { return Face_handle(pm.unbounded_face()); }
Face_const_handle unbounded_face() const
{ return Face_const_handle(pm.unbounded_face()); }
//checks validity of planar map and arrangement's hierarchy tree structures
bool is_valid(bool verbose = false) const
{
CGAL::Verbose_ostream verr(verbose);
//std::ostream& verr = std::cerr;
bool valid = true;
verr << std::endl;
verr << "CGAL::Arrangment_2<Decl, Traits, Base_Node>::";
verr << "is_valid( true ):" << std::endl;
// Planar Map Check
verr << "a) planar_map check... " << std::endl;
if (pm.is_valid())
verr << "passed." << std::endl;
else
valid = false;
// Check each Curve Hierarchy tree
Curve_const_iterator cit;
Edge_const_iterator eit;
Subcurve_const_iterator sit, child_it, parent_it;
unsigned curve_counter = 1;
bool
curve_node_curve_node = true,
curve_node_is_edge_node = true,
curve_node_null_parent = true,
curve_node_children_parent = true,
curve_node_children_curve_node = true,
edge_is_edge_node = true,
edge_node_curve_node = true,
subcurve_is_edge_node = true,
subcurve_curve_node = true,
subcurve_edges_curve_node = true,
subcurve_edges_parent = true,
level_structure_ok = true,
not_curve_node,
circ_curve_is_next_curve = true,
circ_curve_is_halfedge_curve = true,
edge_curve_is_halfedge_curve = true;
verr << "b) hierarchy tree check:" << std::endl;
// for each curve tree
for (cit = curve_node_begin(); cit != curve_node_end();
cit++, curve_counter++) {
// check curve node properties
// ---------------------------
// is_edge_node() should return false for a Curve_node
curve_node_is_edge_node &= (cit->is_edge_node() == false);
// curve_node() should point at this current curve
curve_node_curve_node &= (cit->curve_node() == cit);
// parent() should return NULL
curve_node_null_parent &= (cit->parent() == NULL);
// children's parent should equal this curve node
sit = cit->children_begin();
for (;sit != cit->children_end(); sit++)
{
curve_node_children_curve_node &= (sit->curve_node() == cit);
//parent() always returns Subcurve_iterator while cit is of type
// Curve_iterator. to check that a child's parent indeed points at cit
// I use the following combined test
curve_node_children_parent &= (sit->parent()->parent() == NULL &&
sit->parent()->curve_node() == cit);
}
// check edges properties
// ----------------------
eit = cit->edges_begin();
for (;eit != cit->edges_end(); eit++) {
// is_edge_node() should return true for an edge node
edge_is_edge_node &= (eit->is_edge_node() == true);
// edged mutual reference check
edge_node_curve_node &= eit->curve_node() == cit;
// checking the vaildity of overlappings.
Overlap_const_circulator ovlp_circ = eit->halfedge()->overlap_edges();
edge_curve_is_halfedge_curve &=
(traits->curve_equal(eit->x_curve(), eit->halfedge()->curve()));
do {
Overlap_const_circulator next = ovlp_circ;
++next;
circ_curve_is_next_curve &=
traits->curve_equal(ovlp_circ->x_curve(), next->x_curve());
circ_curve_is_halfedge_curve &=
(traits->curve_equal(ovlp_circ->x_curve(),
eit->halfedge()->curve()));
} while (++ovlp_circ != eit->halfedge()->overlap_edges());
}
// check subcurves properties
// --------------------------
int i, levels;
levels = cit->number_of_sc_levels();
if (levels > 0) {
for (i = 0; i < levels; i++) {
sit = cit->level_begin(i);
// check that level i is indeed i deep in this tree
// go up to curve node i times, expect not too find parent
// not too soon, not too late
int j;
for (j = i, not_curve_node = true, parent_it = sit;
j >= 0 && not_curve_node;
j--, parent_it = parent_it->parent())
{
// parent found too soon?
if (parent_it->parent() == NULL) not_curve_node = false;
}
level_structure_ok &= not_curve_node;
// parent found too late :
level_structure_ok &= (parent_it->parent()==NULL);
// for each subcurve in level i
for (;sit != cit->level_end(i) ; sit++) {
// is_edge_node() should return false for a Subcurve_node
subcurve_is_edge_node &= (sit->is_edge_node() == false);
// subcurve - curve check
subcurve_curve_node &= (sit->curve_node() == cit);
// subcurve - edge check
eit = sit->edges_begin();
for (;eit != sit->edges_end(); eit++) {
// ADD CHECK TO PARENT() !!
subcurve_edges_curve_node &= eit->curve_node() == cit;
}
child_it = sit->children_begin();
for (;child_it != sit->children_end(); child_it++) {
// ADD CHECK TO PARENT() !!
subcurve_edges_parent &= (child_it->parent() == sit);
}
} // for (;sit != ...
} // for (i = 0 ...
} // if
}
verr << std::endl;
verr << "let cn denote the root Curve_node of the ";
verr << "arrangement hierarchy tree," << std::endl;
verr << " sn denote a Subcurve_node in that tree," << std::endl;
verr << "and en denote an Edge_node in that tree." << std::endl;
verr << "(&x stands for an iterator that points at x)" << std::endl;
verr << std::endl;
verr << "Curve checks:" << std::endl;
verr <<
"for all cn : cn.is_edge_node() == false ---";
verr << (curve_node_is_edge_node ? "PASS" : "FAIL") << std::endl;
verr <<
"for all cn : cn.curve_node() == &cn ---";
verr << (curve_node_curve_node ? "PASS" : "FAIL") << std::endl;
verr <<
"for all cn : cn.parent() == NULL ---";
verr << (curve_node_null_parent ? "PASS" : "FAIL") << std::endl;
verr <<
"for all children ch of cn : ch.curve_node_node() == &cn ---";
verr << (curve_node_children_curve_node ? "PASS" : "FAIL") << std::endl;
verr <<
"for all children ch of cn : ch.parent() is indeed cn ---";
verr << (curve_node_children_parent ? "PASS" : "FAIL") << std::endl;
verr <<
"level i is indeed i deep in tree ---";
verr << (level_structure_ok ? "PASS" : "FAIL") << std::endl;
verr << std::endl;
verr << "Subcurve checks:" << std::endl;
verr <<
"for all sn : sn.is_edge_node() == false ---";
verr << (subcurve_is_edge_node ? "PASS" : "FAIL") << std::endl;
verr <<
"for all sn : sn->curve_node() == &cn ---";
verr << (subcurve_curve_node ? "PASS" : "FAIL") << std::endl;
verr <<
"for all en in an sn subtree: en->curve_node() == &cn ---";
verr << (subcurve_edges_curve_node ? "PASS" : "FAIL") << std::endl;
verr <<
"for each child ch of sn : ch->parent() == &sn ---";
verr << (subcurve_edges_curve_node ? "PASS" : "FAIL") << std::endl;
verr << std::endl;
verr << "Edge checks:" << std::endl;
verr <<
"for all en : en.is_edge_node() == true ---";
verr << (edge_is_edge_node ? "PASS" : "FAIL") << std::endl;
verr <<
"for all en : en->curve_node() == &cn ---";
verr << (edge_node_curve_node ? "PASS" : "FAIL") << std::endl;
verr <<
"for all en : en->curve() == en->halfedge()->curve() ---";
verr << (edge_curve_is_halfedge_curve ? "PASS" : "FAIL") << std::endl;
verr <<
"for all en : all overlapping circulators have the same curve ---";
verr << (circ_curve_is_next_curve ? "PASS" : "FAIL") << std::endl;
verr <<
"for all en : all circulators curves == en->halfedge()->curve() ---";
verr << (circ_curve_is_halfedge_curve ? "PASS" : "FAIL") << std::endl;
valid =
valid &
curve_node_curve_node &
curve_node_is_edge_node &
curve_node_null_parent &
curve_node_children_parent &
curve_node_children_curve_node &
edge_is_edge_node &
edge_node_curve_node &
subcurve_is_edge_node &
subcurve_curve_node &
subcurve_edges_curve_node &
subcurve_edges_parent &
level_structure_ok &
edge_curve_is_halfedge_curve &
circ_curve_is_next_curve &
circ_curve_is_halfedge_curve;
// Final Result
verr << std::endl;
if (valid)
verr << " object is valid! " << std::endl;
else
verr << "object is INVALID!" << std::endl;
verr << "------------------" << std::endl;
return valid;
}
///////////////////////////////////////////////////////////////////
// INSERTION FUNCTIONS
Curve_iterator insert_from_vertex(const Curve_2 & cv,
Vertex_handle src,
Change_notification * en = NULL)
{
CGAL_precondition(traits->point_equal(src->point(),
traits->curve_source(cv)));
CGAL_precondition(!traits->point_equal(traits->curve_source(cv),
traits->curve_target(cv)) ||
!traits->is_x_monotone(cv));
//either add Arr to pm as friend class or make public functions
Curve_node* cn= new Curve_node;
cn->set_curve(cv);
if (!traits->is_x_monotone(cv)) {
//get an x_monotone sub_curve list and push it in.
cn->levels.push_back(In_place_list<Subcurve_node,true>());
//cut cv into x_monotone curves and insert them into l
std::list<typename Traits::X_curve> x_list;
traits->curve_make_x_monotone(cv, std::back_inserter(x_list));
typename std::list<typename Traits::X_curve>::iterator
lit=x_list.begin();
for (; lit!=x_list.end(); ++lit) {
Subcurve_node* scn=new Subcurve_node;
scn->ftr=cn;
scn->set_x_monotone_curve(*lit);
cn->levels[0].push_back(*scn);
}
cn->begin_child=&(*(cn->levels[0].begin()));
cn->past_end_child=&(*(cn->levels[0].end()));
//so far - inserted subcurve level, we insert the edge level only if
// we are in update mode.
if (do_update) {
Vertex_handle curr_v = src;
Subcurve_iterator scit=cn->levels[0].begin();
In_place_list<Subcurve_node,true> edge_list;
for (; scit!=cn->levels[0].end(); ++scit) {
Arr_hierarchy_ops aho(this, edge_list, &(*scit), en);
Halfedge_handle h = pm.insert_from_vertex
(scit->curve(), curr_v.current_iterator(), &aho);
curr_v = h->target(); // vertex for next insertion
scit->begin_child=&(*(edge_list.begin()));
//add edge_list at end of edge_level :
cn->edge_level.splice(cn->edge_level.end(),edge_list);
}
scit=cn->levels[0].begin();
Subcurve_iterator aux=scit; ++aux;
for (; aux!=cn->levels[0].end(); ++scit,++aux) {
scit->past_end_child=&(*(aux->begin_child));
}
//the last past_end_child :
scit->past_end_child=&(*(cn->edge_level.end()));
} //if (do_update)
}
else { //insert x_curve directly - sub_curve vector is empty
if (do_update) { //insertion of edge level only if in update mode
Arr_hierarchy_ops aho(this, cn->edge_level, cn, en);
pm.insert_from_vertex(cv, src.current_iterator(), &aho);
cn->past_end_child=&(*(cn->edge_level.end()));
cn->begin_child=&(*(cn->edge_level.begin()));
}
}
Curve_iterator ci=curve_list.insert(curve_list.end(),*cn);
if (do_update)
last_updated=ci;
return ci;
}
Curve_iterator insert(const Curve_2 & cv, Change_notification * en = NULL)
{
//either add Arr to pm as friend class or make public functions
Curve_node* cn= new Curve_node;
cn->set_curve(cv);
//get an x_monotone sub_curve list and push it in.
cn->levels.push_back(In_place_list<Subcurve_node,true>());
//cut cv into x_monotone curves and insert them into l
std::list<typename Traits::X_curve> x_list;
traits->curve_make_x_monotone(cv, std::back_inserter(x_list));
typename std::list<typename Traits::X_curve>::iterator
lit=x_list.begin();
for (; lit!=x_list.end(); ++lit) {
Subcurve_node* scn=new Subcurve_node;
scn->ftr=cn;
scn->set_x_monotone_curve(*lit);
cn->levels[0].push_back(*scn);
}
cn->begin_child=&(*(cn->levels[0].begin()));
cn->past_end_child=&(*(cn->levels[0].end()));
//so far - inserted subcurve level, we insert the edge level only if
// we are in update mode.
if (do_update) {
Vertex_handle curr_v;
Halfedge_handle h;
bool first_insert(true);
Subcurve_iterator scit=cn->levels[0].begin();
In_place_list<Subcurve_node,true> edge_list;
for (; scit!=cn->levels[0].end(); ++scit) {
Arr_hierarchy_ops aho(this, edge_list, &(*scit), en);
if (first_insert) {
typename Planar_map::Vertex_handle src, tgt;
h = pm.insert_intersecting_xcurve(scit->x_curve(), src, tgt, false, &aho);
first_insert = false;
}
else {
typename Planar_map::Vertex_handle src(curr_v.current_iterator()), tgt;
h = pm.insert_intersecting_xcurve(scit->x_curve(), src, tgt, true, &aho);
}
curr_v = h->target(); // vertex for next insertion
scit->begin_child=&(*(edge_list.begin()));
//add edge_list at end of edge_level :
cn->edge_level.splice(cn->edge_level.end(),edge_list);
}
scit=cn->levels[0].begin();
Subcurve_iterator aux=scit; ++aux;
for (; aux!=cn->levels[0].end(); ++scit,++aux) {
scit->past_end_child=&(*(aux->begin_child));
}
//the last past_end_child :
scit->past_end_child=&(*(cn->edge_level.end()));
} //if (do_update)
Curve_iterator ci=curve_list.insert(curve_list.end(),*cn);
if (do_update)
last_updated=ci;
return ci;
}
/////////////////////////////////////////////////////////////////////
// insertion with user defined intersection functions
template <class F_iterator>
Curve_iterator insert(const Curve_2 & cv,
F_iterator F_begin,
F_iterator F_end,
Change_notification * en = NULL)
{
if (F_begin==F_end)
return insert(cv); //if list is empty return regular insert function
Curve_node* cn= new Curve_node;
cn->set_curve(cv);
typename std::vector<In_place_list<Subcurve_node,true> >::size_type sz=0;
//distance(F_begin,F_end,sz);
//find size of vector of in place lists
//(currently not all STL distance is implemented same -
//so I implement it myself);
F_iterator first=F_begin;
while(first++!=F_end) ++sz;
//! the following line is _crucial_ to avoid unreferencing
//of the lists afterwards
cn->levels.reserve(sz);
//step 1: insert the first level of subcurves (level 0)
cn->levels.push_back(In_place_list<Subcurve_node,true>());
//cut cv into curves and insert them into l
std::list<Curve_2> c_list;
(*(*F_begin))(cv,c_list);
++F_begin;
typename std::list<Curve_2>::iterator lit=c_list.begin();
for (; lit!=c_list.end(); ++lit) {
Subcurve_node* scn=new Subcurve_node;
scn->ftr=cn;
scn->set_x_monotone_curve(*lit);
cn->levels[0].push_back(*scn);
}
cn->begin_child=&(*(cn->levels[0].begin()));
cn->past_end_child=&(*(cn->levels[0].end()));
//step 2: insert the rest of the levels of subcurves
//(until no more split functions)
int i=1; //current level
for (; F_begin!=F_end ; ++F_begin, ++i ) {
cn->levels.push_back(In_place_list<Subcurve_node,true>());
Subcurve_iterator scit=cn->levels[i-1].begin();
for (; scit!=cn->levels[i-1].end(); ++scit) {
//cut cv into curves and insert them into l
std::list<Curve_2> c_list;
(*(*F_begin))(scit->x_curve(),c_list); //split the curve
Subcurve_iterator aux=cn->levels[i].end();
if (!cn->levels[i].empty()) {
--aux;
}
typename std::list<Curve_2>::iterator lit=c_list.begin();
for (; lit!=c_list.end(); ++lit) {
Subcurve_node* scno=new Subcurve_node;
scno->ftr=&(*scit);
scno->set_x_monotone_curve(*lit);
cn->levels[i].push_back(*scno);
}
if (!cn->levels[i].empty()) {
++aux;
}
//the begin_child is the one directly after the last one of before.:
scit->begin_child=&(*aux);
}
(cn->levels[i-1].begin())->begin_child=&(*(cn->levels[i].begin()));
//the begin child of the first - now all begin children are well defined
//defining the past end child pointer of level[i-1]
scit=cn->levels[i-1].begin();
Subcurve_iterator aux=scit; ++aux;
for (; aux!=cn->levels[i-1].end(); ++scit,++aux) {
scit->past_end_child=&(*(aux->begin_child));
}
//the last past_end_child
scit->past_end_child=&(*(cn->levels[i].end()));
}
//ALL the subcurve levels are now inserted.
//step 3: insert the edge level.
if (do_update) {
Subcurve_iterator scit=cn->levels[i-1].begin();
In_place_list<Subcurve_node,true> edge_list;
for (; scit!=cn->levels[i-1].end(); ++scit) {
Arr_hierarchy_ops aho(this, edge_list, &(*scit), en);
pm.insert(scit->x_curve(), &aho);
scit->begin_child=&(*(edge_list.begin()));
//add edge_list at end of edge_level :
cn->edge_level.splice(cn->edge_level.end(),edge_list);
}
scit=cn->levels[i-1].begin();
Subcurve_iterator aux=scit; ++aux;
for (; aux!=cn->levels[i-1].end(); ++scit,++aux) {
scit->past_end_child=&(*(aux->begin_child));
}
//the last past_end_child :
scit->past_end_child=&(*(cn->edge_level.end()));
} //if (do_update)
//insert in curve list and return
Curve_iterator ci=curve_list.insert(curve_list.end(),*cn);
if (do_update)
last_updated=ci;
return ci;
}
///////////////////////////////////////////////////////////////
// SPLIT EDGE
//add a new edge_node after e->edge_node(), split the edge in the pm,
//update the curves and halfedge pointers in the nodes and halfedges
void handle_split_edge(Pm_halfedge_handle orig_edge,
Pm_halfedge_handle new_edge,
const typename Traits::X_curve& c1,
const typename Traits::X_curve& c2)
{
Halfedge_handle e = orig_edge;
Edge_iterator eit=e->edge_node();
Curve_iterator cit=eit->curve_node();
Edge_node* en=new Edge_node;
//!! bug fix (two weeks of debugging)
en->ftr=eit->ftr;
if (traits->point_equal(traits->curve_source(c1),
orig_edge->source()->point()))
{
en->set_x_monotone_curve(c2);
orig_edge->edge_node()->set_x_monotone_curve(c1);
}
else {
en->set_x_monotone_curve(c1);
orig_edge->edge_node()->set_x_monotone_curve(c2);
}
//insert en after eit in the edge_node list
++eit;
(cit->edge_level).insert(eit.current_iterator(),*en);
en->set_halfedge(Halfedge_handle(new_edge));
new_edge->set_edge_node(en);
new_edge->twin()->set_edge_node(en);
//deal with overlapping edges of eit (if there were any)
if (((Edge_node*)(orig_edge->edge_node()))->begin_child !=
(Subcurve_node*)&(*(orig_edge->edge_node())))
{
//eit has overlapping edges (it doesn't point to itself)
//split all overlapping edge_nodes and create the circular list of
//the edges corresponding to the new edge
Overlap_circulator occ= (Halfedge_handle(orig_edge))->overlap_edges();
++occ; //we have already dealt with the first edge
do {
//add a new edge before/after edge_iterator(occ);
//set its curve,ftr,begin_child,past_end_child,halfedge
eit=occ;
cit=eit->curve_node();
Edge_node* nen=new Edge_node;
nen->ftr=eit->ftr;
//insert nen into circular list before en
nen->begin_child=en->begin_child;
nen->past_end_child=en;
en->begin_child->past_end_child=nen;
en->begin_child=nen;
eit->set_x_monotone_curve(orig_edge->curve());
nen->set_x_monotone_curve(new_edge->curve());
//insert en before/after eit in the edge_node list
if (eit->halfedge()== Halfedge_handle(orig_edge->twin())) {
//eit is directed opposite orig_edge->edge_node()
//we take advantage of our knowledge of the pm
//split function to know this
nen->set_halfedge(Halfedge_handle(new_edge->twin()));
//en will be inserted before eit
}
else {
nen->set_halfedge(Halfedge_handle(new_edge));
++eit; //en should be inserted after eit
}
//insertion into the in_place edge list
(cit->edge_level).insert(eit.current_iterator(),*nen);
} while (++occ != (Halfedge_handle(orig_edge))->overlap_edges());
}
}
Halfedge_handle split_edge(Halfedge_handle e,
const typename Traits::X_curve& c1,
const typename Traits::X_curve& c2)
{
Edge_iterator eit = e->edge_node();
//find the representative halfedge of the edge node
//(the one with the same direction as the curve)
Halfedge_handle e_rep = eit->halfedge();
typename Planar_map::Halfedge_handle pmh =
pm.split_edge(e_rep.current_iterator(),c1,c2);
handle_split_edge(pmh, pmh->next_halfedge(), c1, c2);
return Halfedge_handle(pmh);
}
////////////////////////////
//LOCATE
////////////////////////////
Halfedge_handle locate(const typename Traits::Point_2& p,Locate_type& lt)
{
typename Planar_map::Locate_type pmlt;
typename Planar_map::Halfedge_handle pmh=pm.locate(p,pmlt);
switch(pmlt) {
case Planar_map::VERTEX :
//workaround since MSVC does not approve the automatic cast here :
lt=static_cast<Locate_type>(VERTEX);
break;
case Planar_map::EDGE :
lt=static_cast<Locate_type>(EDGE);
break;
case Planar_map::FACE :
lt=static_cast<Locate_type>(FACE);
break;
case Planar_map::UNBOUNDED_VERTEX :
lt=static_cast<Locate_type>(UNBOUNDED_VERTEX);
break;
case Planar_map::UNBOUNDED_EDGE :
lt=static_cast<Locate_type>(UNBOUNDED_EDGE);
break;
case Planar_map::UNBOUNDED_FACE :
lt=static_cast<Locate_type>(UNBOUNDED_FACE);
break;
}
return Halfedge_handle(pmh);
}
Halfedge_const_handle locate(const typename Traits::Point_2& p,
Locate_type& lt) const
{
typename Planar_map::Locate_type pmlt;
typename Planar_map::Halfedge_const_handle pmh=pm.locate(p,pmlt);
switch(pmlt) {
case Planar_map::VERTEX :
//workaround since MSVC does not approve the automatic cast here
lt = static_cast<Locate_type>(VERTEX);
break;
case Planar_map::EDGE :
lt = static_cast<Locate_type>(EDGE);
break;
case Planar_map::FACE :
lt = static_cast<Locate_type>(FACE);
break;
case Planar_map::UNBOUNDED_VERTEX :
lt = static_cast<Locate_type>(UNBOUNDED_VERTEX);
break;
case Planar_map::UNBOUNDED_EDGE :
lt = static_cast<Locate_type>(UNBOUNDED_EDGE);
break;
case Planar_map::UNBOUNDED_FACE :
lt = static_cast<Locate_type>(UNBOUNDED_FACE);
break;
}
return Halfedge_const_handle(pmh);
}
//////////////////////////////////////////////////////
// VERTICAL RAY SHOOT
//////////////////////////////////////////////////////
Halfedge_handle vertical_ray_shoot(const typename Traits::Point_2& p,
Locate_type& lt, bool up)
{
typename Planar_map::Locate_type pmlt;
typename Planar_map::Halfedge_handle pmh=pm.vertical_ray_shoot(p,pmlt,up);
switch(pmlt) {
case Planar_map::VERTEX :
//workaround since MSVC does not approve the automatic cast here :
lt = static_cast<Locate_type>(VERTEX);
break;
case Planar_map::EDGE :
lt = static_cast<Locate_type>(EDGE);
break;
case Planar_map::FACE :
lt = static_cast<Locate_type>(FACE);
break;
case Planar_map::UNBOUNDED_VERTEX :
lt = static_cast<Locate_type>(UNBOUNDED_VERTEX);
break;
case Planar_map::UNBOUNDED_EDGE :
lt = static_cast<Locate_type>(UNBOUNDED_EDGE);
break;
case Planar_map::UNBOUNDED_FACE :
lt = static_cast<Locate_type>(UNBOUNDED_FACE);
break;
}
return Halfedge_handle(pmh);
}
Halfedge_const_handle vertical_ray_shoot(const typename Traits::Point_2& p,
Locate_type& lt) const
{
typename Planar_map::Locate_type pmlt;
typename Planar_map::Halfedge_const_handle pmh =
pm.vertical_ray_shoot(p,pmlt);
switch(pmlt) {
case Planar_map::VERTEX :
//workaround since MSVC does not approve the automatic cast here :
lt = static_cast<Locate_type>(VERTEX);
break;
case Planar_map::EDGE :
lt = static_cast<Locate_type>(EDGE);
break;
case Planar_map::FACE :
lt = static_cast<Locate_type>(FACE);
break;
case Planar_map::UNBOUNDED_VERTEX :
lt = static_cast<Locate_type>(UNBOUNDED_VERTEX);
break;
case Planar_map::UNBOUNDED_EDGE :
lt = static_cast<Locate_type>(UNBOUNDED_EDGE);
break;
case Planar_map::UNBOUNDED_FACE :
lt = static_cast<Locate_type>(UNBOUNDED_FACE);
break;
}
return Halfedge_const_handle(pmh);
}
///////////////////////////////////////////////////////////////
// REMOVE CURVE
/////////////////////////////////////////////////////////////
//removes the curve ,its heirarchy tree, and the edges in the pm
void remove_curve(Curve_iterator cit)
{
Edge_iterator eit=cit->edges_begin();
for (; eit!=cit->edges_end(); ++eit) {
if (eit->begin_child == &(*eit)) { //no overlap
pm.remove_edge((eit->halfedge()).current_iterator()); //deletes edges
}
else { //eit overlaps - don't remove the halfedges from planar map
eit->begin_child->past_end_child=eit->past_end_child;
eit->past_end_child->begin_child=eit->begin_child;
//set the edge_node ptr of halfedges to something that is not deleted
eit->halfedge()->set_edge_node(eit->begin_child);
eit->halfedge()->twin()->set_edge_node(eit->begin_child);
}
}
typename std::vector<In_place_list<Subcurve_node,true> >::iterator
vit=(cit->levels).begin();
for (; vit!=(cit->levels).end(); ++vit)
(*vit).destroy(); //deletes subcurve lists
curve_list.erase(&(*cit)); //deletes from curve list
}
///////////////////////////////////////////////////////////////
// CLEAR
///////////////////////////////////////////////////////////////
void clear()
{
pm.clear();
for (Curve_iterator cv_iter = curve_node_begin();
cv_iter != curve_node_end();
cv_iter++){
// destroying all subcurves levels.
for (unsigned int i = 0; i < cv_iter->number_of_sc_levels(); i++)
cv_iter->levels[i].destroy();
// destroying edge node level.
cv_iter->edge_level.destroy();
}
curve_list.destroy();
}
///////////////////////////////////////////////////////////////
// UPDATE
///////////////////////////////////////////////////////////////
void set_update(bool u) {
do_update=u;
if (u) {
//go from last_updated to curve_node_end(), and insert x_curves
if (last_updated!=curve_node_end()) //for the very first update
++last_updated;
else
last_updated=curve_node_begin();
for (; last_updated!=curve_node_end(); ++last_updated) {
unsigned int num=last_updated->number_of_sc_levels();
if (num>0) {
In_place_list<Subcurve_node,true> edge_list;
Subcurve_iterator scit=last_updated->level_begin(num - 1);
for (; scit!=last_updated->level_end(num - 1); ++scit) {
Arr_hierarchy_ops aho(this, edge_list, &(*scit));
pm.insert(scit->x_curve(), &aho);
scit->begin_child=&(*(edge_list.begin()));
//add edge_list at end of edge_level :
last_updated->edge_level.splice(last_updated->edge_level.end(),
edge_list);
}
scit=last_updated->level_begin(num - 1);
Subcurve_iterator aux=scit; ++aux;
for (; aux!=last_updated->level_end(num-1); ++scit,++aux) {
scit->past_end_child=&(*(aux->begin_child));
}
//the last past_end_child :
scit->past_end_child=&(*(last_updated->edge_level.end()));
}
else { //num==0, no subcurve level, insert Curve directly.
Arr_hierarchy_ops aho(this,
last_updated->edge_level,
&(*last_updated));
pm.insert(last_updated->x_curve(), &aho);
last_updated->past_end_child=&(*(last_updated->edge_level.end()));
last_updated->begin_child=&(*(last_updated->edge_level.begin()));
}
}
//now last_update==curve_node_end() - take the one before
--last_updated;
}
}
// object given as a parameter to insert function of pmwx
// such that insert will not know about curve hirarchy
class Arr_hierarchy_ops : public Change_notification
{
public:
typedef Self Arr;
Arr_hierarchy_ops(Arr *arr_,
In_place_list<Subcurve_node,true>& edge_list_,
Subcurve_node* ftr_,
Change_notification *user_notifier_ = NULL ) :
arr(arr_), edge_list(edge_list_), ftr(ftr_),
user_notifier(user_notifier_)
{}
void add_edge(const typename Traits::X_curve& cv,
Pm_halfedge_handle e,
bool original_direction, bool overlap=false)
{
arr->push_in_edge_list(cv, e, ftr, edge_list, original_direction,
overlap);
if (user_notifier != NULL)
user_notifier->add_edge(cv, e, original_direction, overlap);
}
void split_edge(Pm_halfedge_handle orig_edge,
Pm_halfedge_handle new_edge,
const typename Traits::X_curve& c1,
const typename Traits::X_curve& c2)
{
arr->handle_split_edge(orig_edge, new_edge, c1, c2);
if (user_notifier != NULL)
user_notifier->split_edge(orig_edge, new_edge, c1, c2);
}
void split_face(Pm_face_handle orig_face, Pm_face_handle new_face)
{
if (user_notifier != NULL)
user_notifier->split_face(orig_face, new_face);
}
void add_hole(Pm_face_handle in_face, Pm_halfedge_handle new_hole)
{
if (user_notifier != NULL)
user_notifier->add_hole(in_face, new_hole);
}
// return in support_cv the suuporting curve of edge.
// if not avilable returns false
const typename Traits::X_curve &edge_support_curve(Pm_halfedge_handle edge)
{
Halfedge_handle arr_handle = edge;
return arr_handle->edge_node()->parent()->x_curve();
}
bool have_support_curve() { return true; }
Arr *arr;
In_place_list<Subcurve_node,true> &edge_list;
Subcurve_node* ftr;
Change_notification *user_notifier;
};
friend class Arr_hierarchy_ops;
// Pushes the curve cv corresponding to halfedge e to the edge_node_list
// push_back if original_direction
// push_front otherwise - will be called from insert after
// inserting cv into the pm and getting e
//
// *** Edge_node class:
// Edge_node holds a curve that is used also as the curve of its
// associated halfedge. There are two halfedges (an halfedge and its
// twin) which point to the Edge_node. The Edge_node contains a
// handle to one of these halfedges of which has the same orientation
// as the curve the Edge_node holds. Edge_node also contains two
// pointers named begin_child and past_end_child which are two
// pointers in a circulat list of all overlapping curves on the
// specific edge.
//
// *** Historical comment (Eti and Eyal, January 2002)
// original_direction was a boolean flag indicating whether cv and
// ftr->curve() have the same orientation. Pm_with_intersections
// calculated this value and passed it through the add_edge
// function of the notifier However, this value was miscalculated
// and had an error value. As a result, we do not use
// original_direction. Instead we compare the directions of cv and
// ftr->curve().
//
void push_in_edge_list(const typename Traits::X_curve& cv,
Pm_halfedge_handle phe,
Subcurve_node* ftr,
In_place_list<Subcurve_node,true>& edge_list,
bool /* original_direction */,
bool overlap=false)
{
Halfedge_handle e = phe;
Edge_node* en=new Edge_node;
en->ftr=ftr;
// The following condition replaces the original functionality
// of original_direction, as described in the histroial comment above.
// The original condition: if (original_direction)
if (traits->compare_xy(traits->curve_source(ftr->x_curve()),
traits->curve_target(ftr->x_curve())) ==
traits->compare_xy(traits->curve_source(cv),
traits->curve_target(cv)))
en->set_x_monotone_curve(cv);
else
en->set_x_monotone_curve(traits->curve_opposite(cv));
// DEALING WITH OVERLAP:
// We use the 2 redundant pointers - begin_child and past_end_child
// to create a circular linked list of overlapping edges (for the
// same halfedge)
// 2 options: circular bidircetionsl list(bi-circulator) ,
// or linear single directional list (forward iterator),
// bidirectional iterator can't be implemented because we can't
// have a sentinel for the past_the_end value.
//we implement below a bi-dircetional circular list, when no overlap
//en points at itself - this implies that the default ctr of the
//edge node has begin_child and past_end_child initialized to this
//(whereas if we implement a forward list, it is initialized to NULL).
if (overlap) {
//pointer shuffling to insert en into circular list
//past_end_child == next, begin_child == prev
Edge_node* aux=&(*e->edge_node());
en->past_end_child = aux;
en->begin_child = aux->begin_child;
aux->begin_child->past_end_child = en;
aux->begin_child = en;
}
else {
//initialization of circular list with en - not needed - done in the ctr
//en->past_end_child=en;
//en->begin_child=en;
}
//the following code should replace the above code if we want a single list
//if (overlap)
// en->past_end_child=&(*e->edge_node());
e->set_edge_node(en);
e->twin()->set_edge_node(en);
if (traits->point_equal(e->target()->point(),
traits->curve_target(en->x_curve())))
en->set_halfedge(Halfedge_handle(e));
else
en->set_halfedge(Halfedge_handle(e->twin()));
edge_list.push_back(*en);
}
//////////////////////////////////////////////////////////////////////////
// The following function is implemented for the Adaptive arr of Bezier
// curves - a local project that is not (currently) in CGAL.
//debug
//public:
protected:
//replace the subtree rooted at sc, with the list of curves cv_list
//then continue to subdivide with the rest of the levels.
//assumes sc is not a Curve_node and not an edge_node
template <class F_iterator>
Subcurve_iterator replace(Subcurve_iterator sc,
const std::list<Curve_2> & cv_list,
F_iterator F_begin,
F_iterator F_end)
{
Subcurve_node* cn= sc->ftr;
//define the level we're in and finding the curve_node (the root)
int level_number=-1;
Subcurve_node* curr = &(*sc);
while (curr->ftr) {
curr=curr->ftr;
++level_number;
}
Curve_iterator root(curr);
//step 0: define the past_end levels
std::vector<typename
In_place_list<Subcurve_node,true>::iterator > level_begin;
std::vector<typename
In_place_list<Subcurve_node,true>::iterator > level_end;
Edge_node* past_end_edge;
Edge_node* begin_edge;
Subcurve_iterator begin_aux=sc;
Subcurve_iterator end_aux=sc;
++end_aux;
level_end.push_back(end_aux); end_aux=(--end_aux)->children_end();
level_begin.push_back(begin_aux); begin_aux=begin_aux->children_begin();
while (!begin_aux->is_edge_node()) {
level_begin.push_back(begin_aux);
level_end.push_back(end_aux);
end_aux=(--end_aux)->children_end();
begin_aux=begin_aux->children_begin();
}
past_end_edge = (Edge_node*)(&(*(end_aux))); //use static_cast ?
begin_edge = (Edge_node*)(&(*begin_aux));
//step 1: insert the first level of subcurves (the one given in cv_list)
//do it with vector<inplacelist> and splice at the end
//will hold the new subtree
std::vector<In_place_list<Subcurve_node,true> > levels;
typename std::vector<In_place_list<Subcurve_node,true> >::size_type sz=0;
//distance(F_begin,F_end,sz); //find size of vector of in place lists
//(currently not all STL distance is implemented same -
//so I implement it myself);
F_iterator first=F_begin;
while(first++!=F_end) ++sz;
//!to avoid unreferencing of the lists afterwards
//(sz+1) because the first is also inserted into the vector
levels.reserve(sz+1);
levels.push_back(In_place_list<Subcurve_node,true>() );
typename std::list<Curve_2>::const_iterator
lit=cv_list.begin();
for (; lit!=cv_list.end(); ++lit) {
Subcurve_node* scn=new Subcurve_node;
scn->ftr=cn;
scn->set_x_monotone_curve(*lit);
levels[0].push_back(*scn);
}
//step 2: insert the rest of the levels of subcurves (until no more
//split functions)
int i=1; //current level
for (; F_begin!=F_end ; ++F_begin, ++i ) {
levels.push_back(In_place_list<Subcurve_node,true>());
Subcurve_iterator scit=levels[i-1].begin();
for (; scit!=levels[i-1].end(); ++scit) {
//cut cv into curves and insert them into l
std::list<Curve_2> c_list;
(*(*F_begin))(scit->curve(),c_list); //split the curve
Subcurve_iterator aux=levels[i].end();
--aux;
//aux keeps the last place we inserted before the coming insertion
typename std::list<Curve_2>::iterator
lit=c_list.begin();
for (; lit!=c_list.end(); ++lit) {
Subcurve_node* scn=new Subcurve_node;
scn->ftr=&(*scit);
scn->set_x_monotone_curve(*lit);
levels[i].push_back(*scn);
}
++aux;
scit->begin_child=&(*aux);
}
//the begin child of the first - now all begin children are well defined
(levels[i-1].begin())->begin_child=&(*(levels[i].begin()));
//defining the past end child pointer of level[i-1]
scit=levels[i-1].begin();
Subcurve_iterator aux=scit; ++aux;
for (; aux!=levels[i-1].end(); ++scit,++aux) {
scit->past_end_child=&(*(aux->begin_child));
}
}
//ALL the subcurve levels are now inserted.
//step 3: insert the edge level.
//first remove edges from pm then insert.
//assumes there will always be a pointer ctr for Edge_iterator
Edge_iterator start_edges(begin_edge), end_edges(past_end_edge);
while (start_edges!=end_edges) {
Edge_iterator tmp=start_edges++;
//pm.remove_edge((tmp->halfedge()).current_iterator());
//the previous line is replaced by the following to deal with overlaps
if (tmp->begin_child == &(*tmp)) { //no overlap
pm.remove_edge((tmp->halfedge()).current_iterator()); //deletes edges
//debug
//Ccb_halfedge_circulator cc= *(unbounded_face()->holes_begin());
//do {
//debug
//std::cout << "cc->face=" << &(*cc->face()) << " unbounded="
//<< &(*unbounded_face()) << std::endl;
//CGAL_assertion(cc->face()==unbounded_face());
//++cc;
//} while (cc != *(unbounded_face()->holes_begin()) );
//debug
//Face_handle ff=faces_begin();
//std::cout << "faces=" << &(*ff); ++ff;
//std::cout << " " << &(*ff) << std::endl;
}
else { //tmp overlaps - don't remove the halfedges from planar map
tmp->begin_child->past_end_child=tmp->past_end_child;
tmp->past_end_child->begin_child=tmp->begin_child;
//set the edge_node ptr of halfedges to something that is not deleted
tmp->halfedge()->set_edge_node(tmp->begin_child);
tmp->halfedge()->twin()->set_edge_node(tmp->begin_child);
}
}
In_place_list<Subcurve_node,true> edge_list;
Subcurve_iterator scit=levels[i-1].begin();
Subcurve_iterator aux;
for (; scit!=levels[i-1].end(); ++scit) {
In_place_list<Subcurve_node,true> el;
Arr_hierarchy_ops aho(this, el, &(*scit));
pm.insert(scit->curve(), &aho);
scit->begin_child=&(*(el.begin()));
edge_list.splice(edge_list.end(),el); //add el at end of edge_list
}
scit=levels[i-1].begin();
aux=scit; ++aux;
for (; aux!=levels[i-1].end(); ++scit,++aux) {
scit->past_end_child=&(*(aux->begin_child));
}
//step 4: insert the whole subtree back into its place and do the
//finish on the stitches
//number of levels in the new subtree is the same as in the old one :
CGAL_assertion((unsigned int)i==level_begin.size());
Subcurve_node* return_value = &(*levels[0].begin());
//step 4.1: replacing level[0]
//erasing the first node and replacing it with the new
//if sc was a first child then make the new one a first child :
if (sc==cn->children_begin()) {
cn->begin_child=&(*levels[0].begin());
//if cn is not a curve_node, need to update previous past-end-child :
if (cn->ftr!=0) {
Subcurve_iterator prev_cn=cn; --prev_cn;
prev_cn->past_end_child=&(*levels[0].begin());
}
}
(root->levels[level_number]).erase(level_begin[0],level_end[0]);
level_begin[0] = level_end[0]; --level_begin[0]; //keeping the one before
//insert the new level[0] into its place :
(root->levels[level_number]).splice(level_end[0],levels[0]);
//step 4.2: replacing the rest of the subcurve_levels
//erasing the subcurve levels and replacing them with the new
int k;
for (k=1; k<i; ++k) {
//erasure of old
(root->levels[k+level_number]).erase(level_begin[k],level_end[k]);
level_begin[k] = level_end[k]; --level_begin[k]; //keeping the one before
//for later use
//define the past-end-child of the node before the inserted in
//previous level
//maybe need to check before I do this if the node before
//(level_begin[k-1]) is not past-end of levels[k-1]
level_begin[k-1]->past_end_child=&(*(levels[k].begin()));
//insert the new level[k] into its place
(root->levels[level_number+k]).splice(level_end[k],levels[k]);
//define the past-end-child of last node inserted in the previous level
Subcurve_iterator prev_last=level_end[k-1];
--prev_last;
prev_last->past_end_child=&(*(level_end[k]));
}
//step 4.3: replacing the edge_level
//do the same for the edge_level
root->edge_level.erase(begin_edge,past_end_edge);
//define the past-end-child of node before the inserted in previous level
(level_begin[k-1])->past_end_child=&(*(edge_list.begin()));
//define the past-end-child of the last node inserted in the previous level
Subcurve_iterator prev_last=level_end[k-1];
--prev_last;
//prev_last->past_end_child=&(*(edge_level_end));
prev_last->past_end_child=&(*(past_end_edge));
//insert the new level[k] into its place
(root->edge_level).splice(past_end_edge,edge_list);
return Subcurve_iterator(return_value);
}
///////////////////////////////////////////////////////////////////////////
// Scanning Arrangement.
/////////////////////////////////////////////////////////////////////////
private:
void copy_hierarchy_tree(const Self& arr)
{
typedef std::map<const void*, void*> ConnectMap;
typedef std::map<void*, Halfedge_iterator> Pointer_halfedge_Map;
// mapping all halfedges pointers of the two arrangements.
ConnectMap cross_halfedges;
Halfedge_iterator h_iter1;
Halfedge_const_iterator h_iter2;
// we need this for overlapping edge nodes which share pointers to
// edge nodes on different hirarchies trees.
ConnectMap all_edges_map;
// assuming that the two containers are in the SAME order.
for (h_iter1 = halfedges_begin(), h_iter2 = arr.halfedges_begin();
h_iter1 != halfedges_end() && h_iter2 != arr.halfedges_end();
++h_iter1, ++h_iter2)
cross_halfedges.insert(ConnectMap::value_type((const void*) &(*h_iter2),
(void*) &(*h_iter1)));
// mapping the arrangement halfedges pointers to halfedges handles.
Pointer_halfedge_Map current_halfedges_pointers;
for (h_iter1 = halfedges_begin(); h_iter1 != halfedges_end(); ++h_iter1)
{
current_halfedges_pointers.insert
(Pointer_halfedge_Map::value_type((void*) &(*h_iter1), h_iter1));
}
// for each curve node
Curve_const_iterator cv_iter;
for (cv_iter = arr.curve_list.begin();
cv_iter != arr.curve_list.end();
++cv_iter)
{
// first creating the curve node.
Curve_node* cn = new Curve_node;
cn->assign(*cv_iter);
// creating subcurve nodes.
ConnectMap scn_map;
unsigned int i;
// for each level
for (i = 0; i < cv_iter->levels.size(); ++i)
{
// the current level to be created
In_place_list<Subcurve_node,true> level;
// for each subcurve node
Subcurve_const_iterator scv_iter;
for (scv_iter = cv_iter->levels[i].begin();
scv_iter != cv_iter->levels[i].end(); ++scv_iter){
Subcurve_node* scn = new Subcurve_node;
scn->assign(*scv_iter);
level.push_back(*scn);
}
// inserting the i'th level to current curve node.
cn->levels.push_back(level);
// copy the original items in cn->levels[i] - otherwise makes a
// copy. Notice that the vector of levels is NOT in place and
// hence mapping the scn pointers instead of the original values
// will cause a bug!.
Subcurve_iterator new_scv_iter;
for (scv_iter = cv_iter->levels[i].begin(),
new_scv_iter = cn->levels[i].begin();
scv_iter != cv_iter->levels[i].end() &&
new_scv_iter != cn->levels[i].end();
++scv_iter, ++new_scv_iter)
{
scn_map.insert(ConnectMap::value_type((const void*)&(*scv_iter),
(void*) &(*new_scv_iter)));
}
// Notice that arrangement uses the pointers of end() at each
// level, instead of the expected NULL pointer.
scn_map.insert(ConnectMap::value_type
((const void*) cv_iter->levels[i].end().operator->(),
(void*) (cn->levels[i].end().operator->()) ));
}
// creating edge nodes mapping, we use it (in spite we have
// all_edge_nodes) for efficientcy.
ConnectMap edge_map;
ConnectMap halfedge_edge_map;
Edge_const_iterator edge_iter;
for (edge_iter = cv_iter->edge_level.begin();
edge_iter != cv_iter->edge_level.end(); ++edge_iter){
Edge_node* en = new Edge_node;
en->assign(*edge_iter);
halfedge_edge_map.insert
(ConnectMap::value_type((const void*) &(*edge_iter),
(void*) &*(edge_iter->halfedge()) ));
cn->edge_level.push_back(*en);
}
Edge_iterator new_edge_iter;
for (edge_iter = cv_iter->edge_level.begin(),
new_edge_iter = cn->edge_level.begin();
edge_iter != cv_iter->edge_level.end() &&
new_edge_iter != cn->edge_level.end();
++edge_iter, ++new_edge_iter)
{
edge_map.insert(ConnectMap::value_type((const void*) &(*edge_iter),
(void*) &(*new_edge_iter)));
all_edges_map.insert(ConnectMap::value_type
((const void*) &(*edge_iter),
(void*) &(*new_edge_iter)));
}
edge_map.insert(ConnectMap::value_type
((const void*) cv_iter->edge_level.end().operator->(),
(void*) (cn->edge_level.end().operator->()) ));
all_edges_map.insert(ConnectMap::value_type
((const void*)cv_iter->
edge_level.end().operator->(),
(void*) (cn->edge_level.end().operator->()) ));
// updating all edge nodes vector - we need this for overlapping
// edge nodes which share pointers to edge nodes on different
// hirarchies trees.
// updating pointers between sub curve nodes.
for (i = 0; i < cv_iter->levels.size(); ++i) {
Subcurve_const_iterator scv_iter;
Subcurve_iterator new_scv_iter;
for (scv_iter = cv_iter->levels[i].begin(),
new_scv_iter = cn->levels[i].begin();
scv_iter != cv_iter->levels[i].end() &&
new_scv_iter != cn->levels[i].end();
++scv_iter, ++new_scv_iter)
{
Subcurve_node* scn = &*new_scv_iter;
// if it's the first level, than the father pointer is to the
// curve node cn;
if (i == 0)
scn->ftr = cn;
else {
Subcurve_node* scn_ftr =
(Subcurve_node*)
(scn_map.find((const void*) &*(scv_iter->ftr))->second);
scn->ftr = scn_ftr;
}
// if the level is not the last one.
if (i+1 < cv_iter->levels.size()) {
Subcurve_node* scn_begin_child =
(Subcurve_node*)(scn_map.find
((const void*) scv_iter->begin_child)->second);
scn->begin_child = scn_begin_child;
// pay attention to the fact that the past_end_child can be end().
Subcurve_node* scn_past_end_child =
(Subcurve_node*)
(scn_map.find((const void*) scv_iter->past_end_child)->second);
scn->past_end_child = scn_past_end_child;
}
else {
// last level - the next level is the edge node.
Edge_node* scn_begin_child =
(Edge_node*)
(edge_map.find((const void*) scv_iter->begin_child)->second);
scn->begin_child = scn_begin_child;
// pay attention to the fact that the past_end_child can be end()
Edge_node* scn_past_end_child =
(Edge_node*)
(edge_map.find((const void*) scv_iter->past_end_child)->second);
scn->past_end_child = scn_past_end_child;
}
}
}
// updating the father pointer of edge node.
new_edge_iter = cn->edge_level.begin();
edge_iter = cv_iter->edge_level.begin();
for (edge_iter = cv_iter->edge_level.begin(),
new_edge_iter = cn->edge_level.begin();
edge_iter != cv_iter->edge_level.end() &&
new_edge_iter != cn->edge_level.end();
++edge_iter, ++new_edge_iter)
{
Edge_node* en = &*new_edge_iter;
if (cn->levels.size() == 0)
en->ftr = cn;
else
en->ftr = (Subcurve_node*)
(scn_map.find((const void*) edge_iter->ftr)->second);
}
// updating cn begin and end children pointers.
if (cn->levels.size()) {
cn->begin_child = &(*(cn->levels[0].begin()));
cn->past_end_child = &(*(cn->levels[0].end()));
}
else {
cn->begin_child = &(*(cn->edge_level.begin()));
cn->past_end_child = &(*(cn->edge_level.end()));
}
cn->ftr = 0;
curve_list.push_back(*cn);
}
// running on both curve lists and upfdating edge node pointers.
// Notice that when updating edge node childrens we need all edge
// nodes to be defined since when there are overlappings edge nodes
// will points to other edge nodes on different curve lists.
Curve_iterator new_cv_iter;
for (cv_iter = arr.curve_list.begin(), new_cv_iter = curve_list.begin();
cv_iter != arr.curve_list.end() && new_cv_iter != curve_list.end();
++cv_iter, ++new_cv_iter){
Edge_iterator new_edge_iter = new_cv_iter->edge_level.begin();
Edge_const_iterator edge_iter = cv_iter->edge_level.begin();
for (edge_iter = cv_iter->edge_level.begin(),
new_edge_iter = new_cv_iter->edge_level.begin();
edge_iter != cv_iter->edge_level.end() &&
new_edge_iter != new_cv_iter->edge_level.end();
++edge_iter, ++new_edge_iter)
{
Edge_node* en = &*new_edge_iter;
Edge_node* en_begin_child =
(Edge_node*)
(all_edges_map.find
((const void*) &*(edge_iter->begin_child))->second);
en->begin_child = en_begin_child;
Edge_node* en_past_end_child =
(Edge_node*)
(all_edges_map.find
((const void*) &*(edge_iter->past_end_child))->second);
en->past_end_child = en_past_end_child;
Halfedge* hp =
(Halfedge*)
(cross_halfedges.find(&*(edge_iter->halfedge() ))->second);
Halfedge_handle curr_h = current_halfedges_pointers.find(hp)->second;
curr_h->set_edge_node(en);
curr_h->twin()->set_edge_node(en);
// notice the fact that curr_h is in the direction of en->curve(),
// since cross_halfedges maps the halfedge pointers 1-1.
en->hdg = curr_h;
}
}
}
template <class Scanner>
bool scan_arr (Scanner& scanner)
{
typedef typename Dcel::Vertex D_vertex;
typedef typename Dcel::Halfedge D_halfedge;
typedef typename Dcel::Face D_face;
typedef typename Dcel::Vertex_iterator D_vetrex_iterator;
typedef typename Dcel::Vertex_const_iterator D_vetrex_const_iterator;
typedef typename Dcel::Halfedge_iterator D_halfedge_iterator;
typedef typename Dcel::Halfedge_const_iterator D_halfedge_const_iterator;
typedef typename Dcel::Face_iterator D_face_iterator;
typedef typename Dcel::Face_const_iterator D_face_const_iterator;
typedef std::pair<std::size_t, std::size_t> Index_pair;
// keeping a vector of halfedges (to access them easily by their indices)
std::vector<Halfedge_handle> halfedges_vec;
if (!scanner.in())
return false;
if (!pm.read(scanner.in(), scanner)) {
std::cerr << "can't read planar map"<<std::endl;
scanner.in().clear(std::ios::badbit);
clear();
return false;
}
for (Halfedge_iterator h_iter = halfedges_begin();
h_iter != halfedges_end();
++h_iter)
halfedges_vec.push_back(h_iter);
std::list<std::list<Index_pair> > en_ovlp_child_indices_all_lists;
std::size_t number_of_curves;
scanner.scan_index(number_of_curves);
if (!scanner.in()) {
std::cerr << "can't read number of curves"<<std::endl;
scanner.in().clear(std::ios::badbit);
clear();
return false;
}
unsigned int i;
for (i = 0; i < number_of_curves; i++) {
Curve_node* cn = new Curve_node;
scanner.scan_Curve_node(cn);
if (!scanner.in()) {
std::cerr << "can't read curve node"<<std::endl;
scanner.in().clear(std::ios::badbit);
clear();
return false;
}
// reading subcurve node levels.
std::size_t number_of_levels;
scanner.scan_index(number_of_levels);
if (!scanner.in()){
std::cerr << "can't read number of levels"<<std::endl;
scanner.in().clear(std::ios::badbit);
clear();
return false;
}
std::vector<std::vector<std::size_t> > begin_child_indices_table,
end_child_indices_table;
//std::vector<std::vector<Subcurve_node*> > scn_table;
unsigned int j;
for (j = 0; j < number_of_levels; j++) {
// reading level j.
std::size_t number_of_subcurves;
scanner.scan_index(number_of_subcurves);
if (!scanner.in()) {
std::cerr << "can't read number of subcurves"<<std::endl;
scanner.in().clear(std::ios::badbit);
clear();
return false;
}
In_place_list<Subcurve_node, true> scn_list;
std::vector<std::size_t> begin_child_indices_vec,
end_child_indices_vec;
//std::vector<Subcurve_node* > scn_vec;
for (unsigned int k = 0; k < number_of_subcurves; k++) {
std::size_t begin_child_index, end_child_index;
scanner.scan_index(begin_child_index);
if (! scanner.in()){
std::cerr << "can't read begin child index"<<std::endl;
scanner.in().clear(std::ios::badbit);
clear();
return false;
}
scanner.scan_index(end_child_index);
if (! scanner.in()) {
std::cerr << "can't read past end child index"<<std::endl;
scanner.in().clear(std::ios::badbit);
clear();
return false;
}
begin_child_indices_vec.push_back(begin_child_index);
end_child_indices_vec.push_back(end_child_index);
Subcurve_node* scn = new Subcurve_node;
scanner.scan_Subcurve_node(scn);
if (! scanner.in()){
std::cerr << "can't read subcurve node"<<std::endl;
scanner.in().clear(std::ios::badbit);
clear();
return false;
}
scn->ftr = cn;
scn_list.push_back(*scn);
// update the tmp vector for finding scn pointers according indices.
//scn_vec.push_back(scn);
}
begin_child_indices_table.push_back(begin_child_indices_vec);
end_child_indices_table.push_back(end_child_indices_vec);
(cn->levels).push_back(scn_list);
}
// now scanning edge nodes.
std::size_t number_of_edge_nodes;
scanner.scan_index(number_of_edge_nodes);
if (! scanner.in()){
std::cerr << "can't read numberof edge nodes"<<std::endl;
scanner.in().clear(std::ios::badbit);
clear();
return false;
}
std::list<Index_pair> en_ovlp_child_indices_list;
for (j = 0; j < number_of_edge_nodes; j++) {
//std::vector<Index_pair> en_ovlp_child_indices_vec;
Edge_node* en = new Edge_node;
std::size_t halfedge_index;
std::size_t cn_ovlp_index, en_ovlp_index;
// scanning the past to end child of edge node
// (this pointer indicates the overlapping edge nodes).
scanner.scan_index(cn_ovlp_index);
if (! scanner.in()){
std::cerr << "can't read begin overlapping index"<<std::endl;
scanner.in().clear(std::ios::badbit);
clear();
return false;
}
scanner.scan_index(en_ovlp_index);
if (! scanner.in()) {
std::cerr << "can't read past end overlapping index"<<std::endl;
scanner.in().clear(std::ios::badbit);
clear();
return false;
}
en_ovlp_child_indices_list.push_back(Index_pair(cn_ovlp_index,
en_ovlp_index));
scanner.scan_index(halfedge_index);
if (! scanner.in()) {
std::cerr << "can't read halfedge index"<<std::endl;
scanner.in().clear(std::ios::badbit);
clear();
return false;
}
scanner.scan_Edge_node(en);
if (! scanner.in()) {
std::cerr << "can't read edge node"<<std::endl;
scanner.in().clear(std::ios::badbit);
clear();
return false;
}
// update the halfedge field.
en->hdg = halfedges_vec[halfedge_index];
en->ftr = cn;
// update the pointer in halfedge and its twin to edge_nodes.
halfedges_vec[halfedge_index]->set_edge_node(en);
halfedges_vec[halfedge_index]->twin()->set_edge_node(en);
// updating cn list.
cn->edge_level.push_back(*en);
}
en_ovlp_child_indices_all_lists.push_back(en_ovlp_child_indices_list);
// updating cn begin and end children pointers.
if (number_of_levels){
cn->begin_child = &(*(cn->levels[0].begin()));
cn->past_end_child = &(*(cn->levels[0].end()));
}
else {
cn->begin_child = cn->edge_level.begin().operator->();
cn->past_end_child = cn->edge_level.end().operator->();
}
// now updating begin and past end children pointers of each
// subcurve node and also its pointer to its father.
for (j = 0; j < number_of_levels; j++) {
unsigned int k = 0, l = 0, m = 0;
Subcurve_iterator scn_child_iter;
Edge_iterator en_child_iter = cn->edges_begin();
if (j+1 < number_of_levels) // else - we use the en_child_iter.
scn_child_iter = cn->level_begin(j+1);
for (Subcurve_iterator scn_iter = cn->level_begin(j);
scn_iter != cn->level_end(j);
scn_iter++, k++){
if (j+1 < number_of_levels){ // not including the last one.
std::size_t begin_child_index = begin_child_indices_table[j][k];
for (;
l < begin_child_index &&
scn_child_iter != cn->level_end(j+1);
scn_child_iter++, l++);
scn_iter->begin_child = &(*scn_child_iter);
std::size_t past_end_child_index = end_child_indices_table[j][k];
// running the pointer and also updating father field.
for (;
l < past_end_child_index &&
scn_child_iter != cn->level_end(j+1);
scn_child_iter++, l++){
scn_child_iter->ftr = scn_iter.operator->();
}
scn_iter->past_end_child = &(*scn_child_iter);
}
else {
//the last one should point to the edge nodes.
std::size_t begin_child_index = begin_child_indices_table[j][k];
for(;
m < begin_child_index && en_child_iter != cn->edges_end();
en_child_iter++, m++) ;
scn_iter->begin_child = &(*en_child_iter);
std::size_t past_end_child_index = end_child_indices_table[j][k];
// running the pointer and also updating father field.
for(;
m < past_end_child_index && en_child_iter != cn->edges_end();
en_child_iter++, m++){
en_child_iter->ftr = scn_iter.operator->();
}
scn_iter->past_end_child = &(*en_child_iter);
}
}
}
curve_list.push_back(*cn);
}
// now updating edge node childs, which indicates overlapping edge nodes.
Curve_iterator cn_iter = curve_node_begin();
std::list <std::list<Index_pair> >::iterator
all_lists_iter = en_ovlp_child_indices_all_lists.begin();
for (;
all_lists_iter != en_ovlp_child_indices_all_lists.end() &&
cn_iter != curve_node_end();
all_lists_iter++, cn_iter++){
Edge_iterator en_iter = cn_iter->edges_begin();
for (std::list<Index_pair>::iterator list_iter =
(*all_lists_iter).begin();
list_iter != (*all_lists_iter).end() &&
en_iter != cn_iter->edges_end();
list_iter++, en_iter++) {
std::size_t cn_ovlp_index = list_iter->first;
std::size_t en_ovlp_index = list_iter->second;
unsigned int j;
Curve_iterator tmp_cn_iter;
for (tmp_cn_iter = curve_node_begin(), j = 0;
tmp_cn_iter != curve_node_end() && j < cn_ovlp_index;
tmp_cn_iter++, j++);
// now tmp_cn_iter is the cn_ovlp_index'th curve node.
Edge_iterator tmp_en_iter;
for (tmp_en_iter = tmp_cn_iter->edges_begin(), j = 0;
tmp_en_iter != tmp_cn_iter->edges_end() && j < en_ovlp_index;
tmp_en_iter++, j++);
// now tmp_en_iter is the en_ovlp_index'th edge node.
en_iter->past_end_child = tmp_en_iter.operator->();
}
}
return true;
}
///////////////////////////////////////////////////////////////////////////
private:
bool use_delete_pl;
bool use_delete_traits;
protected:
//debug
//public:
Traits_wrap *traits;
Pmwx pm;
In_place_list<Subcurve_node,true> curve_list;
//for UPDATE mode
bool do_update;
Curve_iterator last_updated;
/*
//debug
public:
friend ::std::ostream& operator<<(::std::ostream& o,
const Curve_iterator& cn) {
o << "Curve_node: " << cn->curve() << std::endl;
for (unsigned int i=0; i<cn->number_of_sc_levels(); ++i) {
o << "Level" << i << ": ";
for (Subcurve_iterator scit=cn->level_begin(i);
scit!=cn->level_end(i); ++scit) {
o << scit->curve() << " , " ;
}
o << std::endl;
}
o <<"Edge level: ";
for (Edge_iterator eit=cn->edges_begin(); eit!=cn->edges_end();
++eit) {
o << eit->curve() << " , " ;
}
o << std::endl;
return o;
}
*/
};
CGAL_END_NAMESPACE
#endif
syntax highlighted by Code2HTML, v. 0.9.1