CGAL 5.1.2 - 2D Segment Delaunay Graphs
|
The concept SegmentDelaunayGraphTraits_2
provides the traits requirements for the CGAL::Segment_Delaunay_graph_2<Gt,DS>
and CGAL::Segment_Delaunay_graph_hierarchy_2<Gt,STag,DS>
classes. In particular, it provides a type Site_2
, which must be a model of the concept SegmentDelaunayGraphSite_2
. It also provides constructions for sites and several function object types for the predicates.
CGAL::Segment_Delaunay_graph_traits_2<K,MTag>
CGAL::Segment_Delaunay_graph_traits_without_intersections_2<K,MTag>
CGAL::Segment_Delaunay_graph_filtered_traits_2<CK,CM,EK,EM,FK,FM>
CGAL::Segment_Delaunay_graph_filtered_traits_without_intersections_2<CK,CM,EK,EM,FK,FM>
SegmentDelaunayGraphSite_2
CGAL::Segment_Delaunay_graph_2<Gt,DS>
CGAL::Segment_Delaunay_graph_hierarchy_2<Gt,STag,DS>
CGAL::Segment_Delaunay_graph_traits_2<K,MTag>
CGAL::Segment_Delaunay_graph_traits_without_intersections_2<K,MTag>
CGAL::Segment_Delaunay_graph_filtered_traits_2<CK,CM,EK,EM,FK,FM>
CGAL::Segment_Delaunay_graph_filtered_traits_without_intersections_2<CK,CM,EK,EM,FK,FM>
Types | |
typedef unspecified_type | Intersections_tag |
Indicates or not whether the intersecting segments are to be supported. More... | |
typedef unspecified_type | Site_2 |
A type for a site of the segment Delaunay graph. More... | |
typedef unspecified_type | Point_2 |
A type for a point. | |
typedef unspecified_type | Line_2 |
A type for a line. More... | |
typedef unspecified_type | Ray_2 |
A type for a ray. More... | |
typedef unspecified_type | Segment_2 |
A type for a segment. More... | |
typedef unspecified_type | FT |
A type for the field number type of sites, points, etc... | |
typedef unspecified_type | RT |
A type for the ring number type of sites, points, etc. | |
typedef unspecified_type | Arrangement_type |
An enumeration type that indicates the type of the arrangement of two sites. More... | |
typedef unspecified_type | Object_2 |
A type representing different types of objects in two dimensions, namely: Point_2 , Site_2 , Line_2 , Ray_2 and Segment_2 . | |
typedef unspecified_type | Assign_2 |
Must provide template <class T> bool operator() ( T& t, Object_2 o) which assigns o to t if o was constructed from an object of type T . More... | |
typedef unspecified_type | Construct_object_2 |
Must provide template <class T> Object_2 operator()( T t) that constructs an object of type Object_2 that contains t and returns it. | |
typedef unspecified_type | Construct_svd_vertex_2 |
A constructor for a point of the segment Voronoi diagram equidistant from three sites. More... | |
typedef unspecified_type | Compare_x_2 |
A predicate object type. More... | |
typedef unspecified_type | Compare_y_2 |
A predicate object type. More... | |
typedef unspecified_type | Less_x_2 |
A predicate object type. More... | |
typedef unspecified_type | Less_y_2 |
A predicate object type. More... | |
typedef unspecified_type | Orientation_2 |
A predicate object type. More... | |
typedef unspecified_type | Equal_2 |
A predicate object type. More... | |
typedef unspecified_type | Are_parallel_2 |
A predicate object type. More... | |
typedef unspecified_type | Oriented_side_of_bisector_2 |
A predicate object type. More... | |
typedef unspecified_type | Vertex_conflict_2 |
A predicate object type. More... | |
typedef unspecified_type | Finite_edge_interior_conflict_2 |
A predicate object type. More... | |
typedef unspecified_type | Infinite_edge_interior_conflict_2 |
A predicate object type. More... | |
typedef unspecified_type | Oriented_side_2 |
A predicate object type. More... | |
typedef unspecified_type | Arrangement_type_2 |
A predicate object type. More... | |
Access to contructor objects | |
Construct_object_2 | construct_object_2_object () |
Construct_svd_vertex_2 | construct_svd_vertex_2_object () |
Access to other objects | |
Assign_2 | assign_2_object () |
A predicate object type.
Must provide bool operator()(Site_2 s1, Site_2 s2)
, which determines is the segments represented by the sites s1
and s2
are parallel.
s1
and s2
must be segments. An enumeration type that indicates the type of the arrangement of two sites.
The possible values are DISJOINT
, IDENTICAL
, CROSSING
, TOUCHING_1
, TOUCHING_2
, TOUCHING_11
, TOUCHING_12
, TOUCHING_21
, TOUCHING_22
, OVERLAPPING_11
, OVERLAPPING_12
, OVERLAPPING_21
, OVERLAPPING_22
, INTERIOR
, INTERIOR_1
, INTERIOR_2
, TOUCHING_11_INTERIOR_1
, TOUCHING_11_INTERIOR_2
, TOUCHING_12_INTERIOR_1
, TOUCHING_12_INTERIOR_2
, TOUCHING_21_INTERIOR_1
, TOUCHING_21_INTERIOR_2
, TOUCHING_22_INTERIOR_1
, TOUCHING_22_INTERIOR_2
. A detailed description of the meaning of these values is shown the end of the reference manual for this concept.
A predicate object type.
Must provide Arrangement_type operator()(Site_2 s1, Site_2 s2)
that returns the type of the arrangement of the two sites s1
and s2
.
Must provide template <class T> bool operator() ( T& t, Object_2 o)
which assigns o
to t
if o
was constructed from an object of type T
.
Returns true
, if the assignment was possible.
A predicate object type.
Must provide Comparison_result operator()(Site_2 s1, Site_2 s2)
, which compares the \( x\)-coordinates of the points represented by the sites s1
and s2
.
s1
and s2
must be points. A predicate object type.
Must provide Comparison_result operator()(Site_2 s1, Site_2 s2)
, which compares the \( y\)-coordinates of the points represented by the sites s1
and s2
.
s1
and s2
must be points. A constructor for a point of the segment Voronoi diagram equidistant from three sites.
Must provide Point_2 operator()(Site_2 s1, Site_2 s2, Site_2 s3)
, which constructs a point equidistant from the sites s1
, s2
and s3
.
A predicate object type.
Must provide bool operator()(Site_2 s1, Site_2 s2)
, which determines is the points represented by the sites s1
and s2
are identical.
s1
and s2
must be points. A predicate object type.
Must provide bool operator()(Site_2 s1, Site_2 s2, Site_2 s3, Site_2 s4, Site_2 q, Sign sgn)
. The sites s1
, s2
, s3
and s4
define a Voronoi edge that lies on the bisector of s1
and s2
and has as endpoints the Voronoi vertices defined by the triplets s1
, s2
, s3
and s1
, s4
and s2
. The sign sgn
is the common sign of the distance of the site q
from the Voronoi circle of the triplets s1
, s2
, s3
and s1
, s4
and s2
. In case that sgn
is equal to NEGATIVE
, the predicate returns true
if and only if the entire Voronoi edge is in conflict with q
. If sgn
is equal to POSITIVE
or ZERO
, the predicate returns false
if and only if q
is not in conflict with the Voronoi edge.
s1
, s2
, s3
, and s1
, s4
, s2
must exist.Must also provide bool operator()(Site_2 s1, Site_2 s2, Site_2 s3, Site_2 q, Sign sgn)
. The sites s1
, s2
, s3
and the site at infinity \( s_\infty\) define a Voronoi edge that lies on the bisector of s1
and s2
and has as endpoints the Voronoi vertices \( v_{123}\) and \( v_{1\infty{2}}\) defined by the triplets s1
, s2
, s3
and s1
, \( s_\infty\) and s2
(the second vertex is actually at infinity). The sign sgn
is the common sign of the distance of the site q
from the two Voronoi circles centered at the Voronoi vertices \( v_{123}\) and \( v_{1\infty{2}}\). In case that sgn
is NEGATIVE
, the predicate returns true
if and only if the entire Voronoi edge is in conflict with q
. If sgn
is POSITIVE
or ZERO
, the predicate returns false
if and only if q
is not in conflict with the Voronoi edge.
s1
, s2
, s3
must exist.Must finally provide bool operator()(Site_2 s1, Site_2 s2, Site_2 q, Sign sgn)
. The sites s1
, s2
and the site at infinity \( s_\infty\) define a Voronoi edge that lies on the bisector of \( v_{12\infty}\) and \( v_{1\infty{}2}\) s1
and s2
and has as endpoints the Voronoi vertices defined by the triplets s1
, s2
, \( s_\infty\) and s1
, \( s_\infty\) and s2
(both vertices are actually at infinity). The sign sgn
denotes the common sign of the distance of the site q
from the Voronoi circles centered at \( v_{12\infty}\) and \( v_{1\infty{}2}\). If sgn
is NEGATIVE
, the predicate returns true
if and only if the entire Voronoi edge is in conflict with q
. If POSITIVE
or ZERO
is false
, the predicate returns false
if and only if q
is not in conflict with the Voronoi edge.
A predicate object type.
Must provide bool operator()(Site_2 s1, Site_2 s2, Site_2 s3, Site_2 q, Sign sgn)
. The sites \( s_\infty\), s1
, s2
and s3
define a Voronoi edge that lies on the bisector of \( s_\infty\) and s1
and has as endpoints the Voronoi vertices \( v_{\infty{}12}\) and \( v_{\infty{}31}\) defined by the triplets \( s_\infty\), s1
, s2
and \( s_\infty\), s3
and s1
. The sign sgn
is the common sign of the distances of q
from the Voronoi circles centered at the vertices \( v_{\infty{}12}\) and \( v_{\infty{}31}\). If sgn
is NEGATIVE
, the predicate returns true
if and only if the entire Voronoi edge is in conflict with q
. If sgn
is POSITIVE
or ZERO
, the predicate returns false
if and only if q
is not in conflict with the Voronoi edge.
Indicates or not whether the intersecting segments are to be supported.
The tag must either be CGAL::Tag_true
or CGAL::Tag_false
.
A predicate object type.
Must provide bool operator()(Point_2 p1, Point_2 p2)
, which returns true
if p1.x() < p2.x()
.
A predicate object type.
Must provide bool operator()(Point_2 p1, Point_2 p2)
, which returns true
if p1.y() < p2.y()
.
A type for a line.
Only required if the segment Delaunay graph is inserted in a stream.
A predicate object type.
Must provide Orientation operator()(Site_2 s1, Site_2 s2, Site_2 s3)
, which performs the usual orientation test for three points. s1
, s2
and s3
.
s1
, s2
and s3
must be points. A predicate object type.
Must provide Oriented_side operator()(Site_1 s1, Site_2 s2, Site_2 s3, Site_2 s, Site_2 p)
. Determines the oriented side of the line \( \ell\) that contains the point site p
, where \( \ell\) is the line that passes through the Voronoi vertex of the sites s1
, s2
, s3
and is perpendicular to the segment site s
.
s
must be a segment and p
must be a point. A predicate object type.
Must provide Oriented_side operator()(Site_2 s1, Site_2 s2, Point_2 p)
, which returns the oriented side of the bisector of s1
and s2
that contains p
. Returns ON_POSITIVE_SIDE
if p
lies in the half-space of s1
(i.e., p
is closer to s1
than s2
); returns ON_NEGATIVE_SIDE
if p
lies in the half-space of s2
; returns ON_ORIENTED_BOUNDARY
if p
lies on the bisector of s1
and s2
.
A type for a ray.
Only required if the segment Delaunay graph is inserted in a stream.
A type for a segment.
Only required if if the segment Delaunay graph is inserted in a stream.
A type for a site of the segment Delaunay graph.
Must be a model of the concept SegmentDelaunayGraphSite_2
.
A predicate object type.
Must provide Sign operator()(Site_2 s1, Site_2 s2, Site_2 s3, Site_2 q)
, which returns the sign of the distance of q
from the Voronoi circle of s1
, s2
, s3
(the Voronoi circle of three sites s1
, s2
, s3
is a circle co-tangent to all three sites, that touches them in that order as we walk on its circumference in the counter-clockwise sense).
s1
, s2
, s3
must exist.Must also provide Sign operator()(Site_2 s1, Site_2 s2, Site_2 q)
, which returns the sign of the distance of q
from the bitangent line of s1
, s2
(a degenerate Voronoi circle, with its center at infinity).