CGAL 6.0  Fast Intersection and Distance Computation (AABB Tree)

The concept AABBTraits
provides the geometric primitive types and methods for the class CGAL::AABB_tree<AABBTraits>
.
CGAL::AABB_traits_2<AABBGeomTraits_2,AABBPrimitive>
CGAL::AABB_traits_3<AABBGeomTraits_3,AABBPrimitive>
SearchTraits
CGAL::AABB_tree<AABBTraits>
AABBPrimitive
Types  
typedef unspecified_type  FT 
Value type of the Squared_distance functor.  
typedef unspecified_type  Point 
Type of a point.  
typedef unspecified_type  Primitive 
Type of primitive.  
typedef unspecified_type  Bounding_box 
Bounding box type.  
typedef std::pair< Point, Primitive::Id >  Point_and_primitive_id 
Point and Primitive Id type.  
typedef std::pair< Object, Primitive::Id >  Object_and_primitive_id 
template<typename Query >  
using  Intersection_and_primitive_id = unspecified_type 
A nested class template providing as a pair the intersection result of a Query object and a Primitive::Datum , together with the Primitive::Id of the primitive intersected.  
Splitting  
During the construction of the AABB tree, the primitives are split according to some comparison functions related to the longest axis:  
typedef unspecified_type  Split_primitives 
A functor object to split a range of primitives into two subranges along the longest axis.  
typedef unspecified_type  Compute_bbox 
A functor object to compute the bounding box of a set of primitives.  
Intersections  
The following predicates are required for each type  
typedef unspecified_type  Do_intersect 
A functor object to compute intersection predicates between the query and the nodes of the tree.  
typedef unspecified_type  Intersection 
A functor object to compute the intersection of a query and a primitive.  
Distance Queries  
The following predicates are required for each type  
typedef unspecified_type  Compare_distance 
A functor object to compute distance comparisons between the query and the nodes of the tree.  
typedef unspecified_type  Closest_point 
A functor object to compute the closest point from the query on a primitive.  
typedef unspecified_type  Squared_distance 
A functor object to compute the squared distance between two points.  
typedef unspecified_type  Equal 
A functor object to compare two points.  
Operations  
Split_primitives  split_primitives_object () 
returns the primitive splitting functor.  
Compute_bbox  compute_bbox_object () 
returns the bounding box constructor.  
Do_intersect  do_intersect_object () 
returns the intersection detection functor.  
Intersection  intersection_object () 
returns the intersection constructor.  
Compare_distance  compare_distance_object () 
returns the distance comparison functor.  
Closest_point  closest_point_object () 
returns the closest point constructor.  
Squared_distance  squared_distance_object () 
returns the squared distance functor.  
Equal  equal_object () 
returns the equal functor.  
Primitive with Shared Data  
In addition, if  
template<class ... T>  
void  set_shared_data (T ... t) 
the signature of that function must be the same as the static function Primitive::construct_shared_data .  
A functor object to compute the closest point from the query on a primitive.
Provides the operator: Point operator()(const Query& query, const Primitive& primitive, const Point & closest);
which returns the closest point to query
, among closest
and all points of the primitive.
A functor object to compute distance comparisons between the query and the nodes of the tree.
Provides the operators:
bool operator()(const Query & query, const Bounding_box& box, const Point & closest);
which returns true
iff the bounding box is closer to query
than closest
isbool operator()(const Query & query, const Primitive & primitive, const Point & closest);
which returns true
iff primitive
is closer to the query
than closest
is A functor object to compute the bounding box of a set of primitives.
Provides the operator: Bounding_box operator()(Input_iterator begin, Input_iterator beyond);
Iterator type InputIterator
must have Primitive
as value type.
A functor object to compute intersection predicates between the query and the nodes of the tree.
Provides the operators:
bool operator()(const Query & q, const Bounding_box & box);
which returns true
iff the query intersects the bounding boxbool operator()(const Query & q, const Primitive & primitive);
which returns true
iff the query intersects the primitive typedef unspecified_type AABBTraits::Equal 
A functor object to compare two points.
Provides the operator: bool operator()(const Point& p, const Point& q);}
which returns true
if p
is equal to q
.
A functor object to compute the intersection of a query and a primitive.
Provides the operator: std::optional<Intersection_and_primitive_id<Query>::Type > operator()(const Query & q, const Primitive& primitive);
which returns the intersection as a pair composed of an object and a primitive id, iff the query intersects the primitive.
Note on Backward Compatibility
Before the release 4.3 of CGAL, the return type of this function used to be std::optional<Object_and_primitive_id>
.
using AABBTraits::Intersection_and_primitive_id = unspecified_type 
A nested class template providing as a pair the intersection result of a Query
object and a Primitive::Datum
, together with the Primitive::Id
of the primitive intersected.
The type of the pair is Intersection_and_primitive_id<Query>::Type
.
typedef std::pair<Object, Primitive::Id> AABBTraits::Object_and_primitive_id 
Type of primitive.
Must be a model of the concepts AABBPrimitive
or AABBPrimitiveWithSharedData
.
A functor object to split a range of primitives into two subranges along the longest axis.
Provides the operator: void operator()(InputIterator first, InputIterator beyond);
Iterator type InputIterator
must be a model of RandomAccessIterator and have Primitive
as value type. The operator is used for determining the primitives assigned to the two children nodes of a given node, assuming that the goal is to split the chosen axis dimension of the bounding box of the node. The primitives assigned to this node are passed as argument to the operator. It should modify the iterator range in such a way that its first half and its second half correspond to the two children nodes.
A functor object to compute the squared distance between two points.
Provides the operator: FT operator()(const Point& query, const Point & p);
which returns the squared distance between p
and q
.
void AABBTraits::set_shared_data  (  T ...  t  ) 
the signature of that function must be the same as the static function Primitive::construct_shared_data
.
The type Primitive
expects that the data constructed by a call to Primitive::construct_shared_data(t...)
is the one given back when accessing the reference point and the datum of a primitive.