SegmentDelaunayGraphLinfTraits_2 Concept Reference

Definition

The concept SegmentDelaunayGraphLinfTraits_2 provides traits for constructing the segment Delaunay graph under the \( L_{\infty} \) distance. The segment Delaunay graph is the dual of the segment Voronoi diagram. We stress that we consider the 1-dimensionalization of \( L_{\infty} \) bisectors between two sites which is explained in Section Bisectors and 1-Dimensionalization of the User Manual, and this reflects on the constructed graph (and its dual diagram). These traits should be used in the Gt template parameter of the CGAL::Segment_Delaunay_graph_Linf_2<Gt,DS> and CGAL::Segment_Delaunay_graph_Linf_hierarchy_2<Gt,STag,DS> class templates. The concept is a refinement of SegmentDelaunayGraphTraits_2. 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.

In contrast with \( L_{2} \), the concept also contains drawing methods for the edges of the \( L_{\infty} \) segment Voronoi diagram (class templates Construct_sdg_bisector_2, Construct_sdg_bisector_ray_2, and Construct_sdg_bisector_segment_2). These methods are used when, additionally, the tag type Has_bisector_constructions_type is defined in the concept.

We only describe the refined and additional requirements of the SegmentDelaunayGraphLinfTraits_2 concept with respect to the SegmentDelaunayGraphTraits_2 concept.

Refines

SegmentDelaunayGraphTraits_2

Has models

CGAL::Segment_Delaunay_graph_Linf_traits_2<K,MTag>

CGAL::Segment_Delaunay_graph_Linf_traits_without_intersections_2<K,MTag>

CGAL::Segment_Delaunay_graph_Linf_filtered_traits_2<CK,CM,EK,EM,FK,FM>

CGAL::Segment_Delaunay_graph_Linf_filtered_traits_without_intersections_2<CK,CM,EK,EM,FK,FM>

See also

SegmentDelaunayGraphSite_2

CGAL::Segment_Delaunay_graph_Linf_2<Gt,DS>

CGAL::Segment_Delaunay_graph_Linf_hierarchy_2<Gt,STag,DS>

Concepts
concept	Construct_sdg_bisector_2
	The class template drawing the \(L_{\infty}\) bisector between two sites. More...
concept	Construct_sdg_bisector_ray_2
	The class template drawing the \(L_{\infty}\) edge between two sites, that is bounded by another site and the dummy site \(s_{\infty}\) (at infinity). More...
concept	Construct_sdg_bisector_segment_2
	The class template drawing the \(L_{\infty}\) edge between two sites, that is bounded by two other sites. More...

Bisector construction tag
typedef char	Has_bisector_constructions_type
	If this tag type is defined in the concept, then the concept should also contain three bisector drawing class templates, Construct_sdg_bisector_2, Construct_sdg_bisector_ray_2, and Construct_sdg_bisector_segment_2, that will be used when drawing the dual of the \(L_{\infty}\) segment Delaunay graph.

Types
typedef Hidden_type	Construct_svd_vertex_2
	A constructor for the point \( v \) at which the three \( L_{\infty} \) bisectors between the three given sites s1, s2 and s3 intersect and the regions of s1, s2 and s3 appear in the counter-clockwise order s1, s2, s3 around \( v\).
typedef Hidden_type	Oriented_side_of_bisector_2
	A predicate object type.
typedef Hidden_type	Vertex_conflict_2
	A predicate object type.
typedef Hidden_type	Finite_edge_interior_conflict_2
	A predicate object type.
typedef Hidden_type	Infinite_edge_interior_conflict_2
	A predicate object type.
typedef Hidden_type	Oriented_side_2
	A predicate object type.

Access to predicate objects
Oriented_side_of_bisector_2	oriented_side_of_bisector_test_2_object ()
Vertex_conflict_2	vertex_conflict_2_object ()
Finite_edge_interior_conflict_2	finite_edge_interior_conflict_2_object ()
Infinite_edge_interior_conflict_2	infinite_edge_interior_conflict_2_object ()
Oriented_side_2	oriented_side_2_object ()

Access to constructor objects
Construct_svd_vertex_2	construct_svd_vertex_2_object ()

Member Typedef Documentation

Construct_svd_vertex_2

typedef Hidden_type SegmentDelaunayGraphLinfTraits_2::Construct_svd_vertex_2

A constructor for the point \( v \) at which the three \( L_{\infty} \) bisectors between the three given sites s1, s2 and s3 intersect and the regions of s1, s2 and s3 appear in the counter-clockwise order s1, s2, s3 around \( v\).

Point \( v \) is equidistant from the three sites, under the \( L_{\infty} \) distance.

It must provide Point_2 operator()(Site_2 s1, Site_2 s2, Site_2 s3), which constructs this point \( v \) which is equidistant (under the \( L_{\infty} \) distance) from the sites s1, s2 and s3.

Finite_edge_interior_conflict_2

typedef Hidden_type SegmentDelaunayGraphLinfTraits_2::Finite_edge_interior_conflict_2

A predicate object type.

It 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 \(L_{\infty}\) Voronoi vertices \( v_{123} \) and \( v_{142} \) defined by the ordered triplets s1, s2, s3 and s1, s4, s2, respectively. The sign sgn is the common sign of the distance of the site q from the \(L_{\infty}\) Voronoi square of the triplets s1, s2, s3 and s1, s4, 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 \(L_{\infty}\) Voronoi vertices \( v_{123} \) and \( v_{142} \) must exist and the sign of the distance of q from these two vertices must be common and equal to sgn.

It 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 dummy site at infinity \( s_\infty\) define a Voronoi edge that lies on the \(L_{\infty}\) 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\), s2 (the second vertex is at infinity). The sign sgn is the common sign of the distance of the site q from the two \(L_{\infty}\) Voronoi squares 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.

Precondition

the \(L_{\infty}\) Voronoi vertex \( v_{123}\) of s1, s2, s3 must exist and the sign of the distance of q from the vertices \( v_{123}\) and \( v_{1{\infty}2}\) must be common and equal to sgn.

It must finally provide bool operator()(Site_2 s1, Site_2 s2, Site_2 q, Sign sgn). The sites s1, s2 and the dummy site at infinity \( s_\infty\) define a Voronoi edge that is equal to the \(L_{\infty}\) bisector of s1 and s2. The endpoints of this edge are the \(L_{\infty}\) Voronoi vertices \( v_{12\infty}\) and \( v_{1\infty{}2}\), defined by the triplets s1, s2, \( s_\infty\) and s1, \( s_\infty\), s2 (both vertices are at infinity). The sign sgn denotes the common sign of the distance of the site q from the \(L_{\infty}\) Voronoi squares 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 sgn is POSITIVE or ZERO, the predicate returns false if and only if q is not in conflict with the Voronoi edge.

Precondition

the sign of the distance of q from the \(L_{\infty}\) Voronoi vertices \( v_{12\infty}\) and \( v_{1\infty{}2}\) must be common and equal to sgn.

Has_bisector_constructions_type

typedef char SegmentDelaunayGraphLinfTraits_2::Has_bisector_constructions_type

If this tag type is defined in the concept, then the concept should also contain three bisector drawing class templates, Construct_sdg_bisector_2, Construct_sdg_bisector_ray_2, and Construct_sdg_bisector_segment_2, that will be used when drawing the dual of the \(L_{\infty}\) segment Delaunay graph.

This is the only way to draw correctly the \(L_{\infty}\) segment Voronoi diagram. If this type is omitted, then the default drawing methods are used, which are only good for the \(L_2\) segment Voronoi diagram.

Infinite_edge_interior_conflict_2

typedef Hidden_type SegmentDelaunayGraphLinfTraits_2::Infinite_edge_interior_conflict_2

A predicate object type.

It must provide bool operator()(Site_2 s1, Site_2 s2, Site_2 s3, Site_2 q, Sign sgn). Let \(s_\infty\) be the dummy site at infinity. 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 \(L_{\infty}\) Voronoi vertices \( v_{\infty{}12}\) and \( v_{\infty{}31}\) defined by the triplets \( s_\infty\), s1, s2 and \( s_\infty\), s3, s1, respectively. The sign sgn is the common sign of the distances of q from the \(L_{\infty}\) Voronoi squares centered at the vertices \( v_{\infty{}{1}{2}}\) 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.

Precondition

the sign of the distance of q from the \(L_{\infty}\) Voronoi vertices \( v_{{\infty}{1}{2}}\) and \( v_{{\infty}{3}{1}}\) must be common and equal to sgn.

Oriented_side_2

typedef Hidden_type SegmentDelaunayGraphLinfTraits_2::Oriented_side_2

A predicate object type.

First, we define the notion of (non-oriented) \(L_{\infty}\)-perpendicular lines to a given non-trivial (non-oriented) segment \( s \). If \( s \) is horizontal, then the perpendicular lines are the vertical lines. If \( s \) is vertical, then the perpendicular lines are the horizontal lines. If \( s \) has positive slope, then the perpendicular lines are the lines of slope -1. If \( s \) has negative slope, then the perpendicular lines are the lines of slope +1.

Since CGAL segments have also an orientation, we also orient \(L_{\infty}\)-perpendicular lines, as follows. For an oriented segment \( s \), we orient its \(L_{\infty}\)-perpendicular lines so that the lines' orientation is closest to the following orientation: the orientation of \( s \) rotated counter-clockwise by \( \pi/2 \).

Let s be a segment and p a point contained in its interior. Let \( \ell\) be the line which is \(L_{\infty}\)-perpendicular to segment s and is passing through point p.

The predicate object type must provide Oriented_side operator()(Site_1 s1, Site_2 s2, Site_2 s3, Site_2 s, Site_2 p). This determines the oriented side of the line \( \ell\) in which the \(L_{\infty}\) Voronoi vertex \(v_{123}\) of the sites s1, s2, s3 is contained.

Precondition

s must be a segment, p must be a point, and p must be contained in the interior of s.

The predicate object type must also provide bool operator()(Site_2 s1, Site_2 s2, Site_2 s, Site_2 p). This determines the oriented side of the line \( \ell\) in which the \(L_{\infty}\) Voronoi vertex \(v_{12\infty}\) of the sites s1, s2, \(s_{\infty}\) is contained.

Precondition

s must be a segment, p must be a point, and p must be contained in the interior of s.

Oriented_side_of_bisector_2

typedef Hidden_type SegmentDelaunayGraphLinfTraits_2::Oriented_side_of_bisector_2

A predicate object type.

It must provide Oriented_side operator()(Site_2 s1, Site_2 s2, Point_2 p), which returns the oriented side of the \( L_{\infty} \) bisector of s1 and s2 that contains p. It returns ON_POSITIVE_SIDE if p lies in the nearest region of s1 (i.e., p is closer to s1 than s2); returns ON_NEGATIVE_SIDE if p lies in the nearest region of s2; returns ON_ORIENTED_BOUNDARY if p lies on the \( L_{\infty} \) bisector of s1 and s2.

Vertex_conflict_2

typedef Hidden_type SegmentDelaunayGraphLinfTraits_2::Vertex_conflict_2

A predicate object type.

It 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 \( L_{\infty} \) Voronoi square of s1, s2, s3. The \( L_{\infty} \) Voronoi square of three sites s1, s2, s3 is an axis-parallel square which is passing through all three sites and touches them in the s1, s2, s3 order as we walk on the square in the counter-clockwise sense. The center of the square is at the intersection of the three \( L_{\infty} \) bisectors of the three sites.

Precondition

the \( L_{\infty} \) Voronoi square of s1, s2, s3 must exist.

It 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 \( L_{\infty} \) Voronoi square of sites s1, s2, \(s_\infty\), where \(s_\infty\) is the dummy site at infinity. This is a degenerate \( L_{\infty} \) Voronoi square, with its center at infinity, which is either a line or a right angle wedge.