ApolloniusGraphTraits_2 Concept Reference

Definition

Refines

TriangulationTraits_2

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.

Has models

CGAL::Apollonius_graph_traits_2<K,Method_tag>

CGAL::Apollonius_graph_filtered_traits_2<CK,CM,EK,EM,FK,FM>

See also

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.
typedef unspecified_type	Line_2
	A type for a line.
typedef unspecified_type	Ray_2
	A type for a ray.
typedef unspecified_type	Segment_2
	A type for a segment.
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.
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.
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).
typedef unspecified_type	Compare_x_2
	A predicate object type.
typedef unspecified_type	Compare_y_2
	A predicate object type.
typedef unspecified_type	Compare_weight_2
	A predicate object type.
typedef unspecified_type	Orientation_2
	A predicate object type.
typedef unspecified_type	Is_hidden_2
	A predicate object type.
typedef unspecified_type	Oriented_side_of_bisector_2
	A predicate object type.
typedef unspecified_type	Vertex_conflict_2
	A predicate object type.
typedef unspecified_type	Finite_edge_interior_conflict_2
	A predicate object type.
typedef unspecified_type	Infinite_edge_interior_conflict_2
	A predicate object type.
typedef unspecified_type	Is_degenerate_edge_2
	A predicate object type.

Creation
	ApolloniusGraphTraits_2 ()
	Default constructor.
	ApolloniusGraphTraits_2 (ApolloniusGraphTraits_2 other)
	Copy constructor.
ApolloniusGraphTraits_2	operator= (ApolloniusGraphTraits_2 other)
	Assignment operator.

Access to predicate objects
Compare_x_2	compare_x_2_object ()
Compare_y_2	compare_y_2_object ()
Compare_weight_2	compare_weight_2_object ()
Orientation_2	orientation_2_object ()
Is_hidden_2	is_hidden_2_object ()
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 ()
Is_degenerate_edge_2	is_degenerate_edge_2_object ()

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 ()

Member Typedef Documentation

Assign_2

typedef unspecified_type ApolloniusGraphTraits_2::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.

Returns true, if the assignment was possible.

Compare_weight_2

typedef unspecified_type ApolloniusGraphTraits_2::Compare_weight_2

A predicate object type.

Must provide Comparison_result operator()(Site_2 s1, Site_2 s2), which compares the weights of s1 and s2.

Compare_x_2

typedef unspecified_type ApolloniusGraphTraits_2::Compare_x_2

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.

Compare_y_2

typedef unspecified_type ApolloniusGraphTraits_2::Compare_y_2

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.

Construct_Apollonius_site_2

typedef unspecified_type ApolloniusGraphTraits_2::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).

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.

Construct_Apollonius_vertex_2

typedef unspecified_type ApolloniusGraphTraits_2::Construct_Apollonius_vertex_2

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.

Finite_edge_interior_conflict_2

typedef unspecified_type ApolloniusGraphTraits_2::Finite_edge_interior_conflict_2

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.

Precondition

the Apollonius vertices of 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.

Precondition

the Apollonius vertex of 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.

Infinite_edge_interior_conflict_2

typedef unspecified_type ApolloniusGraphTraits_2::Infinite_edge_interior_conflict_2

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.

Is_degenerate_edge_2

typedef unspecified_type ApolloniusGraphTraits_2::Is_degenerate_edge_2

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.

Precondition

the Apollonius vertices of s1, s2, s3, and s1, s4, s2 must exist.

Is_hidden_2

typedef unspecified_type ApolloniusGraphTraits_2::Is_hidden_2

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.

Line_2

typedef unspecified_type ApolloniusGraphTraits_2::Line_2

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.

Orientation_2

typedef unspecified_type ApolloniusGraphTraits_2::Orientation_2

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.

Precondition

the Apollonius vertex of s1, s2 and s3 must exist.

Oriented_side_of_bisector_2

typedef unspecified_type ApolloniusGraphTraits_2::Oriented_side_of_bisector_2

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.

Ray_2

typedef unspecified_type ApolloniusGraphTraits_2::Ray_2

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.

Segment_2

typedef unspecified_type ApolloniusGraphTraits_2::Segment_2

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.

Site_2

typedef unspecified_type ApolloniusGraphTraits_2::Site_2

A type for an Apollonius site.

Must be a model of the concept ApolloniusSite_2.

Vertex_conflict_2

typedef unspecified_type ApolloniusGraphTraits_2::Vertex_conflict_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.

Precondition

the dual Apollonius site of 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).