CGAL 5.4.4 - 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 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.
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 counter-clockwise 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 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
.
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 (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.
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 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.
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.