EnvelopeDiagram

Navigation: Up Table of Contents Package Overview Bibliography Index Title Acknowledging CGAL

EnvelopeDiagram_1

Definition

This concept defines the representation of an envelope diagram of a set of planar curve. The envelope diagram is a subdivision of the x-axis into 0-dimensional cells (vertices) and 1-dimensional cells (edges), such that the identity of the curves that induce the lower envelope (or the upper envelope) over each cell is fixed.

A vertex in an envelope diagram is therefore associated with a point on the envelope, and corresponds to either a curve endpoint or to an intersection point of two (or more) curves. Therefore each vertex is associated with a set of x-monotone curves that induce the envelope over this point. Each vertex is incident to two edges, one lying to its left and the other to its right.

An edge in the envelope diagram represents a continuous portion of the x-axis, and is associated with a (possibly empty) set of curves that induce the envelope over this portion of the x-axis. An edge may be bounded by two vertices, one to its left and the other to its right. However, the diagram contains two unbounded edges, its leftmost edge, representing the interval (-∞, x_l), and its rightmost edge, representing the interval (x_r, ∞), where x_l and x_r are the x-coodinates of the leftmost and the rightmost vertices in the diagram, respectively. Note that a diagram may contain no vertices at all, in which case it comprises a single edge.

Note that any model of the EnvelopeDiagram_1 concept must define a geometric traits class, which in turn defines the Point_2 and X_monotone_curve_2 types defined with the diagram features.

Types

EnvelopeDiagram_1::Traits_2
	the geometric traits class.

typedef Traits_2::Point_2	Point_2;	the point type.
typedef Traits_2::X_monotone_curve_2
	X_monotone_curve_2;	the x-monotone curve type.

EnvelopeDiagram_1::Size
	the size type (convertible to size_t).

EnvelopeDiagram_1::Curve_const_iterator
	an iterator for the x-monotone curves that induce a diagram feature. Its value-type is X_monotone_curve_2.

EnvelopeDiagram_1::Vertex
	the vertex type, a model of the concept EnvelopeDiagramVertex.
EnvelopeDiagram_1::Edge
	the edge type, a model of the concept EnvelopeDiagramEdge.

EnvelopeDiagram_1::Vertex_handle
	a handle to a diagram vertex.
EnvelopeDiagram_1::Vertex_const_handle
	a non-mutable handle to a diagram vertex.

EnvelopeDiagram_1::Edge_handle
	a handle to a diagram edge.
EnvelopeDiagram_1::Edge_const_handle
	a non-mutable handle to a diagram edge.

Creation

EnvelopeDiagram_1 diag;
	constructs an empty diagram containing one unbounded edge, which corresponds to the entire plane and has no x-monotone curves that are associated with it.

EnvelopeDiagram_1 diag ( Self other);
	copy constructor.

Access Functions

Edge_const_handle	diag.leftmost () const	returns the leftmost edge of the diagram (a non-const version is also available).
Edge_const_handle	diag.rightmost () const	returns the rightmost edge of the diagram (a non-const version is also available).

Modifiers

void	diag.set_leftmost ( Edge_const_handle e)
		sets the leftmost edge of the diagram to be e.
void	diag.set_rightmost ( Edge_const_handle e)
		sets the rightmost edge of the diagram to be e.

Vertex_handle	diag.new_vertex ( Point_2 p)	creates a new diagram vertex, associated with the point p.
Edge_handle	diag.new_edge ()	creates a new diagram edge.

void	diag.delete_vertex ( Vertex_handle v)
		deletes the given vertex v.
void	diag.delete_edge ( Edge_handle e)
		deletes the given edge e.