CGAL::Planar_map_2<Dcel,Traits>

Definition

#include <CGAL/Planar_map_2.h>

Inherits From

The modifying functions insert_in_face_interior, insert_from_vertex, insert_at_vertices, split_edge, merge_edge and remove_edge overwrite the inherited functions and make use of the geometric information of the planar map.

Types

Planar_map_2<Dcel,Traits>::Traits
	traits class.
Planar_map_2<Dcel,Traits>::Dcel
	DCEL class.
Planar_map_2<Dcel,Traits>::Change_notification

The Vertex, Halfedge and Face types of the planar map are defined as part of the planar map DCEL While the face of planar map is a face of the topological map, the Vertex and Halfedge have additional functionality. A Vertex has the additional point and set_point operations. A Halfedge has the additional curve and set_curve operations. See concepts PlanarMapDcel_2, PlanarMapDcelVertex_2 and PlanarMapDcelHalfedge_2 .

Planar_map_2<Dcel,Traits>::Vertex
	represents a vertex of the planar map.

Planar_map_2<Dcel,Traits>::Halfedge
	represents a halfedge of the topological map.

Planar_map_2<Dcel,Traits>::Face
	represents a face of the topological map.

typedef typename Traits::X_monotone_curve_2
	X_monotone_curve_2;	a curve of the planar map.
typedef typename Traits::Point_2
	Point_2;	a point of the planar map.

Constants

Creation

Planar_map_2<Dcel,Traits> pm;
	constructs an ``empty map'' containing one unbounded face, which corresponds to the whole plane.
Planar_map_2<Dcel,Traits> pm ( Self pm);
	copy constructor;

advanced

Point Location

As described in the introduction, the planar map users can define which algorithm to use in the point location queries. This is done by passing an instance of some point location class instance to the map in this constructor. The point location class should be a model of the PlanarMapPointLocation_2 concept. The randomized trapezoidal decomposition algorithm is the one used by default in our implementation. However, the users can choose to use the naive or ``walk'' algorithms (trading time for memory efficiency) or can implement their own point location algorithm. This can be done with a class derived from the Point_location_base<Planar_map>. The concept PlanarMapPointLocation_2 lists the set of requirements ().

Planar_map_2<Dcel,Traits> pm ( Pm_point_location_base<Self> * pl_ptr);

advanced

advanced

Reading Planar map

bool	pm.read ( istream & in)
		reads Planar_map_2<Dcel,Traits> from the given input stream in. The input stream should support the extractor operator (>>) for the Point_2 and X_monotone_curve_2 types of Planar_map. Note that the verbose format is not meant to be read.
template <class Scanner>
bool	pm.read ( istream & in, Scanner & scanner)
		reads Planar_map_2<Dcel,Traits> from the given input stream in using scanner. The input stream should support the extractor operator (>>) for the Point_2 and X_monotone_curve_2 types of Planar_map

advanced

Query Functions

The following two functions are query functions. Their time complexity depends on the point location strategy used.

Halfedge_handle	pm.locate ( Point_2 p, Locate_type & lt)
		computes the location in pm where p lies; If lt returns VERTEX then p lies on the vertex which is the target of the returned Halfedge. If lt returns EDGE then p lies on the returned Halfedge. If lt returns FACE then p lies on the face which is on the left of the returned Halfedge . If lt returns UNBOUNDED_FACE then p lies on the unbounded face, and the returned Halfedge is on the boundary of a hole in the unbounded face. The returned value for an empty map equals halfedges_end().
Halfedge_handle	pm.vertical_ray_shoot ( Point_2 p, Locate_type & lt, bool up_direction)
		if up_direction is true (respectively, false) returns the first edge of pm that intersects the upward (respectively, downward) vertical ray emanating from p. If several edges intersect the vertical ray in the same (end)point $$q, the function returns the first halfedge pointing at $$q, that is encountered when moving clockwise from $pq$ around $$q . In that case the value of lt will be VERTEX . If the ray does not intersect any edge, the value of lt will be UNBOUNDED_FACE and the Halfedge returned will be null valued. Otherwise the value of lt will be EDGE. Postcondition: the returned edge belongs to one of the CCB's of the face in which p is found, null valued if none is found.
bool	pm.is_point_in_face ( Point_2 p, Face_const_handle f)
		determines whether the given point p lies within the interior of the given face f. A point lies within a face interior, iff the number of intersections between the face boundary and a ray emanating from the point is even. Note that if f is the unbounded face, and it has no holes, the point must lie within the face interior. is_point_in_face() returns true if p lies within the interior of f, and false otherwise.

advanced

For some applications the users may want to have direct access to the point location strategy (e.g., query the default strategy about the state of its internal search structure). For this we have implemented the following function, note that the returned pointer is const so the users cannot change the internal state.

const Pm_point_location_base<Self>*
	pm.point_location ()
		returns a const pointer to the point location strategy of the map.

advanced

Modifiers

Halfedge_handle	pm.insert ( X_monotone_curve_2 cv, Change_notification * en = NULL)
		inserts the curve cv into the map. insert() returns a handle to a new halfedge directed in the same way as the curve cv. That is, the curve source and target points coincide with the points of the source and target vertices of the returned halfedge respectively. Precondition: no curve of pm intersects cv in the interiors of the curve itself and cv. Precondition: cv is not equivalent to a point.
template <X_curve_iterator>
Halfedge_handle	pm.insert ( X_curve_iterator begin, X_curve_iterator end, Change_notification * en = NULL)
		iterates through a given range of curves, inserting the curves into the map. begin and end are input iterators that point to the first curve and past-the-end curve of the range respectively. insert() returns a handle to a new halfedge directed in the same way as the last curve in the range. Precondition: the curves of pm do not intersect the curves in the given range in the interiors of the curves respectively. Precondition: no curve in the given range is equivalent to a point.

advanced

Specialized Insertion Functions

The following functions enable the usage of information about the map which was acquired beforehand, to save time in insertions. It is recommended to use these functions with the naive point location strategy.

Halfedge_handle	pm.insert_in_face_interior ( X_monotone_curve_2 cv, Face_handle f, Change_notification * en = NULL)
		inserts the curve cv as a new inner component of the face f. insert_in_face_interior() returns a handle to a new halfedge directed in the same way as cv. Precondition: cv is contained completely in the interior of f, (no endpoint of cv coincides with a point of any vertex of the map). Precondition: cv is not equivalent to a point.
Halfedge_handle	pm.insert_from_vertex ( X_monotone_curve_2 cv, Vertex_handle v, Change_notification * en = NULL)
		inserts the curve cv into the map. One endpoint of cv is the point of the given vertex v, that is already in the map. insert_from_vertex returns a handle to a new halfedge that has v as its source vertex. Precondition: v is a vertex of the map. Precondition: the point of v coincides with one endpoint of cv. Precondition: no vertex of the map has a point that coincides with the other endpoint of cv. Precondition: no curve of pm intersects cv in the interiors of the curve itself and cv. Precondition: cv is not equivalent to a point.
Halfedge_handle	pm.insert_at_vertices ( X_monotone_curve_2 cv, Vertex_handle v1, Vertex_handle v2, Change_notification * en = NULL)
		inserts the curve cv into the map. The two endpoints of cv are held by the two given vertices v1 and v2 respectively, that are already in the map. insert_at_vertices() returns a handle to a new halfedge, that has v1 and v2 as its source and target vertices respectively. Precondition: v1 and v2 are vertices of the map. Precondition: the points of v1 and v2 coincide with the two endpoints of cv respectively. Precondition: no curve of pm intersects cv in the interiors of the curve itself and cv. Precondition: cv is not equivalent to a point.
Halfedge_handle	pm.insert_from_vertex ( X_monotone_curve_2 cv, Halfedge_handle h, Change_notification * en = NULL)
		inserts the curve cv into the map. One endpoint of cv is the point of the target vertex, v, of the given halfedge h. insert_from_vertex returns a handle to a new halfedge that has v as its source vertex. The returened twin halfedge is inserted immediately after h in the circular list of halfedges that share the same target vertex v. This method is the quick version of insert_from_vertex(), as the search for the previous halfedge in the circular list of halfedges that share the same target vertex is unnecessary, saving computation time. Precondition: h is a halfedge of the map. Precondition: the point of v coincides with one endpoint of cv. Precondition: no vertex of the map has a point that coincides with the other endpoint of cv. Precondition: In the clockwise order of curves around the common point of v, cv succeeds the curve of h. Precondition: no curve of pm intersects cv in the interiors of the curve itself and cv. Precondition: cv is not equivalent to a point.
Halfedge_handle	pm.insert_at_vertices ( X_monotone_curve_2 cv, Halfedge_handle h1, Halfedge_handle h2, Change_notification * en = NULL)
		inserts the curve cv into the map. The two endpoints of cv are held by the two target vertices v1 and v2 of h1 and h2 respectively. insert_at_vertices() returns a handle to a new halfedge, that has v1 and v2 as its source and target vertices respectively. The returened halfedge is inserted immediately after h1 in the circular list of halfedges that share the same target vertex v1. Its twin halfedge is inserted immediately after h2 in the circular list of halfedges that share the same target vertex v2. This method is the quick version of insert_from_vertex(), as the search for the previous halfedges in the circular lists of halfedges that share the same target vertices is unnecessary, saving computation time. Precondition: h1 and h2 are halfedges of the map. Precondition: the points of v1 and v2 coincide with the two endpoints of cv respectively. Precondition: In the clockwise order of curves around the common point of v1, cv succeeds the curve of h1. Precondition: In the clockwise order of curves around the common point of v2, cv succeeds the curve of h2. Precondition: no curve of pm intersects cv in the interiors of the curve itself and cv. Precondition: cv is not equivalent to a point.

advanced

Halfedge_handle	pm.split_edge ( Halfedge_handle e, X_monotone_curve_2 c1, X_monotone_curve_2 c2)
		splits the edge e into e1 and e2 , and add a vertex in the splitting point. If the source point of e is identical to the source of the curve c1 then c1 abd c2 will be assigned to e1 and to e2 respectively and to their respective twin halfedges. Otherwise, the opposite will take place. The returned halfedge will be e1 where e2 is e1->next_halfedge(). Precondition: the preconditions of Topological_map<Dcel>::split_edge. Precondition: the target of the curve $$c1 is identical to the source of the curve $$c2. Precondition: the source of the curve $$c1 is identical to the source point of e and the target of the curve $$c2 is identical to the target point of e, or the source of the curve $$c1 is identical to the target point of e and the target of the curve $$c2 is identical to the source point of e.
Halfedge_handle	pm.merge_edge ( Halfedge_handle e1, Halfedge_handle e2, X_monotone_curve_2 cv)
		merges the edges represented by e1 and e2 into a single edge. The resulting halfedge and its twin hold the curve cv. The return value is the halfedge with the same source vertex that e1 had and the same target e2 had. Precondition: the preconditions of Topological_map<Dcel>::merge_edge. Precondition: the source of the curve $$cv is identical to the source point of e1 and the target of the curve $$cv is identical to the target point of e2, or the target of the curve $$cv is identical to the source point of e1 and the source of the curve $$cv is identical to the target point of e2.
Face_handle	pm.remove_edge ( Halfedge_handle e)
		removes the edge e from pm. If the operation causes two faces to merge, the merged face is returned. Otherwise, the face to which the edge was incident is returned.

See Also