2D Planar Map (CGAL_Planar_map_2)

Definition

such that no curve intersects the interior of any other curve. The available traits and dcel classes will be described later.

#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 CGAL_Planar_map_2<Dcel,Traits>
	Self;

CGAL_Planar_map_2<Dcel,Traits>::Traits
	traits class.
CGAL_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};
	enumeration of the features of the planar map. This specifies the result of point location and ray shooting operations.

Creation

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

Point Location Strategies

The CGAL_Planar_map<Dcel,Traits> class has a point location function (namely, the locate function that determines which feature of the map contains a given query point) which is also used internally in the insert function. There are several known algorithms for solving a point location query. We have implemented two - the randomized incremental algorithm introduced by Mulmuley  [Mul90],  [Sei91],  [dBvKOS97], and the naive algorithm (which goes over all vertices and edges). The former uses a trapezoidal map structure for achieving an expected query time of $O(log\; n)$ for a map with $n$ edges. The randomized algorithm is the one used by default in our implementation. However, the users can choose to use the naive algorithm (trading time for memory efficiency) or can implement their own point location algorithm. This is done with a class derived from the CGAL_Point_location_base<Planar_map> class which is passed as a parameter in the constructor. The description of the class is given in Section .

CGAL_Planar_map_2<Dcel,Traits> pm ( CGAL_Pm_point_location_base<Self> *pl_ptr);

Operations

Halfedge_handle	pm.insert ( X_curve cv)
		insert 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)
		insert 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.
Halfedge_handle	pm.insert_from_vertex ( X_curve cv, Vertex_handle v1, bool source)
		insert 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)
		insert 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)
		return 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) return 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 $\backslash vecpq$ 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 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.

Modifying Functions

Halfedge_handle	pm.split_edge ( Halfedge_handle e, X_curve c1, X_curve c2)
		split 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. Precondition: the preconditions of CGAL_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)
		merge 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 CGAL_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)
		remove 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.