\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 5.0 - K Discrete Oriented Polytope Tree (K-DOP Tree)
List of all members
KDOPTraits Class Reference
K Discrete Oriented Polytope Tree (K-DOP Tree) Reference » Concepts

#include <Concepts/KDOPTraits.h>

Definition

The concept KDOPTraits provides the geometric primitive types and methods for the class CGAL::KDOP_tree<KDOPTraits>.

^^

Has Models:
CGAL::KDOP_traits<KDOPGeomTraits,KDOPPrimitive>

Types

typedef unspecified_type Geom_traits
 Type of geometry traits (kernel)
 
typedef unspecified_type FT
 Number type of the geometry kernel.
 
typedef unspecified_type KT
 Type of k-DOP traits.
 
typedef unspecified_type Primitive
 Type of primitives.
 
typedef unspecified_type Point_and_primitive_id
 3D point and primitive id type
 
typedef unspecified_type Point_3
 Type of a 3D point.
 
typedef unspecified_type Sphere_3
 Type of a sphere.
 
typedef unspecified_type Bounding_box
 Type of a bounding box.
 
typedef unspecified_type Kdop
 K-dop type.
 
typedef unspecified_type Array_height
 Type of support heights of a k-DOP.
 

Splitting

During the construction of the KDOP tree, the primitives are splitted in the binary way.

typedef unspecified_type Split_primitives
 A functor object to split a range of primitives. More...
 
typedef unspecified_type Compute_bbox
 A functor object to compute the bounding box of a set of primitives. More...
 

K-dop computation

Different from the implementation of AABB tree, the K-dop computation is after the whole splitting is completed so that the K-dop can be computed recursively in a bottom-top manner, without duplicate computation as in AABB tree where the bounding box is computed after each splitting.

typedef unspecified_type Compute_kdop
 A functor object to compute the kdop (support heights) of a set of primitives. More...
 

Intersections

typedef unspecified_type Do_intersect
 A functor object to compute intersection predicates between the query and the nodes of the tree. More...
 
typedef unspecified_type Intersection
 A functor object to compute the intersection of a query and a primitive. More...
 

Distance queries

typedef unspecified_type Closest_point
 A functor object to compute closest point from the query on a primitive. More...
 
typedef unspecified_type Compare_distance
 A functor object to compare distance between the point and the nodes of the tree. More...
 

Operations

Split_primitives split_primitives_object ()
 Return the primitive splitting functor.
 
Compute_bbox compute_bbox_object ()
 Return the bounding box functor.
 
Compute_kdop compute_kdop_object ()
 Return the support heights constructor.
 
Do_intersect do_intersect_object ()
 Return the intersection detection functor.
 
Intersection intersection_object ()
 Return the intersection constructor.
 
Compare_distance compare_distance_object ()
 Return the distance comparison functor.
 
Closest_point closest_point_object ()
 Return the closest point computation functor.
 

Member Typedef Documentation

typedef unspecified_type KDOPTraits::Closest_point

A functor object to compute closest point from the query on a primitive.

Provides the operator: Point_3 operator()(const Query& query, const Primitive& primitive, const Point_3 & closest); which returns the closest point to query, among closest and all points of the primitive.

typedef unspecified_type KDOPTraits::Compare_distance

A functor object to compare distance between the point and the nodes of the tree.

Provides the operators:

  • bool operator()(const Query & query, const Kdop & kdop, const Array_height & support_heights, const Point & closest); which returns true iff the k-DOP is closer to query than closest is
typedef unspecified_type KDOPTraits::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.

typedef unspecified_type KDOPTraits::Compute_kdop

A functor object to compute the kdop (support heights) of a set of primitives.

Provides the operator: Kdop operator()(Input_iterator begin, Input_iterator beyond); Iterator type InputIterator must have Primitive as value type. The operation contains the union of k-dops of the children of a node in the tree.

typedef unspecified_type KDOPTraits::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 Kdop & kdop, const Array_height & support_heights); which returns true iff the query intersects the kdop
  • bool operator()(const Query & q, const Primitive & primitive); which returns true iff the query intersects the primitive
typedef unspecified_type KDOPTraits::Intersection

A functor object to compute the intersection of a query and a primitive.

Provides the operator: boost::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.

typedef unspecified_type KDOPTraits::Split_primitives

A functor object to split a range of primitives.

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 children nodes of a given node, assuming that the goal is to split at the centroid of the collection of primitives. The primitives assigned to this node are passed as argument to the operator.