CGAL 4.11 - L Infinity Segment Delaunay Graphs
|
The concept SegmentDelaunayGraphLinfTraits_2
provides traits for constructing the segment Delaunay graph under the L∞ distance. The segment Delaunay graph is the dual of the segment Voronoi diagram. We stress that we consider the 1-dimensionalization of L∞ 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 L2, the concept also contains drawing methods for the edges of the L∞ 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∞ bisector between two sites. More... | |
concept | Construct_sdg_bisector_ray_2 |
The class template drawing the L∞ edge between two sites, that is bounded by another site and the dummy site s∞ (at infinity). More... | |
concept | Construct_sdg_bisector_segment_2 |
The class template drawing the L∞ 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∞ segment Delaunay graph. More... | |
Types | |
typedef Hidden_type | Construct_svd_vertex_2 |
A constructor for the point v at which the three L∞ 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∞ 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∞ 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∞ 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∞ Voronoi vertices v123 and v142 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∞ 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∞ define a Voronoi edge that lies on the L∞ bisector of s1
and s2
and has as endpoints the Voronoi vertices v123 and v1∞2 defined by the triplets s1
, s2
, s3
and s1
, s∞, 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∞ Voronoi squares centered at the Voronoi vertices v123 and v1∞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 v123 and v1∞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∞ define a Voronoi edge that is equal to the L∞ bisector of s1
and s2
. The endpoints of this edge are the L∞ Voronoi vertices v12∞ and v1∞2, defined by the triplets s1
, s2
, s∞ and s1
, s∞, s2
(both vertices are at infinity). The sign sgn
denotes the common sign of the distance of the site q
from the L∞ Voronoi squares centered at v12∞ and v1∞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∞ Voronoi vertices v12∞ and v1∞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∞ segment Delaunay graph.
This is the only way to draw correctly the L∞ segment Voronoi diagram. If this type is omitted, then the default drawing methods are used, which are only good for the L2 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∞ be the dummy site at infinity. 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 L∞ Voronoi vertices v∞12 and v∞31 defined by the triplets s∞, s1
, s2
and s∞, s3
, s1
, respectively. The sign sgn
is the common sign of the distances of q
from the L∞ Voronoi squares 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.
q
from the L∞ Voronoi vertices v∞12 and v∞31 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∞-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∞-perpendicular lines, as follows. For an oriented segment s, we orient its L∞-perpendicular lines so that the lines' orientation is closest to the following orientation: the orientation of s rotated counter-clockwise by π/2.
Let s
be a segment and p
a point contained in its interior. Let ℓ be the line which is L∞-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 ℓ in which the L∞ Voronoi vertex v123 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 ℓ in which the L∞ Voronoi vertex v12∞ of the sites s1
, s2
, s∞ 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∞ 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∞ 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∞ Voronoi square of s1
, s2
, s3
. The L∞ 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∞ 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∞ Voronoi square of sites s1
, s2
, s∞, where s∞ is the dummy site at infinity. This is a degenerate L∞ Voronoi square, with its center at infinity, which is either a line or a right angle wedge.