|
CGAL 4.14 - L Infinity Segment Delaunay Graphs
|
|
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 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.
1.8.13