CGAL 4.14  L Infinity Segment Delaunay Graphs

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 1dimensionalization of \( L_{\infty} \) bisectors between two sites which is explained in Section Bisectors and 1Dimensionalization 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.
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>
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. More...  
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 counterclockwise order s1 , s2 , s3 around \( v\). More...  
typedef Hidden_type  Oriented_side_of_bisector_2 
A predicate object type. More...  
typedef Hidden_type  Vertex_conflict_2 
A predicate object type. More...  
typedef Hidden_type  Finite_edge_interior_conflict_2 
A predicate object type. More...  
typedef Hidden_type  Infinite_edge_interior_conflict_2 
A predicate object type. More...  
typedef Hidden_type  Oriented_side_2 
A predicate object type. More...  
Access to constructor objects  
Construct_svd_vertex_2  construct_svd_vertex_2_object () 
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 counterclockwise 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
.
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.
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.
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.
q
from the \(L_{\infty}\) Voronoi vertices \( v_{12\infty}\) and \( v_{1\infty{}2}\) must be common and equal to sgn
. 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.
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.
q
from the \(L_{\infty}\) Voronoi vertices \( v_{{\infty}{1}{2}}\) and \( v_{{\infty}{3}{1}}\) must be common and equal to sgn
. typedef Hidden_type SegmentDelaunayGraphLinfTraits_2::Oriented_side_2 
A predicate object type.
First, we define the notion of (nonoriented) \(L_{\infty}\)perpendicular lines to a given nontrivial (nonoriented) 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 counterclockwise 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.
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.
s
must be a segment, p
must be a point, and p
must be contained in the interior of s
. 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
.
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 axisparallel 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 counterclockwise sense. The center of the square is at the intersection of the three \( L_{\infty} \) bisectors of the three sites.
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.