CGAL::Kinetic_space_partition_3< GeomTraits, IntersectionTraits > Class Template Reference

#include <CGAL/Kinetic_space_partition_3.h>

Definition

template<typename GeomTraits, typename IntersectionTraits = CGAL::Exact_predicates_exact_constructions_kernel>
class CGAL::Kinetic_space_partition_3< GeomTraits, IntersectionTraits >

creates the kinetic partition of the bounding box of the polygons given as input data.

The kinetic partition can either be initialized by using the default constructor Kinetic_space_partition_3(), insert() to provide input data and initialize() to prepare the partition or by using the constructor with input parameters.

Template Parameters

GeomTraits	must be a model of KineticSpacePartitionTraits_3.
IntersectionTraits	must be a model of Kernel using exact computations. Defaults to CGAL::Exact_predicates_exact_constructions_kernel.

Examples

Kinetic_space_partition/kinetic_partition.cpp.

Classes
class	Linear_cell_complex_min_items
	this class provides a minimal model of KineticLCCItems. More...

Public Types
enum	Face_support : int {   ZMIN = -1 , YMIN = -2 , XMAX = -3 , YMAX = -4 ,   XMIN = -5 , ZMAX = -6 , OCTREE_FACE = -7 }
	identifies the support of a face in the exported linear cell complex, which is either an input polygon, identified by a non-negative number, a side of the bounding box in the rotated coordinate system or a face of the octree used to partition the scene.
using	Kernel = GeomTraits
using	Intersection_kernel = IntersectionTraits
using	Point_3 = typename Kernel::Point_3
using	Index = std::pair< std::size_t, std::size_t >

Initialization
template<typename NamedParameters = parameters::Default_named_parameters>
	Kinetic_space_partition_3 (const NamedParameters &np=CGAL::parameters::default_values())
	constructs an empty kinetic space partition object.
template<typename PointRange , typename PolygonRange , typename NamedParameters = parameters::Default_named_parameters>
	Kinetic_space_partition_3 (const PointRange &points, const PolygonRange &polygons, const NamedParameters &np=CGAL::parameters::default_values())
	constructs a kinetic space partition object and initializes it.
template<typename PointRange , typename PolygonRange , typename NamedParameters = parameters::Default_named_parameters>
void	insert (const PointRange &points, const PolygonRange &polygons, const NamedParameters &np=CGAL::parameters::default_values())
	inserts non-coplanar polygons, requires initialize() afterwards to have effect.
template<typename NamedParameters = parameters::Default_named_parameters>
void	initialize (const NamedParameters &np=CGAL::parameters::default_values())
	initializes the kinetic partition of the bounding box.
void	partition (std::size_t k)
	propagates the kinetic polygons in the initialized partition.

Access
std::size_t	number_of_volumes () const
	returns the number of volumes created by the kinetic partition.
const std::vector< typename Intersection_kernel::Plane_3 > &	input_planes () const
	provides the support planes of the partition derived from the input polygons
template<class LCC >
void	get_linear_cell_complex (LCC &lcc) const
	exports the kinetic partition into a Linear_cell_complex_for_combinatorial_map<3, 3> using a model of KineticLCCItems as items, e.g., Kinetic_space_partition_3::Linear_cell_complex_min_items.

Constructor & Destructor Documentation

Kinetic_space_partition_3() [1/2]

template<typename GeomTraits , typename IntersectionTraits = CGAL::Exact_predicates_exact_constructions_kernel>

template<typename NamedParameters = parameters::Default_named_parameters>

CGAL::Kinetic_space_partition_3< GeomTraits, IntersectionTraits >::Kinetic_space_partition_3

(

const NamedParameters &

np = CGAL::parameters::default_values()

)

constructs an empty kinetic space partition object.

Use insert() afterwards to insert polygons into the partition and initialize() to initialize the partition.

Template Parameters

NamedParameters

a sequence of Named Parameters

Parameters

np	a sequence of Named Parameters among the ones listed below

Optional Named Parameters

verbose Write timing and internal information to std::cout. Type: bool Default: false
debug Export of intermediate results. Type: bool Default: false

Kinetic_space_partition_3() [2/2]

template<typename GeomTraits , typename IntersectionTraits = CGAL::Exact_predicates_exact_constructions_kernel>

template<typename PointRange , typename PolygonRange , typename NamedParameters = parameters::Default_named_parameters>

CGAL::Kinetic_space_partition_3< GeomTraits, IntersectionTraits >::Kinetic_space_partition_3	(	const PointRange &	points,
		const PolygonRange &	polygons,
		const NamedParameters &	np = CGAL::parameters::default_values()
	)

constructs a kinetic space partition object and initializes it.

Template Parameters

PointRange	must be a model of ConstRange whose iterator type is RandomAccessIterator and whose value type is Point_3.
PolygonRange	contains index ranges to form polygons by providing indices into PointRange
NamedParameters	a sequence of Named Parameters

Parameters

points	an instance of PointRange with 3D points and corresponding 3D normal vectors
polygons	a range of non-coplanar polygons defined by a range of indices into points
np	a sequence of Named Parameters among the ones listed below

Optional Named Parameters

point_map a property map associating points to the elements of the input range PointRange points. Type: a model of ReadablePropertyMap whose key type is the value type of the iterator of PointRange and whose value type is GeomTraits::Point_3 Default: CGAL::Identity_property_map<GeomTraits::Point_3>
debug Export of intermediate results. Type: bool Default: false
verbose Write timing and internal information to std::cout. Type: bool Default: false
reorient_bbox Use the oriented bounding box instead of the axis-aligned bounding box. While the z direction is maintained, the x axis is aligned with the largest variation in the horizontal plane. Type: bool Default: false
bbox_dilation_ratio Factor for extension of the bounding box of the input data to be used for the partition. Type: FT Default: 1.1
max_octree_depth The maximal depth of the octree for subdividing the kinetic partition before initialization. Type: std::size_t Default: 3
max_octree_node_size A node in the octree is only split if the contained number of primitives is larger and the maximal depth is not yet reached. Type: std::size_t Default: 40

Precondition

! points.empty() and ! polygons.empty()

Member Function Documentation

get_linear_cell_complex()

template<typename GeomTraits , typename IntersectionTraits = CGAL::Exact_predicates_exact_constructions_kernel>

template<class LCC >

void CGAL::Kinetic_space_partition_3< GeomTraits, IntersectionTraits >::get_linear_cell_complex

(

LCC &

lcc

)

const

exports the kinetic partition into a Linear_cell_complex_for_combinatorial_map<3, 3> using a model of KineticLCCItems as items, e.g., Kinetic_space_partition_3::Linear_cell_complex_min_items.

Volume and face attributes defined in the model KineticLCCItems are filled. The volume index is in the range [0, number of volumes -1]

Template Parameters

LCC	must be a model of Linear_cell_complex_for_combinatorial_map<3, 3> using a model of KineticLCCItems.

Parameters

lcc	instance of LCC to be filled with the kinetic partition. Any data contained in lcc will be cleared before.

Precondition

created partition

initialize()

template<typename GeomTraits , typename IntersectionTraits = CGAL::Exact_predicates_exact_constructions_kernel>

template<typename NamedParameters = parameters::Default_named_parameters>

void CGAL::Kinetic_space_partition_3< GeomTraits, IntersectionTraits >::initialize

(

const NamedParameters &

np = CGAL::parameters::default_values()

)

initializes the kinetic partition of the bounding box.

Template Parameters

NamedParameters

a sequence of Named Parameters

Parameters

np	a sequence of Named Parameters among the ones listed below

Optional Named Parameters

reorient_bbox Use the oriented bounding box instead of the axis-aligned bounding box. While the z direction is maintained, the x axis is aligned with the largest variation in the horizontal plane. Type: bool Default: false
bbox_dilation_ratio Factor for extension of the bounding box of the input data to be used for the partition. Type: FT Default: 1.1
max_octree_depth The maximal depth of the octree for subdividing the kinetic partition before initialization. Type: std::size_t Default: 3
max_octree_node_size A node in the octree is only split if the contained number of primitives is larger and the maximal depth is not yet reached. Type: std::size_t Default: 40

Precondition

input data has been provided via insert().

input_planes()

template<typename GeomTraits , typename IntersectionTraits = CGAL::Exact_predicates_exact_constructions_kernel>

const std::vector< typename Intersection_kernel::Plane_3 > & CGAL::Kinetic_space_partition_3< GeomTraits, IntersectionTraits >::input_planes

(

)

const

provides the support planes of the partition derived from the input polygons

Returns

vector of planes.

Precondition

inserted polygons

insert()

template<typename GeomTraits , typename IntersectionTraits = CGAL::Exact_predicates_exact_constructions_kernel>

template<typename PointRange , typename PolygonRange , typename NamedParameters = parameters::Default_named_parameters>

void CGAL::Kinetic_space_partition_3< GeomTraits, IntersectionTraits >::insert	(	const PointRange &	points,
		const PolygonRange &	polygons,
		const NamedParameters &	np = CGAL::parameters::default_values()
	)

inserts non-coplanar polygons, requires initialize() afterwards to have effect.

Template Parameters

PointRange	must be a model of ConstRange whose iterator type is RandomAccessIterator and whose value type is GeomTraits::Point_3.
PolygonRange	contains index ranges to form polygons by providing indices into PointRange
NamedParameters	a sequence of Named Parameters

Parameters

points	an instance of PointRange with 3D points
polygons	a range of non-coplanar polygons defined by a range of indices into points
np	a sequence of Named Parameters among the ones listed below

Optional Named Parameters

point_map a property map associating points to the elements of the points Type: a model of ReadablePropertyMap whose key type is the value type of the iterator of PointRange and whose value type is GeomTraits::Point_3 Default: CGAL::Identity_property_map<GeomTraits::Point_3>

number_of_volumes()

template<typename GeomTraits , typename IntersectionTraits = CGAL::Exact_predicates_exact_constructions_kernel>

std::size_t CGAL::Kinetic_space_partition_3< GeomTraits, IntersectionTraits >::number_of_volumes

(

)

const

returns the number of volumes created by the kinetic partition.

Precondition

created partition

partition()

template<typename GeomTraits , typename IntersectionTraits = CGAL::Exact_predicates_exact_constructions_kernel>

void CGAL::Kinetic_space_partition_3< GeomTraits, IntersectionTraits >::partition

(

std::size_t

k

)

propagates the kinetic polygons in the initialized partition.

Parameters

k	maximum number of allowed intersections for each input polygon before its expansion stops.

Precondition

initialized partition and k != 0