Given a collection $$ of (possibly intersecting and not necessarily $$x-monotone curves) in the plane, we construct a collection $$'' in two steps, as follows: First, we decompose each curve in $$ into maximal $$x-monotone curves, thus obtaining the collection $$'. Second, We decompose each curve in $$' into maximal connected pieces not intersecting any other curve in $$'. This way we obtain the collection $$'' of $$x-monotone, pairwise interior disjoint curves. Constructing the planar map with intersection of the curves in $$ is therefore equivalent to the construction of the planar map(see Chapter ) induced by the curves in $$''.
The Planar Map with Intersections package extends the functionality of the Planar Map package by enabling simple insertion of intersecting and not necessarily $$x-monotone curves. The Planar_map_with_intersections_2 class has different insertion functions but it uses the same data structures as the Planar_map_2 class. Therefore, almost any functionality of the planar map is also supported here (e.g., traversal of planar map features, point location queries and I/O operations are supported but infinite objects are not supported). However, to maintain a planar map with intersections one obviously needs to support some additional functions in the geometric traits class, handling with intersections and $$x-monotonicity.
Note that if one needs to build a planar map of $$x-monotone, pairwise interior disjoint curves, then it would be more efficient (in running time) and less demanding (in traits class functionality) to use the Planar_map_2 class instead.
Degeneracies
Like the Planar Map package (see Chapter ), the Planar Map with Intersections package can deal with $$x-degenerate input (including vertical segments). However, while in the planar map the input curves were assumed to be non-intersecting in their interiors, there is no such assumption when using planar map with intersections. Furthermore, overlapping curves are also supported: If two curves overlap the traits intersection function must return the two endpoints of the common part.
// file: examples/Pm_with_intersections/example1.C #include <CGAL/Cartesian.h> #include <CGAL/MP_Float.h> #include <CGAL/Quotient.h> #include <CGAL/Pm_default_dcel.h> #include <CGAL/Arr_segment_traits_2.h> #include <CGAL/Planar_map_2.h> #include <CGAL/Pm_with_intersections.h> typedef CGAL::Quotient<CGAL::MP_Float> NT; typedef CGAL::Cartesian<NT> Kernel; typedef CGAL::Arr_segment_traits_2<Kernel> Traits; typedef Traits::Point_2 Point_2; typedef Traits::X_monotone_curve_2 X_monotone_curve_2; typedef CGAL::Pm_default_dcel<Traits> Dcel; typedef CGAL::Planar_map_2<Dcel,Traits> Planar_map_2; typedef CGAL::Planar_map_with_intersections_2<Planar_map_2> Pmwx; int main() { Pmwx pm; X_monotone_curve_2 cv1(Point_2(0, 0), Point_2(1, 1)); X_monotone_curve_2 cv2(Point_2(0, 1), Point_2(1, 0)); //insertion of the curves std::cout << "Inserting the segments:" << std::endl << cv1 << std::endl; pm.insert(cv1); std::cout << cv2 << std::endl << std::endl; pm.insert(cv2); //traversal of the curves std::cout << "Edges of the planar map:" << std::endl; Pmwx::Halfedge_const_iterator eit; for (eit = pm.halfedges_begin(); eit != pm.halfedges_end(); ++eit, ++eit) { std::cout << eit->source()->point() << " --- " << eit->target()->point() << std::endl; } return 0; }
The output of the program looks like this:
Inserting the segments: 0 0 1 1 0 1 1 0 Edges of the planar map: 0 0 --- 0.5 0.5 0.5 0.5 --- 1 1 0 1 --- 0.5 0.5 1 0 --- 0.5 0.5
The Planar_map_with_intersections_2<Planar_map_2<Dcel, Traits> > class is parameterized with the Planar_map_2 class it inherits from, which is parameterized with the Dcel and the Traits objects. The Dcel is a data structure that maintains a doubly-connected edge list and represents the underlying topology. The geometric functionality is provided by the Traits class, and is tailored to handle a specific family of curves. It encapsulates the number type used and the coordinate representation. This package contains traits classes that handle various types of curves (e.g., segments, polylines, conics, etc.).
Similar to some constructors of the Planar_map_2, (see Chapter ), some of the constructors of the Planar_map_with_intersections_2 class allow you to choose between various point-location strategies. While the default point-location strategy of the Planar_map_2 class is the trapezoid-ric strategy, which is based on a trapezoidal decomposition of the map, and requires constructing and maintening auxliary data structures, the default strategy of the Planar_map_with_intersections_2 class is the walk-along-a-line strategy, as the overhead of the former tends to be very large when no restrictions are applied on the input curves.
A Planar Map with Intersections can be built incrementally by inserting one curve after the other into the map. However, for a large number of curves that intersect rather sparsely, it can be more efficient to use the aggregate insertion method, that inserts a set of curves to an empty map at once by performing the sweep-line algorithm on the set of input curves.
The aggregate insertion method is more efficient in many cases and it also has less requirements from the traits class, in comparison with the the incremental insertion function. Namely, the curves_compare_y_at_x_left() and the nearest_intersection_to_left() functions are not required, nor do the various reflection functions.
The output of the program looks like this:
In some cases the users insert curves to a planar map with intersections in an incremental manner, but have some knowledge regarding the location of several curves. In such cases, special insertion functions may be called in order to speed up the construction of the map:
advanced |
An insertion of an intersecting curve into a planar map may add several halfedges and modify several features of the map (i.e. split halfedges, split faces, etc.). The so-called Change Notification class provides this kind of flexibility. The modification methods accept an additional parameter, a class which is a model of the PlanarMapWithIntersectionsChangeNotification_2 concept. The change notification includes an associative function for each modification method. This function is called after each such modification.
The change notification class is useful in many cases. For example, one may add a color (or other extra data) to any halfedge of a planar map. An insertion of a new curve can split halfedges that were previously in the map. After such a split the color of the newly created halfedges should be updated according to the original color of the split halfedge. One can do this by implementing the split_edge function of the change notification class. This function will be called after each split of an halfedge in the map.
// file: examples/Pm_with_intersections/example2.C #include "short_names.h" #include <CGAL/Cartesian.h> #include <CGAL/MP_Float.h> #include <CGAL/Quotient.h> #include <CGAL/Pm_default_dcel.h> #include <CGAL/Arr_segment_traits_2.h> #include <CGAL/Planar_map_2.h> #include <CGAL/Pm_with_intersections.h> typedef CGAL::Quotient<CGAL::MP_Float> NT; typedef CGAL::Cartesian<NT> Kernel; typedef CGAL::Arr_segment_traits_2<Kernel> Traits; typedef Traits::Point_2 Point_2; typedef Traits::X_monotone_curve_2 X_monotone_curve_2; typedef CGAL::Pm_default_dcel<Traits> Dcel; typedef CGAL::Planar_map_2<Dcel,Traits> Planar_map_2; typedef CGAL::Planar_map_with_intersections_2<Planar_map_2> Pmwx; typedef Pmwx::Pmwx_change_notification Pmwx_change_notification; class My_notification : public Pmwx_change_notification { public: My_notification() {i = 0;} void add_edge(const Traits::X_monotone_curve_2 &, Planar_map::Halfedge_handle, bool /* left_to_right */, bool overlap = false) { (void) overlap; std::cout << "add_edge" << std::endl; i++; } void split_edge(Planar_map::Halfedge_handle /* orig_edge */, Planar_map::Halfedge_handle /* new_edge */, const Traits::X_monotone_curve_2 &, const Traits::X_monotone_curve_2 &) { std::cout << "split_edge" << std::endl; i++; } void split_face(Planar_map::Face_handle /* orig_face */, Planar_map::Face_handle /* new_face */) { std::cout << "split_face" << std::endl; } void add_hole(Planar_map::Face_handle /* in_face */, Planar_map::Halfedge_handle /* new_hole */) { std::cout << "add_hole" << std::endl; } int i; }; int main() { Pmwx pm; My_notification notif; //insertion of the curves X_monotone_curve_2 c1(Point_2(0, 1), Point_2(1, 0)); X_monotone_curve_2 c2(Point_2(0, 0), Point_2(1, 1)); X_monotone_curve_2 c3(Point_2(0, 1), Point_2(1, 1)); std::cout << "inserting " << c1 << std::endl; pm.insert(c1, ¬if); std::cout << "inserting " << c2 << std::endl; pm.insert(c2, ¬if); std::cout << "inserting " << c3 << std::endl; pm.insert(c3, ¬if); std::cout << "Total number of edges " << notif.i << std::endl; return 0; }
The output of the program looks like this:
inserting 0 1 1 0 add_edge add_hole inserting 0 0 1 1 split_edge add_edge add_edge inserting 0 1 1 1 add_edge split_face Total number of edges 5
advanced |