CGAL 6.1 - L Infinity Segment Delaunay Graphs

Loading...
Searching...
No Matches
List of all members | Classes
SegmentDelaunayGraphLinfTraits_2 Concept Reference
Reference Manual » Concepts

## Definition

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.

Refines
  `SegmentDelaunayGraphTraits_2`

Has models
  `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>`

See also
  `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 counterclockwise 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 ()

## Member Typedef Documentation

## ◆ Construct_svd_vertex_2

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`.

## ◆ Finite_edge_interior_conflict_2

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.

Precondition
  the \(L_{\infty}\) Voronoi vertices \( v_{123} \) and \( v_{142} \) must exist and the sign of the distance of `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.

Precondition
  the \(L_{\infty}\) Voronoi vertex \( v_{123}\) of `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.

Precondition
  the sign of the distance of `q` from the \(L_{\infty}\) Voronoi vertices \( v_{12\infty}\) and \( v_{1\infty{}2}\) must be common and equal to `sgn`.

## ◆ Has_bisector_constructions_type

typedef char SegmentDelaunayGraphLinfTraits_2::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.

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.

## ◆ Infinite_edge_interior_conflict_2

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.

Precondition
  the sign of the distance of `q` from the \(L_{\infty}\) Voronoi vertices \( v_{{\infty}{1}{2}}\) and \( v_{{\infty}{3}{1}}\) must be common and equal to `sgn`.

## ◆ Oriented_side_2

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 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.

Precondition
  `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.

Precondition
  `s` must be a segment, `p` must be a point, and `p` must be contained in the interior of `s`.

## ◆ Oriented_side_of_bisector_2

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`.

## ◆ Vertex_conflict_2

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 counterclockwise sense. The center of the square is at the intersection of the three \( L_{\infty} \) bisectors of the three sites.

Precondition
  the \( L_{\infty} \) Voronoi square of `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.