2D Planar Map (Planar_map_2)

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

typedef Planar_map_2<Dcel,Traits>
	Self;

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

typedef typename Traits::X_curve
	X_curve;	a curve of the planar map.
typedef typename Traits::Point
	Point;	a point of the planar map.

enum Locate_type { VERTEX = 1, EDGE, FACE, UNBOUNDED_FACE};
	an enumeration that specifies the result of point location and ray shooting operations.

Creation

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

Point Location Strategies

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

Operations

Halfedge_handle	pm.insert ( X_curve cv)
		inserts the curve cv into the map. Precondition: No curve cv1 of pm intersects cv in the interiors of cv and cv1.

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_at_vertices ( X_curve cv, Vertex_handle v1, Vertex_handle v2)
		inserts cv as a new edge between v1 and v2, where v1 and v2 are vertices of the map. v1 and v2 represent the source and target of the returned halfedge. Precondition: v1->point() and v2->point() are the two endpoints of cv.
Halfedge_handle	pm.insert_from_vertex ( X_curve cv, Vertex_handle v1, bool source)
		inserts a new edge for which one endpoint, v1, is already in the map. The returned halfedge is the one that has v1 as it's source. If source is true (resp. false) then the target of the returned halfedge holds the point which is cv's target (resp. source). Precondition: the second endpoint of cv is not in the map.
Halfedge_handle	pm.insert_in_face_interior ( X_curve cv, Face_handle f)
		inserts cv as a new inner component of f. Precondition: cv is contained completely in the interior of f (no vertex of cv meets any vertex on the map).

Query Functions

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

Halfedge_handle	pm.locate ( Point 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.
Halfedge_handle	pm.vertical_ray_shoot ( Point p, Locate_type& lt, bool up_direction)
		if up_direction is true (resp. false) returns the first edge of pm that intersects the upward (resp. 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. Precondition: p lies in the interior of a face of pm, i.e., not on an edge or on a vertex. 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.

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.

Modifying Functions

Halfedge_handle	pm.split_edge ( Halfedge_handle e, X_curve c1, X_curve 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 will be assigned to e1 and c2 to e2. 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_curve cv)
		merges the edges e1 and e2 into one edge which will 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.