SegmentDelaunayGraphTraits

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

SegmentDelaunayGraphTraits_2

Definition

The concept SegmentDelaunayGraphTraits_2 provides the traits requirements for the Segment_Delaunay_graph_2<Gt,DS> and 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.

Refines

DefaultConstructible
CopyConstructible
Assignable

Types

SegmentDelaunayGraphTraits_2::Intersections_tag

Indicates or not whether the intersecting segments are to be supported. The tag must either be CGAL::Tag_true or CGAL::Tag_false.

SegmentDelaunayGraphTraits_2::Site_2

A type for a site of the segment Delaunay graph. Must be a model of the concept SegmentDelaunayGraphSite_2.

SegmentDelaunayGraphTraits_2::Point_2

A type for a point.

SegmentDelaunayGraphTraits_2::Line_2

A type for a line. Only required if the segment Delaunay graph is inserted in a stream.

SegmentDelaunayGraphTraits_2::Ray_2

A type for a ray. Only required if the segment Delaunay graph is inserted in a stream.

SegmentDelaunayGraphTraits_2::Segment_2

A type for a segment. Only required if if the segment Delaunay graph is inserted in a stream.

SegmentDelaunayGraphTraits_2::FT

A type for the field number type of sites, points, etc..

SegmentDelaunayGraphTraits_2::RT

A type for the ring number type of sites, points, etc.

SegmentDelaunayGraphTraits_2::Arrangement_type

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. (to be done)

SegmentDelaunayGraphTraits_2::Object_2

A type representing different types of objects in two dimensions, namely: Point_2, Site_2, Line_2, Ray_2 and Segment_2.

SegmentDelaunayGraphTraits_2::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. Returns true, if the assignment was possible.

SegmentDelaunayGraphTraits_2::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.

SegmentDelaunayGraphTraits_2::Construct_svd_vertex_2

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.

SegmentDelaunayGraphTraits_2::Compare_x_2

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.

Precondition:

s1 and s2 must be points.

SegmentDelaunayGraphTraits_2::Compare_y_2

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.

Precondition:

s1 and s2 must be points.

SegmentDelaunayGraphTraits_2::Orientation_2

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.

Precondition:

the sites s1, s2 and s3 must be points.

SegmentDelaunayGraphTraits_2::Equal_2

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.

Precondition:

s1 and s2 must be points.

SegmentDelaunayGraphTraits_2::Are_parallel_2

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.

Precondition:

s1 and s2 must be segments.

SegmentDelaunayGraphTraits_2::Oriented_side_of_bisector_2

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.

SegmentDelaunayGraphTraits_2::Vertex_conflict_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).

Precondition:

the Voronoi circle of 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).

SegmentDelaunayGraphTraits_2::Finite_edge_interior_conflict_2

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.

Precondition:

the Voronoi vertices of 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_∞ define a Voronoi edge that lies on the bisector of s1 and s2 and has as endpoints the Voronoi vertices v₁₂₃ and v_1∞2 defined by the triplets s1, s2, s3 and s1, s_∞ 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₁₂₃ and v_1∞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.

Precondition:

the Voronoi vertex v₁₂₃ of 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_∞ define a Voronoi edge that lies on the bisector of v_12∞ and v_1∞2 s1 and s2 and has as endpoints the Voronoi vertices defined by the triplets s1, s2, s_∞ and s1, s_∞ 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∞ and v_1∞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.

SegmentDelaunayGraphTraits_2::Infinite_edge_interior_conflict_2

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_∞, s1, s2 and s3 define a Voronoi edge that lies on the bisector of s_∞ and s1 and has as endpoints the Voronoi vertices v_∞12 and v_∞31 defined by the triplets s_∞, s1, s2 and s_∞, s3 and s1. The sign sgn is the common sign of the distances of q from the Voronoi circles centered at the vertices v_∞12 and v_∞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.

SegmentDelaunayGraphTraits_2::Oriented_side_2

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 ℓ that contains the point site p, where ℓ is the line that passes through the Voronoi vertex of the sites s1, s2, s3 and is perpendicular to the segment site s.

Precondition:

s must be a segment and p must be a point.

SegmentDelaunayGraphTraits_2::Arrangement_type_2

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.

Access to predicate objects

Compare_x_2	gt.compare_x_2_object ()
Compare_y_2	gt.compare_y_2_object ()
Orientation_2	gt.orientation_2_object ()
Equal_2	gt.equal_2_object ()
Are_parallel_2	gt.are_parallel_2_object ()
Oriented_side_of_bisector_2	gt.oriented_side_of_bisector_test_2_object ()
Vertex_conflict_2	gt.vertex_conflict_2_object ()
Finite_edge_interior_conflict_2	gt.finite_edge_interior_conflict_2_object ()
Infinite_edge_interior_conflict_2	gt.infinite_edge_interior_conflict_2_object ()
Oriented_side_2	gt.oriented_side_2_object ()
Arrangement_type_2	gt.arrangement_type_2_object ()

Access to contructor objects

Construct_object_2	gt.construct_object_2_object ()
Construct_svd_vertex_2	gt.construct_svd_vertex_2_object ()

Access to other objects

Assign_2

gt.assign_2_object ()

Has Models

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>