CGAL 4.9 - 2D Apollonius Graphs (Delaunay Graphs of Disks)
|
The concept ApolloniusGraphTraits_2
provides the traits requirements for the Apollonius_graph_2
class. In particular, it provides a type Site_2
, which must be a model of the concept ApolloniusSite_2
. It also provides constructions for sites and several function object types for the predicates.
CGAL::Apollonius_graph_traits_2<K,Method_tag>
CGAL::Apollonius_graph_filtered_traits_2<CK,CM,EK,EM,FK,FM>
CGAL::Apollonius_graph_2<Gt,Agds>
CGAL::Apollonius_graph_traits_2<K,Method_tag>
CGAL::Apollonius_graph_filtered_traits_2<CK,CM,EK,EM,FK,FM>
Types | |
typedef unspecified_type | Point_2 |
A type for a point. | |
typedef unspecified_type | Site_2 |
A type for an Apollonius site. More... | |
typedef unspecified_type | Line_2 |
A type for a line. More... | |
typedef unspecified_type | Ray_2 |
A type for a ray. More... | |
typedef unspecified_type | Segment_2 |
A type for a segment. More... | |
typedef unspecified_type | Object_2 |
A type representing different types of objects in two dimensions, namely: Point_2 , Site_2 , Line_2 , Ray_2 and Segment_2 . | |
typedef unspecified_type | FT |
A type for the field number type of sites. | |
typedef unspecified_type | RT |
A type for the ring number type of sites. | |
typedef unspecified_type | Assign_2 |
Must provide template <class T> bool operator() ( T& t, Object_2 o) which assigns o to t if o was constructed from an object of type T . More... | |
typedef unspecified_type | Construct_object_2 |
Must provide template <class T> Object_2 operator()( T t) that constructs an object of type Object_2 that contains t and returns it. | |
typedef unspecified_type | Construct_Apollonius_vertex_2 |
A constructor for a point of the Apollonius diagram equidistant from three sites. More... | |
typedef unspecified_type | Construct_Apollonius_site_2 |
A constructor for a dual Apollonius site (a site whose center is a vertex of the Apollonius diagram and its weight is the common distance of its center from the three defining sites). More... | |
typedef unspecified_type | Compare_x_2 |
A predicate object type. More... | |
typedef unspecified_type | Compare_y_2 |
A predicate object type. More... | |
typedef unspecified_type | Compare_weight_2 |
A predicate object type. More... | |
typedef unspecified_type | Orientation_2 |
A predicate object type. More... | |
typedef unspecified_type | Is_hidden_2 |
A predicate object type. More... | |
typedef unspecified_type | Oriented_side_of_bisector_2 |
A predicate object type. More... | |
typedef unspecified_type | Vertex_conflict_2 |
A predicate object type. More... | |
typedef unspecified_type | Finite_edge_interior_conflict_2 |
A predicate object type. More... | |
typedef unspecified_type | Infinite_edge_interior_conflict_2 |
A predicate object type. More... | |
typedef unspecified_type | Is_degenerate_edge_2 |
A predicate object type. More... | |
Creation | |
ApolloniusGraphTraits_2 () | |
Default constructor. | |
ApolloniusGraphTraits_2 (ApolloniusGraphTraits_2 other) | |
Copy constructor. | |
ApolloniusGraphTraits_2 | operator= (ApolloniusGraphTraits_2 other) |
Assignment operator. | |
Access to constructor objects | |
Construct_object_2 | construct_object_2_object () |
Construct_Apollonius_vertex_2 | construct_Apollonius_vertex_2_object () |
Construct_Apollonius_site_2 | construct_Apollonius_site_2_object () |
Access to other objects | |
Assign_2 | assign_2_object () |
Must provide template <class T> bool operator() ( T& t, Object_2 o)
which assigns o
to t
if o
was constructed from an object of type T
.
Returns true
, if the assignment was possible.
A predicate object type.
Must provide Comparison_result operator()(Site_2 s1, Site_2 s2)
, which compares the weights of s1
and s2
.
A predicate object type.
Must provide Comparison_result operator()(Site_2 s1, Site_2 s2)
, which compares the \( x\)-coordinates of the centers of s1
and s2
.
A predicate object type.
Must provide Comparison_result operator()(Site_2 s1, Site_2 s2)
, which compares the \( y\)-coordinates of the centers of s1
and s2
.
A constructor for a dual Apollonius site (a site whose center is a vertex of the Apollonius diagram and its weight is the common distance of its center from the three defining sites).
Must provide Site_2 operator()(Site_2 s1, Site_2 s2, Site_2 s3)
, which constructs a dual site whose center \( c\) is equidistant from s1
, s2
and s3
, and its weight is equal to the (signed) distance of \( c\) from s1
(or s2
or s3
).
Must also provide Line_2 operator()(Site_2 s1, Site_2 s2)
, which constructs a line bitangent to s1
and s2
. This line is the dual site of s1
, s2
and the site at infinity; it can be viewed as a dual Apollonius site whose center is at infinity and its weight is infinite.
A constructor for a point of the Apollonius diagram equidistant from three sites.
Must provide Point_2 operator()(Site_2 s1, Site_2 s2, Site_2 s3)
, which constructs a point equidistant from the sites s1
, s2
and s3
.
A predicate object type.
Must provide bool operator()(Site_2 s1, Site_2 s2, Site_2 s3, Site_2 s4, Site_2 q, bool b)
. The sites s1
, s2
, s3
and s4
define an Apollonius edge that lies on the bisector of s1
and s2
and has as endpoints the Apollonius vertices defined by the triplets s1
, s2
, s3
and s1
, s4
and s2
. The Boolean b
denotes if the two Apollonius vertices are in conflict with the site q
(in which case b
should be true
, otherwise false
). In case that b
is true
, the predicate returns true
if and only if the entire Apollonius edge is in conflict with q
. If b
is false
, the predicate returns false
if and only if q
is not in conflict with the Apollonius edge.
s1
, s2
, s3
, and s1
, s4
, s2
must exist.Must also provide bool operator()(Site_2 s1, Site_2 s2, Site_2 s3, Site_2 q, bool b)
. The sites s1
, s2
, s3
and the site at infinity \( s_\infty\) define an Apollonius edge that lies on the bisector of s1
and s2
and has as endpoints the Apollonius vertices defined by the triplets s1
, s2
, s3
and s1
, \( s_\infty\) and s2
(the second Apollonius vertex is actually at infinity). The Boolean b
denotes if the two Apollonius vertices are in conflict with the site q
(in which case b
should be true
, otherwise false
). In case that b
is true
, the predicate returns true
if and only if the entire Apollonius edge is in conflict with q
. If b
is false
, the predicate returns false
if and only if q
is not in conflict with the Apollonius edge.
s1
, s2
, s3
must exist.Must finally provide bool operator()(Site_2 s1, Site_2 s2, Site_2 q, bool b)
. The sites s1
, s2
and the site at infinity \( s_\infty\) define an Apollonius edge that lies on the bisector of s1
and s2
and has as endpoints the Apollonius vertices defined by the triplets s1
, s2
, \( s_\infty\) and s1
, \( s_\infty\) and s2
(both Apollonius vertices are actually at infinity). The Boolean b
denotes if the two Apollonius vertices are in conflict with the site q
(in which case b
should be true
, otherwise false
). In case that b
is true
, the predicate returns true
if and only if the entire Apollonius edge is in conflict with q
. If b
is false
, the predicate returns false
if and only if q
is not in conflict with the Apollonius edge.
A predicate object type.
Must provide bool operator()(Site_2 s1, Site_2 s2, Site_2 s3, Site_2 q, bool b)
. The sites \( s_\infty\), s1
, s2
and s3
define an Apollonius edge that lies on the bisector of \( s_\infty\) and s1
and has as endpoints the Apollonius vertices defined by the triplets \( s_\infty\), s1
, s2
and \( s_\infty\), s3
and s1
. The Boolean b
denotes if the two Apollonius vertices are in conflict with the site q
(in which case b
should be true
, otherwise false
. In case that b
is true
, the predicate returns true
if and only if the entire Apollonius edge is in conflict with q
. If b
is false
, the predicate returns false
if and only if q
is not in conflict with the Apollonius edge.
A predicate object type.
Must provide bool operator()(Site_2 s1, Site_2 s2, Site_2 s3, Site_2 s4)
. It returns true
if the Apollonius edge defined by s1
, s2
, s3
and s4
is degenerate, false
otherwise. An Apollonius edge is called degenerate if its two endpoints coincide.
s1
, s2
, s3
, and s1
, s4
, s2
must exist. A predicate object type.
Must provide bool operator()(Site_2 s1, Site_2 s2)
, which returns true
if the circle corresponding to s2
is contained in the closure of the disk corresponding to s1
, false
otherwise.
A type for a line.
Only required if access to the dual of the Apollonius graph is required or if the primal or dual diagram are inserted in a stream.
A predicate object type.
Must provide Orientation operator()(Site_2 s1, Site_2 s2, Site_2 s3)
, which performs the usual orientation test for the centers of the three sites s1
, s2
and s3
.
Must also provide Orientation operator()(Site_2 s1, Site_2 s2, Site_2 s3, Site_2 p1, Site_2 p2)
, which performs the usual orientation test for the Apollonius vertex of s1
, s2
, s3
and the centers of p1
and p2
.
s1
, s2
and s3
must exist. A predicate object type.
Must provide Oriented_side operator()(Site_2 s1, Site_2 s2, Point_2 p)
, which returns the oriented side of the bisector of s1
and s2
that contains p
. Returns ON_POSITIVE_SIDE
if p
lies in the half-space of s1
(i.e., p
is closer to s1
than s2
); returns ON_NEGATIVE_SIDE
if p
lies in the half-space of s2
; returns ON_ORIENTED_BOUNDARY
if p
lies on the bisector of s1
and s2
.
A type for a ray.
Only required if access to the dual of the Apollonius graph is required or if the primal or dual diagram are inserted in a stream.
A type for a segment.
Only required if access to the dual of the Apollonius graph is required or if the primal or dual diagram are inserted in a stream.
A type for an Apollonius site.
Must be a model of the concept ApolloniusSite_2
.
A predicate object type.
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 dual Apollonius site of s1
, s2
, s3
.
s1
, s2
, s3
must exist.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 bitangent line of s1
, s2
(a degenerate dual Apollonius site, with its center at infinity).