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.
- Refines
ArrangementOnCurve_1
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 \((-\infty, x_l)\), and its rightmost edge, representing the interval \((x_r, \infty)\), where \(x_l\) and \(x_r\) are the \( x\)-coordinates 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 | |
| typedef unspecified_type | 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. | |
| typedef unspecified_type | Curve_size |
| the size type (convertible to size_t). | |
| typedef unspecified_type | Curve_const_iterator |
| an iterator for the \( x\)-monotone curves that induce a diagram feature, with value type X_monotone_curve_2. | |
Accessors | |
| Edge_const_descriptor | leftmost () const |
| obtains the leftmost edge of the diagram. | |
| Edge_const_descriptor | rightmost () const |
| obtains the rightmost edge of the diagram. | |
Modifiers | |
| void | set_leftmost (Edge_const_descriptor e) |
| sets the leftmost edge of the diagram to be e. | |
| void | set_rightmost (Edge_const_descriptor e) |
| sets the rightmost edge of the diagram to be e. | |
Curve Data Accessors | |
| const Point_2 & | point (Vertex_const_descriptor v) const |
| obtains the point associated with a given vertex. | |
| const Curve_container & | vertex_curves (Vertex_descriptor v) const |
| obtains the diagram curves associated with a given vertex. | |
| const Curve_container & | edge_curves (Edge_descriptor e) const |
| obtains the diagram curves associated with a given edge. | |
| Curve_size | number_of_vertex_curves (Vertex_const_descriptor v) const |
| obtains the number of curves associated with a given vertex. | |
| Curve_size | number_of_edge_curves (Edge_const_descriptor e) const |
| obtains the number of curves associated with a given edge. | |
| bool | empty_vertex_curves (Vertex_const_descriptor v) const |
| determines whether there are no curves associated with a given vertex. | |
| bool | empty_edge_curves (Edge_const_descriptor e) const |
| determines whether there are no curves associated with a given edge. | |
| const X_monotone_curve_2 & | vertex_curve (Vertex_const_descriptor v) const |
| obtains the first curve assocuayed with a given vertex. | |
| const X_monotone_curve_2 & | edge_curve (Edge_const_descriptor e) const |
| obtains the first curve associated with a given edge. | |
Curve Data Modifiers | |
| void | set_point (Vertex_descriptor v, const Point_2 &p) |
| sets the point associated with a fiven vertex. | |
| void | add_vertex_curve (Vertex_descriptor v, const X_monotone_curve_2 &xcv) |
| adds an \(x\)-monotone curve to the list of curves associated with a given vertex. | |
| void | add_edge_curve (Edge_descriptor e, const X_monotone_curve_2 &xcv) |
| adds an \(x\)-monotone curve to the list of curves associated with a given edge. | |
| void | add_edge_curves (Edge_descriptor e, Curve_const_iterator begin, Curve_const_iterator end) |
| adds a range of \(x\)-monotone curves to the list of curves associated with a given vertex. | |
| void | add_vertex_curves (Vertex_descriptor v, Curve_const_iterator begin, Curve_const_iterator end) |
| adds a range of \(x\)-monotone curves to the list of curves associated with a given edge. | |
| void | clear_vertex_curves (Vertex_descriptor v) |
| clears the curves associated with a given vertex. | |
| void | clear_edge_curves (Edge_descriptor e) |
| clears the curves associated with a given edge. | |
Member Function Documentation
◆ edge_curve()
| const X_monotone_curve_2 & EnvelopeDiagram_1::edge_curve | ( | Edge_const_descriptor | e | ) | const |
obtains the first curve associated with a given edge.
- Precondition
- empty_vertex_curves(v) is false.
◆ edge_curves()
| const Curve_container & EnvelopeDiagram_1::edge_curves | ( | Edge_descriptor | e | ) | const |
obtains the diagram curves associated with a given edge.
(A non-const version is also available.)
◆ leftmost()
| Edge_const_descriptor EnvelopeDiagram_1::leftmost | ( | ) | const |
obtains the leftmost edge of the diagram.
(A non-const version is also available.)
◆ rightmost()
| Edge_const_descriptor EnvelopeDiagram_1::rightmost | ( | ) | const |
obtains the rightmost edge of the diagram.
(A non-const version is also available.)
◆ vertex_curve()
| const X_monotone_curve_2 & EnvelopeDiagram_1::vertex_curve | ( | Vertex_const_descriptor | v | ) | const |
obtains the first curve assocuayed with a given vertex.
- Precondition
- empty_vertex_curves(v) is false.
◆ vertex_curves()
| const Curve_container & EnvelopeDiagram_1::vertex_curves | ( | Vertex_descriptor | v | ) | const |
obtains the diagram curves associated with a given vertex.
(A non-const version is also available.)
- Generated by
1.17.0
#include <Concepts/EnvelopeDiagram_1.h>
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.
- Refines
ArrangementOnCurve_1
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 \((-\infty, x_l)\), and its rightmost edge, representing the interval \((x_r, \infty)\), where \(x_l\) and \(x_r\) are the \( x\)-coordinates 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 | |
| typedef unspecified_type | 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. | |
| typedef unspecified_type | Curve_size |
| the size type (convertible to size_t). | |
| typedef unspecified_type | Curve_const_iterator |
| an iterator for the \( x\)-monotone curves that induce a diagram feature, with value type X_monotone_curve_2. | |
Accessors | |
| Edge_const_descriptor | leftmost () const |
| obtains the leftmost edge of the diagram. | |
| Edge_const_descriptor | rightmost () const |
| obtains the rightmost edge of the diagram. | |
Modifiers | |
| void | set_leftmost (Edge_const_descriptor e) |
| sets the leftmost edge of the diagram to be e. | |
| void | set_rightmost (Edge_const_descriptor e) |
| sets the rightmost edge of the diagram to be e. | |
Curve Data Accessors | |
| const Point_2 & | point (Vertex_const_descriptor v) const |
| obtains the point associated with a given vertex. | |
| const Curve_container & | vertex_curves (Vertex_descriptor v) const |
| obtains the diagram curves associated with a given vertex. | |
| const Curve_container & | edge_curves (Edge_descriptor e) const |
| obtains the diagram curves associated with a given edge. | |
| Curve_size | number_of_vertex_curves (Vertex_const_descriptor v) const |
| obtains the number of curves associated with a given vertex. | |
| Curve_size | number_of_edge_curves (Edge_const_descriptor e) const |
| obtains the number of curves associated with a given edge. | |
| bool | empty_vertex_curves (Vertex_const_descriptor v) const |
| determines whether there are no curves associated with a given vertex. | |
| bool | empty_edge_curves (Edge_const_descriptor e) const |
| determines whether there are no curves associated with a given edge. | |
| const X_monotone_curve_2 & | vertex_curve (Vertex_const_descriptor v) const |
| obtains the first curve assocuayed with a given vertex. | |
| const X_monotone_curve_2 & | edge_curve (Edge_const_descriptor e) const |
| obtains the first curve associated with a given edge. | |
Curve Data Modifiers | |
| void | set_point (Vertex_descriptor v, const Point_2 &p) |
| sets the point associated with a fiven vertex. | |
| void | add_vertex_curve (Vertex_descriptor v, const X_monotone_curve_2 &xcv) |
| adds an \(x\)-monotone curve to the list of curves associated with a given vertex. | |
| void | add_edge_curve (Edge_descriptor e, const X_monotone_curve_2 &xcv) |
| adds an \(x\)-monotone curve to the list of curves associated with a given edge. | |
| void | add_edge_curves (Edge_descriptor e, Curve_const_iterator begin, Curve_const_iterator end) |
| adds a range of \(x\)-monotone curves to the list of curves associated with a given vertex. | |
| void | add_vertex_curves (Vertex_descriptor v, Curve_const_iterator begin, Curve_const_iterator end) |
| adds a range of \(x\)-monotone curves to the list of curves associated with a given edge. | |
| void | clear_vertex_curves (Vertex_descriptor v) |
| clears the curves associated with a given vertex. | |
| void | clear_edge_curves (Edge_descriptor e) |
| clears the curves associated with a given edge. | |
Member Function Documentation
◆ edge_curve()
| const X_monotone_curve_2 & EnvelopeDiagram_1::edge_curve | ( | Edge_const_descriptor | e | ) | const |
obtains the first curve associated with a given edge.
- Precondition
- empty_vertex_curves(v) is false.
◆ edge_curves()
| const Curve_container & EnvelopeDiagram_1::edge_curves | ( | Edge_descriptor | e | ) | const |
obtains the diagram curves associated with a given edge.
(A non-const version is also available.)
◆ leftmost()
| Edge_const_descriptor EnvelopeDiagram_1::leftmost | ( | ) | const |
obtains the leftmost edge of the diagram.
(A non-const version is also available.)
◆ rightmost()
| Edge_const_descriptor EnvelopeDiagram_1::rightmost | ( | ) | const |
obtains the rightmost edge of the diagram.
(A non-const version is also available.)
◆ vertex_curve()
| const X_monotone_curve_2 & EnvelopeDiagram_1::vertex_curve | ( | Vertex_const_descriptor | v | ) | const |
obtains the first curve assocuayed with a given vertex.
- Precondition
- empty_vertex_curves(v) is false.
◆ vertex_curves()
| const Curve_container & EnvelopeDiagram_1::vertex_curves | ( | Vertex_descriptor | v | ) | const |
obtains the diagram curves associated with a given vertex.
(A non-const version is also available.)