, Topological Maps.
We also describe the additional functionality of Planar_map_2<Dcel,Traits>
over that of Topological_map<Dcel>.
In this chapter we introduce planar maps which are
embeddings of topological maps into the plane.
The Planar_map_2<Dcel,Traits> class is derived
from the Topological_map<Dcel> class with additional geometric considerations
and functionalities (e.g., point location, bounding box).
In this section we briefly review
the geometric concepts added in the planar map; the combinatorial concepts were
reviewed in Chapter , Topological Maps.
We also describe the additional functionality of Planar_map_2<Dcel,Traits>
over that of Topological_map<Dcel>.
There are two template parameters, the Dcel which is the underlying combinatorial data structure and the Traits which is the underlying geometry, i.e. the number type used, the coordinate representation and the family of curves treated.
Curve: We will use the term curve to describe the image of a continuous mapping into the plane of any one of the following: the closed unit interval (arc), the open unit interval (unbounded curve), or the unit circle (closed curve). In all cases a curve is non self-intersecting. Segments, lines, rays, conic sections are examples for curves.
-monotone curve: We use a convention that a curve is -monotone if either intersects any vertical line in at most one point, or is a vertical segment.
Planar subdivision (planar map): 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. Halfedges around a vertex are also traversed in clockwise order.
Maps with infinite objects (bounding boxes): The Planar map deals both with bounded objects, such as segments, circles. and with infinite objects, such as lines, rays, parabolas. For simplicity we decided that the default would be the former, e.g. bounded objects. In order to deal with the latter, some finite representation of such infinite curves is required. The bounding box strategy supplies the required functionality to do this.
A bounding box is defined by two main aspects: its traits representation and its maintenance strategy. The traits representation is a given shape that corresponds to a region in the plane in which we are interested at a given moment, e.g. a rectangle, a big disk, the whole plane. The maintenance strategy, can be of many types. The strategy may be of static type , i.e. we are interested only in a fixed region of the plane, curves outside this region are ignored, or it may be dynamic, i.e. the bounding box increases or decreases while the user updates the planar map. The strategy may be of an open type, i.e. the boundary of the box should not be included as curves of the map, or it may be closed, where this means that the boundary is a part of the planar map.
Point Location: Some of the basic operations on planar maps are queries such as ``what is the location of a point in the map?'', or ``which curve is vertically above the point?''. These geometric queries are supplied as part of this Planar Map class, with several algorithms available for the user to choose from.
I/O functions: I/O functions for reading a saved planar map from the standard input, writing it to the standard output or drawing it to a graphic stream are also provided. 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.
The class Planar_map<Dcel,Traits> supplies the ability to maintain a planar map. All the combinatorial entities have a geometric mapping, e.g., a vertex of a planar map has a Point data member, a halfedge has a X_curve (x-monotone curve) data member, etc. In addition to the modifying function, namely, insertion, removal, splitting and merging, the user can perform point location queries and vertical ray shoot queries. For a full reference of the class (i.e its associated types, its operations, etc.) read the Planar_map Reference Pages.
Figure: The map generated by the example program
The following program creates a planar map from five curves (see
figure ). It uses the floating-point
arithmetic interface class
(Pm_segment_epsilon_traits<R>). The first part of the
code initializes five segments. The next part inserts them into the map
and checks the validity of the map. In the last part, vertical ray
shooting is performed from the point .
// examples/Planar_map/example1.C
// ------------------------------
#include <CGAL/Cartesian.h>
#include <CGAL/Pm_segment_epsilon_traits.h>
#include <CGAL/Pm_default_dcel.h>
#include <CGAL/Planar_map_2.h>
typedef double Number_type;
typedef CGAL::Cartesian<Number_type> Coord_t;
typedef CGAL::Pm_segment_epsilon_traits<Coord_t> Pmtraits;
typedef Pmtraits::Point Point;
typedef Pmtraits::X_curve Curve;
typedef CGAL::Pm_default_dcel<Pmtraits> Pmdcel;
typedef CGAL::Planar_map_2<Pmdcel,Pmtraits> Planar_map;
int main()
{
// creating an instance of Planar_map_2<Pmdcel,Pmtraits>
// Pm_naive_point_location_strategy<pmdcel,pmtraits> Pl_strategy;
// Planar_map_2<Pmdcel,Pmtraits> pm(&Pl_strategy);
Planar_map pm;
Curve cv[5];
int i;
Point a1(100, 0), a2(20, 50), a3(180, 50), a4(100, 100);
// those curves are about to be inserted to pm
cv[0] = Curve(a1, a2);
cv[1] = Curve(a1, a3);
cv[2] = Curve(a2, a3);
cv[3] = Curve(a2, a4);
cv[4] = Curve(a3, a4);
std::cout << "the curves of the map :" << std::endl;
for (i = 0; i < 5; i++)
std::cout << cv[i] << std::endl;
std::cout << std::endl;
// insert the five curves to the map
std::cout << "inserting the curves to the map..." << std::endl;
for (i = 0; i < 5; i++)
{
std::cout << "inserting curve" << i << std::endl;
pm.insert(cv[i]);
}
// check the validity of the map
std::cout << "check map validity... ";
if (pm.is_valid())
std::cout << "map valid!" << std::endl;
else
std::cout << "map invalid!" << std::endl;
std::cout << std::endl;
// vertical ray shooting upward from p
Point p(95, 30);
Planar_map::Halfedge_handle e;
Planar_map::Locate_type lt;
std::cout << std::endl << "upward vertical ray shooting from " << p;
std::cout << std::endl;
e=pm.vertical_ray_shoot(p, lt, true);
std::cout << "returned the curve :" << e->curve() << " oriented toward "
<< e->target()->point() << std::endl;
return 0;
}
The output of the program is
the curves of the map : 100 0 20 50 100 0 180 50 20 50 180 50 20 50 100 100 180 50 100 100 inserting the curves to the map... inserting curve0 inserting curve1 inserting curve2 inserting curve3 inserting curve4 check map validity... map valid! upward vertical ray shooting from 95 30 returned the curve : 20 50 180 50
The following program demonstrates the use of I/O functions provided for planar maps. First the program demonstrates a trivial use of the I/O functions: it defines an empty instance of Planar_map_2, reads the planar map representation text from the standard input stream, and then prints the resulting planar map to the standard output stream.
Second, it presents the usage of the verbose format, by defining Pm_file_writer with the verbose flag set to true, and then calls the function write_pm. A usage of the interface of the class Pm_file_writer is also presented, by calling its function write_halfedges, which prints all the halfedges of the map. In addition, the program presents the operators writing the resulting Planar map to a postscript file when LEDA is installed. The demo for the planar map package makes use of the output operator of Planar_map_2<Dcel,Traits> to a window stream (see at <CGAL_ROOT>/demo/Planar_map/demo.C ).
// examples/Planar_map/example9.C
// ------------------------------
#include <CGAL/Cartesian.h>
//#include <CGAL/leda_rational.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>
//#ifdef CGAL_USE_LEDA
//#include <CGAL/IO/Pm_Postscript_file_stream.h>
// #endif
//typedef leda_rational NT;
typedef CGAL::Quotient<int> NT;
typedef CGAL::Cartesian<NT> R;
typedef CGAL::Pm_segment_exact_traits<R> Traits;
typedef CGAL::Pm_default_dcel<Traits> Dcel;
typedef CGAL::Planar_map_2<Dcel,Traits> PM;
typedef CGAL::Pm_file_writer<PM> Pm_writer;
int main()
{
PM pm;
std::cout << "* * * Demonstrating a trivial use of IO functions" << std::endl << std::endl;
std::cin >> pm;
std::cout << pm;
std::cout << std::endl;
std::cout << "* * * Presenting the use of verbose format" << std::endl;
std::cout << std::endl;
Pm_writer verbose_writer(std::cout, pm, true);
CGAL::write_pm(pm, verbose_writer, std::cout);
std::cout << std::endl;
std::cout << "* * * Demonstrating the use of the writer class interface." << std::endl;
std::cout << "* * * Printing all halfedges in non verbose format" << std::endl << std::endl;
Pm_writer writer(std::cout, pm);
writer.write_halfedges(pm.halfedges_begin(), pm.halfedges_end());
std::cout << std::endl;
std::cout << "* * * Printing all halfedges in a verbose format" << std::endl << std::endl;
verbose_writer.write_halfedges(pm.halfedges_begin(), pm.halfedges_end());
//#ifdef CGAL_USE_LEDA
// printing to Postscript file.
//CGAL::Postscript_file_stream LPF(500, 500 ,"pm.ps");
//LPF.init(-3,3,-3);
//LPF.set_line_width( 1);
//LPF << pm;
//#endif
return 0;
}
The input of the program is a text file which holds the planar map representation in a special format (which is presented in the reference pages of the the Planar Map package. This representation appears as the first block in the output file.
The output is the Planar map includes both formats, non-verbose and verbose. In addition the two lists (non-verbose and verbose) of halfedges are written.
* * * Demonstrating a trivial use of IO functions # ------------------------------------- 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 # -------------------------------------------------------- * * * Presenting the use of verbose format # ------------------------------------- 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 # ------------------------------------------ 1/1 1/1 0/1 0/1 1/1 1/1 0/1 0/1 0/1 0/1 1/1 1/1 1/1 1/1 1/1 1/1 2/1 0/1 2/1 0/1 1/1 1/1 2/1 0/1 0/1 0/1 2/1 0/1 0/1 0/1 2/1 0/1 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 0/1 0/1 2/1 0/1 0/1 0/1 1/1 1/1 0/1 0/1 1/1 1/1 2/1 0/1 1/1 1/1 2/1 0/1 # finish writing face # ------------------------------------------ # writing face # ------------------------------------------ # outer ccb # number halfedges on outer boundary 3 2/1 0/1 2/1 0/1 0/1 0/1 1/1 1/1 1/1 1/1 2/1 0/1 0/1 0/1 0/1 0/1 1/1 1/1 # number of holes 0 # finish writing face # ------------------------------------------ # ------------------------------------- End of Planar map # -------------------------------------------------------- * * * Demonstrating the use of the writer class interface. * * * Printing all halfedges in non verbose format 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 * * * Printing all halfedges in a verbose format 1/1 1/1 0/1 0/1 1/1 1/1 0/1 0/1 0/1 0/1 1/1 1/1 1/1 1/1 1/1 1/1 2/1 0/1 2/1 0/1 1/1 1/1 2/1 0/1 0/1 0/1 2/1 0/1 0/1 0/1 2/1 0/1 2/1 0/1 0/1 0/1