CGAL 6.0.1 - 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.
SegmentDelaunayGraphTraits_2
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. | |
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 () |
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.