(2D Arrangements).
A planar subdivision (or planar map) is an embedding of a planar topological map into the plane, such that each edge of is embedded as a bounded -monotone curve and each vertex is embedded as a planar point. In this embedding no edge intersects another edge interior.
A face of the subdivision is a maximal connected region of the plane that does not contain any vertex or edge. We consider a face to be open, and its boundary is formed by vertices and halfedges of the subdivision. The halfedges are oriented around a face so that the face they bound is to their left. This means that halfedges on the outer boundary of a face are traversed in counterclockwise order, and halfedges on the inner boundaries (holes) of a face are traversed in clockwise order. Edges around a vertex are also traversed in clockwise order.
We supply a default traits class for exact arithmetic - Pm_segment_exact_traits<R> where R is the kernel representation type (Homogeneous or Cartesian). There is also a class for finite precision arithmetic - Pm_segment_epsilon_traits<R>, which is not recommended unless it is known that robustness issues will not arise. Both traits handle finite line segments in the plane and use the CGAL kernel (Point is of type Point_2<R> and X_curve is of type Segment_2<R>). We also supply a traits class that uses LEDA's rational kernel and makes use of its efficient predicates. The different supplied traits classes are described at the end of this chapter.
The PlanarMapWithIntersectionsTraits_2 and ArrangementTraits_2
concepts are refinements of the PlanarMapTraits_2 concept.
Therefore, all models of the formers are models of the latter.
There are several supplied traits classes for the Arrangement which the user can use.
These classes are described at the end of Chapter
(2D Arrangements).
The motivation for using I/O functions is not only to be able to draw the planar map to a window for instance, but also to be capable to save planar maps in a text file and reload it from a text file when needed.
The format of the output file is defined in a way the reading function will be able to construct the planar map by updating directly the Dcel without using the insertion functions of the Planar map. Consequently, the reading function constructs the planar map very efficiently. Obviously, for very big maps or for repetitive use of the same map it would be extremely faster to build the map only once (incrementally or via a sweep line utility) , save it and reload the ready map when necessary.
Reading a planar map from the standard input or printing it to the standard output may be done simply with the Extractor ( >> ) and Insertor ( << ) operators defined for Planar_map_2, respectively.
#include <CGAL/IO/Pm_iostream.h>
The ability of sending the Planar map 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 planar map instance.
Users of I/O functions for the planar map 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.
Users may wish to add their own attributes planar map components. If those attributes are to be written as part of the planar map representation (respectively, are to be re-read later) a specialized reader (scanner) class (writer class, resp.) should be defined for the special planar map. This is done preferably by making it a sub class of the class Pm_file_scanner (Pm_file_writer, resp.) and overriding all the relevant function for scanning (writing, resp.) the changed components.
After the definition of the inherited class users have to call the function read of Planar map (resp., the global function write_pm ) with the inherited class as a parameter.
The same goes for extending the output graphic streams to include additional attributes only for this purpose a new drawer class has to be defined. This is done preferably by making this class inherit the class Pm_drawer. In order to send the special planar map to the graphic stream one should call the global function draw_pm with this class and their planar map as parameters.
Format The chosen format does not follow an existing standard format. Generally, the format contains lists of the components of a planar map followed by each other. For each component we write its associative geometric information and some topological information in order to be able to update the Dcel efficiently. The format is detailed below.
The current format may not be comfortable for a user to read because of the extensive use of indices. The user can print a planar map in a verbose format (shorthand for verbose mode format). The skeleton of the verbose format is the same. However, in order for the output to be clearer for a human reader points and halfedges are explicitly written rather than being represented by indices. Also the direction of the halfedges are printed in a more convenient way to read. This verbose format cannot be scanned by the reading functions of Planar_map_2.
The example below presents a representation of a planar map containing one triangle with the coordinates (0,0), (1,1) and (2,0). The Planar_map_2 instance that was used to produce this example was templated with the Pm_segment_exact_traits class, which in turn was templated with the representation class Cartesian<leda_rational>. The first line specifies that the planar map has three vertices, six halfedges, and 2 faces (the triangle and the unbounded face). The list of vertices each represented by its associated point follows, as shown in the output example. The next list is the one of halfedges, each component is represented by its index (0,1 or 2) in the vertices list and its associated segment. The faces list is presented next. It starts with the unbounded face having one hole which is the triangle, this connected component specifies that the hole has three halfedges with the indices 4, 0 and 3. The next face presenting the triangle is written in the same manner.
# ------------------------------------- Printing Planar map # -------------------------------------------------------- # Printing number of vertices halfedges and faces in Planar map 3 6 2 # 3 vertices # ------------------------------------------ 1/1 1/1 0/1 0/1 2/1 0/1 # 6 halfedges # ------------------------------------------ 0 0/1 0/1 1/1 1/1 1 0/1 0/1 1/1 1/1 0 1/1 1/1 2/1 0/1 2 1/1 1/1 2/1 0/1 1 2/1 0/1 0/1 0/1 2 2/1 0/1 0/1 0/1 # 2 faces # ------------------------------------------ # writing face # ------------------------------------------ # UNBOUNDED # number halfedges on outer boundary 0 # number of holes 1 # inner ccb # number halfedges on inner boundary 3 4 0 3 # finish writing face # ------------------------------------------ # writing face # ------------------------------------------ # outer ccb # number halfedges on outer boundary 3 5 2 1 # number of holes 0 # finish writing face # ------------------------------------------ # ------------------------------------- End of Planar map # --------------------------------------------------------
The following program demonstrates the usage of I/O functions while users have an additional attribute in their planar map. The attribute chosen here is adding an associative color to each vertex. First the program extends the Dcel to maintain this attribute. Second, the program extends the Pm_file_writer class to handle the newly defined vertex. It simply overrides the functions for writing a vertex to print the color of the vertex as well. Finally, the main function defines an empty Planar map, reads it from the standard input stream, and then set all vertices colors. It then defines an object of its extended writer class and parameterize the function write_pm with that object.
// examples/Planar_map/example10.C
// -------------------------------
#include <CGAL/Cartesian.h>
#include <CGAL/Quotient.h>
#include <CGAL/Pm_default_dcel.h>
#include <CGAL/Planar_map_2.h>
#include <CGAL/Pm_segment_exact_traits.h>
#include <CGAL/IO/Pm_iostream.h>
#include <CGAL/IO/write_pm.h>
#include <iostream>
#include <string>
using CGAL::write_pm;
template <class Pt>
class Pm_my_vertex : public CGAL::Pm_vertex_base<Pt>
{
public:
Pm_my_vertex() : CGAL::Pm_vertex_base<Pt>(){}
void set_color(const std::string& c) { color = c;}
std::string get_color() const { return color;}
private:
std::string color;
};
// building new dcel with my vertex base.
template <class Traits>
class Pm_my_dcel :
public CGAL::Pm_dcel<Pm_my_vertex<typename Traits::Point>,
CGAL::Pm_halfedge_base<typename Traits::X_curve>,
CGAL::Pm_face_base>
{
public: // Creation
Pm_my_dcel() {}
};
// extend the drawer to print the color as well.
template <class PM>
class Pm_my_file_writer : public CGAL::Pm_file_writer<PM> {
public:
typedef typename PM::Vertex_handle Vertex_handle;
typedef typename PM::Vertex_const_handle Vertex_const_handle;
typedef typename PM::Vertex_iterator Vertex_iterator;
typedef typename PM::Vertex_const_iterator Vertex_const_iterator;
Pm_my_file_writer(std::ostream& o, const PM& pm, bool verbose = false) :
CGAL::Pm_file_writer<PM>(o, pm, verbose) {}
void write_vertex(Vertex_handle v) {
out() << v->point() <<" ";
out() << v->get_color()<< std::endl;
}
void write_vertex(Vertex_const_handle v) {
out() << v->point() <<" ";
out() << v->get_color()<< std::endl;
}
};
typedef CGAL::Quotient<int> NT;
typedef CGAL::Cartesian<NT> R;
typedef CGAL::Pm_segment_exact_traits<R> Traits;
typedef Pm_my_dcel<Traits> Dcel;
typedef CGAL::Planar_map_2<Dcel,Traits> PM;
typedef PM::Vertex_iterator Vertex_iterator;
int main()
{
PM pm;
std::cin >> pm;
std::cout<<"* * * Demonstrating the usage of defining user attributes for Planar map components"<<std::endl<<std::endl;
std::cout << std::endl;
// updating the colors for halfedge and vertex.
for (Vertex_iterator v_iter = pm.vertices_begin();
v_iter != pm.vertices_end();
v_iter++)
v_iter->set_color("BLUE");
//printing pm to output stream with the user attributes.
std::cout << "* * * Printing the Planar map" << std::endl;
std::cout << std::endl;
Pm_my_file_writer<PM> writer(std::cout, pm);
write_pm(pm, writer, std::cout);
return 0;
}
The input of the program is a text file presenting the Planar map:
# ------------------------------------- Printing Planar map # -------------------------------------------------------- # Printing number of vertices halfedges and faces in Planar map 3 6 2 # 3 vertices # ------------------------------------------ 1/1 1/1 0/1 0/1 2/1 0/1 # 6 halfedges # ------------------------------------------ 0 0/1 0/1 1/1 1/1 1 0/1 0/1 1/1 1/1 0 1/1 1/1 2/1 0/1 2 1/1 1/1 2/1 0/1 1 2/1 0/1 0/1 0/1 2 2/1 0/1 0/1 0/1 # 2 faces # ------------------------------------------ # writing face # ------------------------------------------ # UNBOUNDED # number halfedges on outer boundary 0 # number of holes 1 # inner ccb # number halfedges on inner boundary 3 4 0 3 # finish writing face # ------------------------------------------ # writing face # ------------------------------------------ # outer ccb # number halfedges on outer boundary 3 5 2 1 # number of holes 0 # finish writing face # ------------------------------------------ # ------------------------------------- End of Planar map # --------------------------------------------------------
The output is the Planar map written in both formats, non verbose and verbose. In addition the two lists (non verbose and verbose) of halfedges are written.
* * * Demonstrating the usage of defining user attributes for Planar map components * * * Printing the Planar map # ------------------------------------- Printing Planar map # -------------------------------------------------------- # Printing number of vertices halfedges and faces in Planar map 3 6 2 # 3 vertices # ------------------------------------------ 1/1 1/1 BLUE 0/1 0/1 BLUE 2/1 0/1 BLUE # 6 halfedges # ------------------------------------------ 0 0/1 0/1 1/1 1/1 1 0/1 0/1 1/1 1/1 0 1/1 1/1 2/1 0/1 2 1/1 1/1 2/1 0/1 1 2/1 0/1 0/1 0/1 2 2/1 0/1 0/1 0/1 # 2 faces # ------------------------------------------ # writing face # ------------------------------------------ # UNBOUNDED # number halfedges on outer boundary 0 # number of holes 1 # inner ccb # number halfedges on inner boundary 3 4 0 3 # finish writing face # ------------------------------------------ # writing face # ------------------------------------------ # outer ccb # number halfedges on outer boundary 3 5 2 1 # number of holes 0 # finish writing face # ------------------------------------------ # ------------------------------------- End of Planar map # --------------------------------------------------------
More details are given in sections File_header, Pm_file_scanner<Planar_map>, Pm_file_writer<Planar_map> and Pm_drawer<Planar_map>.
We have derived three concrete classes for point location strategies, the default strategy, based on trapezoidal decomposition of the map, the naive strategy, which goes over all the vertices and halfedges of the planar map and the walk-along-a-line strategy, which improves the naive one by ``walking'' only along the zone of the vertical ray emanating from the query point. All three strategies are classes that inherit Pm_point_location_base<Planar_map>. More details are give in sections Pm_default_point_location<Planar_map>, Pm_naive_point_location<Planar_map> and Pm_walk_along_a_line_point_location<Planar_map>.
In order for the advanced user to write a model of a the user's class should inherit the CGAL supplied class Pm_point_location_base<Planar_map>.
Trade-off Issues The main trade-off among the three strategies implemented, is between time and storage. Using the naive or walk strategies takes more time but saves storage space.
Another trade-off depends on the need for point location queries compared to the need for other functions. If the users do not need point location queries, but do need other modifying functions (e.g., remove_edge, split_edge and merge_edge) then using the naive or walk strategies is preferable. Note that using the insert function invokes the point location query, therefore when using the naive or walk strategies it is recommended to use the specialized insertion functions : insert_in_face_interior, insert_from_vertex and insert_at_vertices. For example, when using the planar map to represent polygons (e.g., when computing boolean operations on polygons) it might be preferable to use the walk strategy with the specialized insertion functions.
There are two modes of the default strategy which enables the user
to choose whether preprocessing should be performed or not (read more in
the section stated above).
There is a trade-off between the those two modes. If
preprocessing is not used, the building of the structure is faster. However,
for some input sequences the structure might be unbalanced and therefore
queries and updates might take longer, especially, if many removal and split
operation are performed.
Defining the bounding box algorithm is done with a bounding box class passed to the map in the constructor. The class passed should be a model of the concept PlanarMapBoundingBox_2. The bounding box class should be derived from the base class Pm_bounding_box_base<Planar_map> which is a (pure virtual) base class that defines the interface between the algorithm implemented and the planar map according to the requirements of the above concept. All concrete classes for bounding box strategies, namely the unbounding box strategy and the dynamic open strategy stand up to these criteria
The following sections list and describe the PlanarMapBoundingBox_2 concept and the supplied bounding box strategies which model this concept: PlanarMapBoundingBox_2, Pm_unbounding_box<Planar_map> and Pm_dynamic_open_bounding_box<Planar_map>.
Trade-off Issues The main trade-off issues between the different strategies implemented are concerned with functionality and time efficiency.
The unbounding box is efficient in time though compared to the others it is limited to bounded curves traits, e.g., circle traits or line segment traits. This means that if the users want to work with, say, straight lines the unbounding box will not work. To the other extreme, if one chooses the dynamic bounding box and queries a point outside the bounded area then this might cause the whole bounding box to be modified. The requirement may be of a linear time (in the number of curves). In addition to that, in order to ensure that the bounding box is large enough, the traits has to supply additional functions, namely to model the PlanarMapBoundingBoxTraits_2 concept (which is a refinement of the PlanarMapTraits_2 concept).
This section presents some tips on how to tune CGAL::Planar_map_2<Dcel,Traits> for best performance.
Before the specific tips, it should be reminded that compiling programs with debug flags turned off and with optimization flags significantly reduces running time.
Insertion of a polygon, which is represented by a list of segments along its boundary, into an empty planar map should be done in the following way. First, some segment should be inserted using insert_in_face_interior with the unbounded face. Then a segment with a common end point can be inserted using insert_from_vertex and so on with the rest of the segments but last. The last segment can be inserted using insert_at_vertices since both it endpoints are represented as vertices of the map and are known in advanced.