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

CGAL::AABB_traits<GeomTraits,Primitive> (deprecated, use CGAL::AABB_traits_3<GeomTraits,Primitive>)
CGAL::AABB_traits_2<GeomTraits,Primitive>
CGAL::AABB_traits_3<GeomTraits,Primitive>
CGAL::AABB_tree<AT>

Primitives

CGAL::AABB_triangle_primitive_2<GeomTraits, Iterator, CacheDatum>
CGAL::AABB_indexed_triangle_primitive_2<GeomTraits, IndexIterator, PointRange, CacheDatum, PointMap>
CGAL::AABB_segment_primitive_2<GeomTraits, Iterator, CacheDatum>
CGAL::AABB_polyline_segment_primitive_2<GeomTraits, Iterator, PointRange, CacheDatum, PointMap>
CGAL::AABB_triangle_primitive<GeomTraits, Iterator, CacheDatum> (deprecated, use CGAL::AABB_triangle_primitive_3<GeomTraits, Iterator, CacheDatum>)
CGAL::AABB_triangle_primitive_3<GeomTraits, Iterator, CacheDatum>
CGAL::AABB_segment_primitive<GeomTraits, Iterator, CacheDatum> (deprecated, use CGAL::AABB_segment_primitive_3<GeomTraits, Iterator, CacheDatum>)
CGAL::AABB_segment_primitive_3<GeomTraits, Iterator, CacheDatum>
CGAL::AABB_primitive<Id,ObjectPropertyMap,PointPropertyMap,ExternalPropertyMaps,CacheDatum>
CGAL::AABB_halfedge_graph_segment_primitive<HalfedgeGraph,Vpm,OneHalfedgeGraphPerTree,CacheDatum>
CGAL::AABB_face_graph_triangle_primitive<FaceGraph,Vpm,OneFaceGraphPerTree,CacheDatum>

Functions

CGAL::AABB_trees::do_intersect()
CGAL::AABB_trees::all_pairs_of_intersecting_primitives()

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_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 whether two AABB trees contain intersecting primitives.
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 intersecting primitive pairs between 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 self-intersecting primitive pairs in a single AABB tree.

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

Bug: This is not documented for now in the AABBTraits 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

Bug: This is not documented for now in the AABBTraits 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 self-intersecting primitive pairs in a single AABB tree.

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 intersecting primitive pairs between two AABB trees.

Traverses both trees and outputs all pairs of primitives that intersect. 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

AABBTree1	Type of the first AABB tree.
AABBTree2	Type of the second AABB tree.
OutputIterator	Output iterator storing pairs of primitive IDs.
NamedParameters1	a sequence of Named Parameters
NamedParameters2	a sequence of Named Parameters

Optional Named Parameters

a tag indicating if the task should be done using one or several threads. Type: Either CGAL::Sequential_tag, or CGAL::Parallel_tag, or CGAL::Parallel_if_available_tag Default: CGAL::Sequential_tag Extra: np1 only
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: An 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 whether two AABB trees contain intersecting primitives.

Optional Named Parameters

a tag indicating if the task should be done using one or several threads. Type: Either CGAL::Sequential_tag, or CGAL::Parallel_tag, or CGAL::Parallel_if_available_tag Default: CGAL::Sequential_tag Extra: np1 only
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: An identity transformation

Returns: true if at least one primitive of tree1 intersects a primitive of tree2, and false otherwise.

Examples: AABB_tree/AABB_intersection_example.cpp.

Classified Reference Pages

Concepts

Classes

Primitives

Functions

Topics

Classes

Typedefs

Functions

Types

Types

Typedef Documentation

◆ Iso_cuboid_3

◆ Iso_rectangle_2

Function Documentation

◆ all_pairs_of_intersecting_primitives() [1/2]

◆ all_pairs_of_intersecting_primitives() [2/2]

◆ do_intersect()