).
The arrangement class holds a planar map and a hierarchy tree.
Vertices, halfedges and faces of the arrangement derive from
those of the planar map (with the additional functionality of
the arrangement),
in the same way that the vertices, halfedges and faces of the topological map
class derive from those of the Dcel class
(see Chapter).
The hierarchy tree is implemented using the In_place_list class (see the chapter on STL Extensions in the Support Library Manual). Every level of a curve hierarchy is a list of tree nodes.The Curve_node and Edge_node of the hierarchy derive from Subcurve_node. This enables the polymorphic structure of the tree. The Subcurve_node is derived from the Base_node which is a template parameter of the arrangement. This enables the addition of attributes to the nodes of the hierarchy tree by adding them inside the Base_node.
As part of the Dcel we define requirements for its vertex, halfedge and face constituents. If we consider these constituents as (informally) subconcepts of the Dcel concept then we have the following models for its constituents.
The Arr_2_vertex_base<Point> is a model for the Dcel vertex subconcept, the Arr_2_halfedge_base<Base_node> is a model for the Dcel halfedge subconcept and the Arr_2_face_base is a model for the Dcel face subconcept.
#include <CGAL/Arr_2_bases.h>
The Arr_2_default_dcel<Traits> is a model of the Dcel concept
described above. Its template parameter is the traits class.
It is a wrapper for Pm_dcel instantiated
with Arr_2_vertex_base<Traits::Point>,
Arr_2_halfedge_base<Arr_base_node<Traits::X_curve> > and
Arr_2_face_base.
#include <CGAL/Arr_2_default_dcel.h>
The different traits classes are described at the end of this chapter.
As already mentioned at chapter , the motivation for using I/O functions is not only to be able to draw the arrangement to a window for instance, but also to be capable to save an arrangement in a text file by writing it and reloading it from a text file by reading it.
Reading an arrangement from the standard input or printing it to the standard output may be done simply with the Extractor ( >> ) and Insertor ( << ) operators defined for Arrangement_2, respectively.
#include <CGAL/IO/Arr_iostream.h>
The ability of sending the Arrangement into a graphic stream as leda_window, Postscript file or Geomview is also provided, users simply have to apply the Insertor operator on the graphic stream and their arrangement instance.
Users of I/O functions for the arrangement package are required to define I/O operators for the curves defined in their Traits classes. When using Traits classes in which this operators are already defined (as Segment Traits or Circle Traits ) the operator definition is not obligated, however using Traits classes as the Polyline Traits will force the user to define I/O operators on his polyline curve.
The Arrangement class data consists of the induced planar map and the obtained hierarchy tree. Hence, the data sent to the output stream or read from an input stream should contain both parts.
The format of the planar map part is as specified in the Planar Map refernce pages (). The format of the hierarchy tree is specified below.
The format of the output file is defined in a way the reading function will construct the arrangement efficiently. The induced planar map is constructed efficiently as specified in the Planar Map refernce pages (), and the hierarchy tree is also constructed efficiently by directly accessing its parts and updating them. When constructing an arrangement from an input stream, no use of its insertion functions is performed.
Consequently, the reading function constructs the arrangement very efficiently, and hence users who would like to save their arrangement and reload it have to construct their arrangement by the insertion functions only once. After saving the arrangement to a text file it can be reloaded very efficiently when needed.
When users would like to read their arrangement from the standard input or print it into the standard output, they may simply use the Extractor ( >> ) and Insertor ( << ) operators defined for Arrangement respectively. If users add attributes to their arrangement components, reading (resp. writing) arrangement would be done by inheriting the class Arr_file_scanner (resp. Arr_file_writer ) and overriding all the relevant function for scanning (resp. writing) the arrangement components. After the definition of the inherited class users have to call the function read of Arrangement (resp. the global function write_arr ) with the inherited class as a parameter. The ability of sending the Arrangement into a graphic stream as leda_window, Postscript file or Geomview is also provided, users simply have to use the Insertor operator operated on the graphic stream and their arrangement. When users would like to add attributes to their arrangement components and send their arrangement to a graphic stream, they have to inherit the class Pm_drawer and then call the global function draw_pm with this class and their arrangement as parameters. The function Pm_drawer is used both for Planar map and Arrangement, since drawing an arrangement is defined as drawing only its planar map part.
Format As mentioned above, the format of the planar map part is as specified in the Planar Map refernce pages (). Here, we are representing the format of the hierarchy tree.
Generally, the format represents the curve nodes list of the arrangement. Each component of one curve node is compound from all the subcurves and edge nodes this curve node contains. This data is associative with geometric information and some topological information in order to be able to update the hierarchy tree efficiently.
The format is detailed below:
Other rules concerning the format are detailed in the Planar Map refernce pages ().
The input of the program is a text file presenting the Arrangement:
# ------------------------------------- Printing Arrangement # -------------------------------------------------------- # ------------------------------------- Printing Planar map # -------------------------------------------------------- # Printing number of vertices halfedges and faces in Planar map 5 8 1 # 5 vertices # ------------------------------------------ 1/1 1/1 0/1 0/1 1/2 1/2 0/1 1/1 1/1 0/1 # 8 halfedges # ------------------------------------------ 2 0/1 0/1 1/2 1/2 1 0/1 0/1 1/2 1/2 0 1/2 1/2 1/1 1/1 2 1/2 1/2 1/1 1/1 2 0/1 1/1 1/2 1/2 3 0/1 1/1 1/2 1/2 2 1/2 1/2 1/1 0/1 4 1/2 1/2 1/1 0/1 # 1 faces # ------------------------------------------ # writing face # ------------------------------------------ # UNBOUNDED # number halfedges on outer boundary 0 # number of holes 1 # inner ccb # number halfedges on inner boundary 8 0 5 4 2 3 7 6 1 # finish writing face # ------------------------------------------ # ------------------------------------- End of Planar map # -------------------------------------------------------- # Printing curve hierachy # number of curves 2 # 1 'th curve # ------------------------------------------ 0/1 0/1 1/1 1/1 # number of levels 0 # number of edge nodes 2 # ----------------------- Edge nodes childrens: # pair indices (curve node and its edge node) for next overlapping edge node : 0 0 # Halfedge indices associtaed with edge nodes 0 # Edge node curve 0/1 0/1 1/2 1/2 # pair indices (curve node and its edge node) for next overlapping edge node : 0 1 # Halfedge indices associtaed with edge nodes 2 # Edge node curve 1/2 1/2 1/1 1/1 # finished current level # 2 'th curve # ------------------------------------------ 0/1 1/1 1/1 0/1 # number of levels 0 # number of edge nodes 2 # ----------------------- Edge nodes childrens: # pair indices (curve node and its edge node) for next overlapping edge node : 1 0 # Halfedge indices associtaed with edge nodes 4 # Edge node curve 0/1 1/1 1/2 1/2 # pair indices (curve node and its edge node) for next overlapping edge node : 1 1 # Halfedge indices associtaed with edge nodes 7 # Edge node curve 1/2 1/2 1/1 0/1 # finished current level # ------------------------------------- End of Arrangement # --------------------------------------------------------
The example above presents an arrangement containing two segments intersect in their interior. The segments coordinates are (0,0), (1,1) and (0,1), (1,0). The Arrangement instance that was used to produce this example was templated with the Arr_segment_exact_traits class, which was templated with the representation class Cartesian<Quotient<int> >.
The first part of the input represents the planar map our arrangement contains, and hence its format is identically the same as . It can be seen that the planar map described here represents all the vertcies and halfedges obtained by the disjoint subcurves of the arrangement. The next part of the input file presents the hierarchy tree of our arrangement. This presentation begins with the number 2, indicating there are two curve nodes in our arrangement. The list of curve nodes follows. The first curve node begins withh its associated curve (0,0), (1,1), it has 0 levels since it does not contain any subcurve nodes (only curve nodes and edge nodes). The number of edge nodes the curve (0,0), (1,1) induces is two, and the curves these two edge nodes are associated with are (0,0), (1/2,1/2) and (1/2,1/2), (1,1) correspondingly. The indices of each edge node to an overlapping edge node are pointing to the edge node itself since there are no overlapping in the input file. Finally, the indices of the halfedge indicates the halfedge our edge node is associated with. For example the first edge node induced by the curve (0,0), (1,1) is associated with the first halfedge presented in the halfedges list. The reader may verify that this halfedge holds the same curve the edge node holds.
The current format may not be comfortable for a user to read, because the usage of indices. There is a possibility to define a verbose format which contains instead of indices, the components themselves, and hence the user has the option to have a format which is easy for human to read. This format cannot be scanned by the reading functions of Arrangement.
// examples/Arrangement_2/example11
#include <CGAL/Quotient.h>
#include <CGAL/Cartesian.h>
#include <CGAL/Arr_2_bases.h>
#include <CGAL/Arr_2_default_dcel.h>
#include <CGAL/Arr_segment_exact_traits.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/IO/Arr_iostream.h>
#include <iostream>
//#ifdef CGAL_USE_LEDA
//#include <CGAL/IO/Arr_Postscript_file_stream.h>
//#endif
typedef CGAL::Quotient<int> NT;
typedef CGAL::Cartesian<NT> R;
typedef CGAL::Arr_segment_exact_traits<R> Traits;
typedef Traits::Point Point;
typedef Traits::X_curve X_curve;
typedef Traits::Curve Curve;
typedef CGAL::Arr_2_default_dcel<Traits> Dcel;
typedef CGAL::Arr_base_node<Curve> Base_node;
typedef CGAL::Arrangement_2<Dcel,Traits,Base_node > Arrangement;
int main()
{
Arrangement arr;
std::cout << "* * * Demonstrating a trivial use of IO functions";
std::cout << std::endl << std::endl;
std::cin >> arr;
std::cout << arr;
std::cout << std::endl;
std::cout << "* * * Presenting the use of verbose format";
std::cout << std::endl << std::endl;;
CGAL::Arr_file_writer<Arrangement> verbose_writer(std::cout, arr, true);
CGAL::write_arr(arr, verbose_writer, std::cout);
// printing to Postscript file.
//#ifdef CGAL_USE_LEDA
//CGAL::Postscript_file_stream LPF(500, 500 ,"arr.ps");
//LPF.init(-3,3,-3);
//LPF.set_line_width( 1);
//LPF << arr;
//#endif
return 0;
}
The output is the Arrangement written in both formats, non verbose and verbose.
* * * Demonstrating a trivial use of IO functions # ------------------------------------- Printing Arrangement # -------------------------------------------------------- # ------------------------------------- Printing Planar map # -------------------------------------------------------- # Printing number of vertices halfedges and faces in Planar map 5 8 1 # 5 vertices # ------------------------------------------ 1/1 1/1 0/1 0/1 1/2 1/2 0/1 1/1 1/1 0/1 # 8 halfedges # ------------------------------------------ 2 0/1 0/1 1/2 1/2 1 0/1 0/1 1/2 1/2 0 1/2 1/2 1/1 1/1 2 1/2 1/2 1/1 1/1 2 0/1 1/1 1/2 1/2 3 0/1 1/1 1/2 1/2 2 1/2 1/2 1/1 0/1 4 1/2 1/2 1/1 0/1 # 1 faces # ------------------------------------------ # writing face # ------------------------------------------ # UNBOUNDED # number halfedges on outer boundary 0 # number of holes 1 # inner ccb # number halfedges on inner boundary 8 0 5 4 2 3 7 6 1 # finish writing face # ------------------------------------------ # ------------------------------------- End of Planar map # -------------------------------------------------------- # Printing curve hierachy # number of curves 2 # 1 'th curve # ------------------------------------------ 0/1 0/1 1/1 1/1 # number of levels 0 # number of edge nodes 2 # ----------------------- Edge nodes childrens: # pair indices (curve node and its edge node) for next overlapping edge node : 0 0 # Halfedge indices associtaed with edge nodes 0 # Edge node curve 0/1 0/1 1/2 1/2 # pair indices (curve node and its edge node) for next overlapping edge node : 0 1 # Halfedge indices associtaed with edge nodes 2 # Edge node curve 1/2 1/2 1/1 1/1 # finished current level # 2 'th curve # ------------------------------------------ 0/1 1/1 1/1 0/1 # number of levels 0 # number of edge nodes 2 # ----------------------- Edge nodes childrens: # pair indices (curve node and its edge node) for next overlapping edge node : 1 0 # Halfedge indices associtaed with edge nodes 4 # Edge node curve 0/1 1/1 1/2 1/2 # pair indices (curve node and its edge node) for next overlapping edge node : 1 1 # Halfedge indices associtaed with edge nodes 7 # Edge node curve 1/2 1/2 1/1 0/1 # finished current level # ------------------------------------- End of Arrangement # -------------------------------------------------------- * * * Presenting the use of verbose format # ------------------------------------- Printing Arrangement # -------------------------------------------------------- # ------------------------------------- Printing Planar map # -------------------------------------------------------- # Printing number of vertices halfedges and faces in Planar map 5 8 1 # 5 vertices # ------------------------------------------ 1/1 1/1 0/1 0/1 1/2 1/2 0/1 1/1 1/1 0/1 # 8 halfedges # ------------------------------------------ 1/2 1/2 0/1 0/1 1/2 1/2 0/1 0/1 0/1 0/1 1/2 1/2 1/1 1/1 1/2 1/2 1/1 1/1 1/2 1/2 1/2 1/2 1/1 1/1 1/2 1/2 0/1 1/1 1/2 1/2 0/1 1/1 0/1 1/1 1/2 1/2 1/2 1/2 1/2 1/2 1/1 0/1 1/1 0/1 1/2 1/2 1/1 0/1 # 1 faces # ------------------------------------------ # writing face # ------------------------------------------ # UNBOUNDED # number halfedges on outer boundary 0 # number of holes 1 # inner ccb # number halfedges on inner boundary 8 1/2 1/2 0/1 0/1 1/2 1/2 0/1 1/1 0/1 1/1 1/2 1/2 1/2 1/2 0/1 1/1 1/2 1/2 1/1 1/1 1/2 1/2 1/1 1/1 1/2 1/2 1/2 1/2 1/1 1/1 1/1 0/1 1/2 1/2 1/1 0/1 1/2 1/2 1/2 1/2 1/1 0/1 0/1 0/1 0/1 0/1 1/2 1/2 # finish writing face # ------------------------------------------ # ------------------------------------- End of Planar map # -------------------------------------------------------- # Printing curve hierachy # number of curves 2 # 1 'th curve # ------------------------------------------ 0/1 0/1 1/1 1/1 # number of levels 0 # number of edge nodes 2 # ----------------------- Edge nodes childrens: # Halfedge associated with edge nodes 1/2 1/2 0/1 0/1 1/2 1/2 # Edge node curve 0/1 0/1 1/2 1/2 # Halfedge associated with edge nodes 1/1 1/1 1/2 1/2 1/1 1/1 # Edge node curve 1/2 1/2 1/1 1/1 # finished current level # 2 'th curve # ------------------------------------------ 0/1 1/1 1/1 0/1 # number of levels 0 # number of edge nodes 2 # ----------------------- Edge nodes childrens: # Halfedge associated with edge nodes 1/2 1/2 0/1 1/1 1/2 1/2 # Edge node curve 0/1 1/1 1/2 1/2 # Halfedge associated with edge nodes 1/1 0/1 1/2 1/2 1/1 0/1 # Edge node curve 1/2 1/2 1/1 0/1 # finished current level # ------------------------------------- End of Arrangement # --------------------------------------------------------
For more examples see chapter .
More details are given in sections
Arr_file_scanner<Arrangement>,
Arr_file_writer<Arrangement>
