CGAL 6.3-I-133 - Fast Intersection and Distance Computation (AABB Tree)
Loading...
Searching...
No Matches
Reference Manual

Pierre Alliez, Stéphane Tayeb, and Camille Wormser
The AABB (axis-aligned bounding box) tree component offers a static data structure and algorithms to perform efficient intersection and distance queries on sets of finite 2D and 3D geometric objects.
Introduced in: CGAL 3.5
BibTeX: cgal:atw-aabb-26b
License: GPL
Windows Demo: AABB Tree

Classified Reference Pages

Concepts

Classes

Primitives

Functions

Topics

 Concepts

Classes

class  CGAL::AABB_face_graph_triangle_primitive< FaceGraph, VertexPointPMap, OneFaceGraphPerTree, CacheDatum >
 Primitive type for a facet of a polyhedral surface. More...
class  CGAL::AABB_halfedge_graph_segment_primitive< HalfedgeGraph, VertexPointPMap, OneHalfedgeGraphPerTree, CacheDatum >
 Primitive type for an edge of a polyhedral surface. More...
class  CGAL::AABB_indexed_triangle_primitive_2< GeomTraits, IndexIterator, PointRange, CacheDatum, PointMap >
 Primitive type that uses as identifier an iterator with a range of three indices as value_type. More...
class  CGAL::AABB_indexed_triangle_primitive_3< GeomTraits, PointRange, FaceRange, CacheDatum, PointMap >
 Primitive type that uses as an identifier an index into a range of triplets of indices as its value_type. More...
class  CGAL::AABB_polyline_segment_primitive_2< GeomTraits, Iterator, PointRange, CacheDatum, PointMap >
 Primitive type that uses as identifier an iterator with a 2D point as value_type. More...
struct  CGAL::AABB_primitive< Id, ObjectPropertyMap, PointPropertyMap, ExternalPropertyMaps, CacheDatum >
 Generic primitive type. More...
class  CGAL::AABB_segment_primitive_2< GeomTraits, Iterator, CacheDatum >
 Primitive type that uses as identifier an iterator with a 2D segment as value_type. More...
class  CGAL::AABB_segment_primitive_3< GeomTraits, Iterator, CacheDatum >
 Primitive type that uses as identifier an iterator with a 3D segment as value_type. More...
class  CGAL::AABB_tree< AABBTraits >
 Static data structure for efficient intersection and distance computations in 2D and 3D. More...
class  CGAL::AABB_traits_2< GeomTraits, AABBPrimitive, BboxMap >
 This traits class handles any type of 2D geometric primitives provided that the proper intersection tests and constructions are implemented. More...
struct  CGAL::AABB_traits_2< GeomTraits, AABBPrimitive, BboxMap >::Intersection_and_primitive_id< Query >
 Intersection_and_primitive_id<Query>::Type::first_type is found according to the result type of GeomTraits::Intersect_2::operator(). More...
class  CGAL::AABB_traits_2< GeomTraits, AABBPrimitive, BboxMap >::Do_intersect
 Function object using GeomTraits::Do_intersect. More...
class  CGAL::AABB_traits_3< GeomTraits, AABBPrimitive, BboxMap >
 This traits class handles any type of 3D geometric primitives provided that the proper intersection tests and constructions are implemented. More...
struct  CGAL::AABB_traits_3< GeomTraits, AABBPrimitive, BboxMap >::Intersection_and_primitive_id< Query >
 Intersection_and_primitive_id<Query>::Type::first_type is found according to the result type of GeomTraits::Intersect_3::operator(). More...
class  CGAL::AABB_traits_3< GeomTraits, AABBPrimitive, BboxMap >::Do_intersect
 Function object using GeomTraits::Do_intersect. More...
class  CGAL::AABB_triangle_primitive_2< GeomTraits, Iterator, CacheDatum >
 Primitive type that uses as identifier an iterator with a 2D triangle as value_type. More...
class  CGAL::AABB_triangle_primitive_3< GeomTraits, Iterator, CacheDatum >
 Primitive type that uses as identifier an iterator with a 3D triangle as value_type. More...

Typedefs

template<class GeomTraits, class Iterator, class CacheDatum = Tag_false>
using CGAL::AABB_segment_primitive = AABB_segment_primitive_3<GeomTraits, Iterator, CacheDatum>
 template alias for backward compatibility
template<typename GeomTraits, typename AABBPrimitive, typename BboxMap = Default>
using CGAL::AABB_traits = AABB_traits_3<GeomTraits, AABBPrimitive, BboxMap>
 template alias for backward compatibility
template<class GeomTraits, class Iterator, class CacheDatum = Tag_false>
using CGAL::AABB_triangle_primitive = AABB_triangle_primitive_3<GeomTraits, Iterator, CacheDatum>
 template alias for backward compatibility

Functions

 CGAL::AABB_traits_2< GeomTraits, AABBPrimitive, BboxMap >::AABB_traits_2 ()
 Default constructor.
 CGAL::AABB_traits_3< GeomTraits, AABBPrimitive, BboxMap >::AABB_traits_3 ()
 Default constructor.
template<typename AABBTree1, typename AABBTree2, typename NamedParameters1 = parameters::Default_named_parameters, typename NamedParameters2 = parameters::Default_named_parameters>
bool CGAL::AABB_trees::do_intersect (const AABBTree1 &tree1, const AABBTree2 &tree2, const NamedParameters1 &np1=parameters::default_values(), const NamedParameters2 &np2=parameters::default_values())
 tests if at least two primitives each from an AABB tree intersect.
template<typename AABBTree1, typename AABBTree2, typename OutputIterator, typename NamedParameters1 = parameters::Default_named_parameters, typename NamedParameters2 = parameters::Default_named_parameters>
void CGAL::AABB_trees::all_pairs_of_intersecting_primitives (const AABBTree1 &tree1, const AABBTree2 &tree2, OutputIterator out, const NamedParameters1 &np1=parameters::default_values(), const NamedParameters2 &np2=parameters::default_values())
 computes all pairs of intersecting primitives from two AABB trees.
template<typename Concurrency_tag = Sequential_tag, typename AABBTree, typename OutputIterator>
void CGAL::AABB_trees::all_pairs_of_intersecting_primitives (const AABBTree &tree, OutputIterator out)
 computes all pairs of primitives from a single AABB tree that are intersecting.

Types

typedef GeomTraits::Point_2 CGAL::AABB_traits_2< GeomTraits, AABBPrimitive, BboxMap >::Point
 point type
typedef GeomTraits::Iso_rectangle_2 CGAL::AABB_traits_2< GeomTraits, AABBPrimitive, BboxMap >::Iso_rectangle_2
 additional types for the search tree, required by the RangeSearchTraits concept
typedef CGAL::Bbox_2 CGAL::AABB_traits_2< GeomTraits, AABBPrimitive, BboxMap >::Bounding_box
 Bounding box type.

Types

typedef GeomTraits::Point_3 CGAL::AABB_traits_3< GeomTraits, AABBPrimitive, BboxMap >::Point
 Point type.
typedef GeomTraits::Point_3 CGAL::AABB_traits_3< GeomTraits, AABBPrimitive, BboxMap >::Point_3
 Deprecated point type.
typedef GeomTraits::Iso_cuboid_3 CGAL::AABB_traits_3< GeomTraits, AABBPrimitive, BboxMap >::Iso_cuboid_3
 additional types for the search tree, required by the RangeSearchTraits concept
typedef CGAL::Bbox_3 CGAL::AABB_traits_3< GeomTraits, AABBPrimitive, BboxMap >::Bounding_box
 Bounding box type.

Typedef Documentation

◆ Iso_cuboid_3

template<typename GeomTraits, typename AABBPrimitive, typename BboxMap = Default>
typedef GeomTraits::Iso_cuboid_3 CGAL::AABB_traits_3< GeomTraits, AABBPrimitive, BboxMap >::Iso_cuboid_3

additional types for the search tree, required by the RangeSearchTraits concept

◆ Iso_rectangle_2

template<typename GeomTraits, typename AABBPrimitive, typename BboxMap = Default>
typedef GeomTraits::Iso_rectangle_2 CGAL::AABB_traits_2< GeomTraits, AABBPrimitive, BboxMap >::Iso_rectangle_2

additional types for the search tree, required by the RangeSearchTraits concept

Function Documentation

◆ all_pairs_of_intersecting_primitives() [1/2]

template<typename Concurrency_tag = Sequential_tag, typename AABBTree, typename OutputIterator>
void CGAL::AABB_trees::all_pairs_of_intersecting_primitives ( const AABBTree & tree,
OutputIterator out )

#include <CGAL/AABB_trees/intersection.h>

computes all pairs of primitives from a single AABB tree that are intersecting.

Note
Two primitives do intersect if their datum do intersect according to the traits of the tree. Thus, with all documented traits in CGAL, two triangles sharing a vertex are considered to intersect, and similarly for other primitives types and types of intersection.

Intersections of a primitive with itself are not reported, and each intersecting pair of distinct primitives is reported only once.

◆ all_pairs_of_intersecting_primitives() [2/2]

template<typename AABBTree1, typename AABBTree2, typename OutputIterator, typename NamedParameters1 = parameters::Default_named_parameters, typename NamedParameters2 = parameters::Default_named_parameters>
void CGAL::AABB_trees::all_pairs_of_intersecting_primitives ( const AABBTree1 & tree1,
const AABBTree2 & tree2,
OutputIterator out,
const NamedParameters1 & np1 = parameters::default_values(),
const NamedParameters2 & np2 = parameters::default_values() )

#include <CGAL/AABB_trees/intersection.h>

computes all pairs of intersecting primitives from two AABB trees.

Both trees are traversed and all pairs of primitives that intersect are collected. Each output element is a pair (id1, id2) where:

  • id1 is the ID of a primitive from tree1
  • id2 is the ID of a primitive from tree2
Template Parameters
AABBTree1Type of the first AABB tree.
AABBTree2Type of the second AABB tree.
OutputIteratorOutput iterator storing std::pair<AABBTree1::Primitive::Id, AABBTree2::Primitive::Id>.
NamedParameters1a sequence of Named Parameters
NamedParameters2a sequence of Named Parameters
Optional Named Parameters
  • An affine transformation apply to tree1 (tree2)
  • Type: CGAL::Aff_transformation_3<Kernel> where Kernel is the kernel associated with AABBTree1::AABB_traits::Point (AABBTree2::AABB_traits::Point)
  • Default: The identity transformation
See also
do_intersect()
Examples
AABB_tree/AABB_intersection_example.cpp.

◆ do_intersect()

template<typename AABBTree1, typename AABBTree2, typename NamedParameters1 = parameters::Default_named_parameters, typename NamedParameters2 = parameters::Default_named_parameters>
bool CGAL::AABB_trees::do_intersect ( const AABBTree1 & tree1,
const AABBTree2 & tree2,
const NamedParameters1 & np1 = parameters::default_values(),
const NamedParameters2 & np2 = parameters::default_values() )

#include <CGAL/AABB_trees/intersection.h>

tests if at least two primitives each from an AABB tree intersect.

Optional Named Parameters
  • If true, the inverse of the transformations are used to accelerate the queries.
  • Type: CGAL::Tag_true or CGAL::Tag_false
  • Default: CGAL::Tag_false
  • Extra: The result may be less accurate than using the original transformations.
  • Extra: np1 only
Warning
The Do_intersect functors of the AABBTraits of both AABB trees should accept the Datum type of the other tree as the Query type.
Returns
true if at least one primitive of tree1 intersects a primitive of tree2, and false otherwise.
Examples
AABB_tree/AABB_intersection_example.cpp.