CGAL 6.1 - Fast Intersection and Distance Computation (AABB Tree)

Loading...
Searching...
No Matches
List of all members
AABBTraits Concept Reference
Reference Manual » Concepts

## Definition

The concept `AABBTraits` provides the geometric primitive types and methods for the class `CGAL::AABB_tree<AABBTraits>`.

Has models
  `CGAL::AABB_traits_2<AABBGeomTraits_2,AABBPrimitive>`
  `CGAL::AABB_traits_3<AABBGeomTraits_3,AABBPrimitive>`

Refines
  `SearchTraits`

See also
  `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 sub-ranges 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 `Query` for which the class `CGAL::AABB_tree<AABBTraits>` may receive an intersection detection or computation query.
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 `Query` for which the class `CGAL::AABB_tree<AABBTraits>` may receive a distance query.
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 `Primitive` is a model of the concept `AABBPrimitiveWithSharedData`, the following functions are part of the concept:
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`.

## Member Typedef Documentation

## ◆ Closest_point

typedef unspecified_type AABBTraits::Closest_point

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.

## ◆ Compare_distance

typedef unspecified_type AABBTraits::Compare_distance

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` is
- `bool operator()(const Query & query, const Primitive & primitive, const Point & closest);` which returns `true` iff `primitive` is closer to the `query` than `closest` is

## ◆ Compute_bbox

typedef unspecified_type AABBTraits::Compute_bbox

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.

## ◆ Do_intersect

typedef unspecified_type AABBTraits::Do_intersect

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 box
- `bool operator()(const Query & q, const Primitive & primitive);` which returns `true` iff the query intersects the primitive

## ◆ Equal

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

## ◆ Intersection

typedef unspecified_type AABBTraits::Intersection

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

## ◆ Intersection_and_primitive_id

template<typename Query >

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

## ◆ Object_and_primitive_id

typedef std::pair<Object, Primitive::Id> AABBTraits::Object_and_primitive_id

Deprecated:
  This requirement is deprecated and is no longer needed.

## ◆ Primitive

typedef unspecified_type AABBTraits::Primitive

Type of primitive.

Must be a model of the concepts `AABBPrimitive` or `AABBPrimitiveWithSharedData`.

## ◆ Split_primitives

typedef unspecified_type AABBTraits::Split_primitives

A functor object to split a range of primitives into two sub-ranges 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.

## ◆ Squared_distance

typedef unspecified_type AABBTraits::Squared_distance

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

## Member Function Documentation

## ◆ set_shared_data()

template<class ... T>

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.