Computational geometry. More...

Classes
class	Basis

class	Basis_spline
	Non-uniform rational basis spline (NURBS). More...

class	Bezier_curve

class	Bounds

class	BSP_node_iterator
	Traverse BSP tree nodes using depth-first search. More...

struct	BSP_traits

struct	BSP_traits< T, 2 >

struct	BSP_traits< T, 3 >

class	BSP_tree

class	Closed_basis_spline
	Closed non-uniform rational basis spline (NURBS). More...

struct	Compare_vertex

class	Coons_surface

class	Coordinate_system

class	Cubic_spline

class	Curve_segments

struct	Equal_vertex

class	Face

struct	Inertia_tensor

struct	Inertia_tensor< T, 2 >

struct	Inertia_tensor< T, 3 >

struct	is_figure

struct	is_figure< Line_segment< T, N > >

struct	is_figure< Polygon< T, N > >

struct	is_figure< Polyline< T, N > >

struct	is_figure< Tetrahedron< T, N > >

struct	is_figure< Triangle< T, N > >

class	Line_segment

class	Linear_interpolation

struct	Mass_moments

struct	Mass_moments< T, 2 >

struct	Mass_moments< T, 3 >

class	Plane
	Three- and two-dimensional plane. More...

class	Polygon

class	Polyhedron
	Three-dimensional polyhedron. More...

class	Polyline
	A polygon composed of line segments. More...

class	Quaternion

class	Quaternion_coordinate_system

class	Ray

class	Rectangle

class	Rotation_matrix

class	Ruled_surface

class	Spline_surface

class	Tetrahedron

class	Triangle

Typedefs
using	bstream = ::vtb::base::bstream

template<class T , int N>
using	Vertex = blitz::TinyVector< T, N >

template<class T , int N>
using	Matrix = blitz::TinyMatrix< T, N, N >

template<class T >
using	Array = std::vector< T >

template<int N>
using	Face_array = Array< Face< N > >

template<class T , int N>
using	Vertex_array = Array< Vertex< T, N > >

template<class T , int N>
using	Vertex_matrix = Array< Vertex_array< T, N > >

template<class T , int N>
using	Ray_array = Array< Ray< T, N > >

Enumerations
enum	Plane_position : unsigned char { Same = 0, Front = 1, Back = 2 }

Functions
template<class T , int N>
void	transpose (Basis< T, N > &basis)

template<class T , int N>
Vertex< T, N >	to (const Basis< T, N > &b, const Vertex< T, N > &v)

template<class T , int N>
Basis< T, N >	rotation_matrix_zyx (const Vertex< T, N > &angle)
	Return rotation matrix specified by Euler `angles`. More...

template<class T , int N>
Basis< T, N >	rotation_matrix_xyz (const Vertex< T, N > &angle)

template<class T , int N>
Basis< T, N >	inverse (const Basis< T, N > &basis)

template<class T , int N>
bstream &	operator<< (bstream &out, const Rotation_matrix< T, N > &rhs)

template<class T , int N>
bstream &	operator>> (bstream &in, Rotation_matrix< T, N > &rhs)

template<class T , int N>
Basis< T, N >	inverse (const Rotation_matrix< T, N > &rot)

template<class T , int N, class X >
auto	operator * (const Basis< T, N > &lhs, const X &rhs) -> decltype(product(lhs, rhs))

template<class T , int N>
Vertex< T, N >	to (const Rotation_matrix< T, N > &rot, const Vertex< T, N > &v)

template<class T , int N>
Vertex< T, N >	from (const Rotation_matrix< T, N > &rot, const Vertex< T, N > &v)

template<class T , int N>
Rotation_matrix< T, N >	make_rotation (const Basis< T, N > &basis, const Basis< T, N > &ibasis)

template<class T , int N>
Rotation_matrix< T, N >	make_rotation (const Basis< T, N > &basis)

template<class T , int N>
Rotation_matrix< T, N >	make_rotation_zyx (const Vertex< T, N > &angles)
	Rotation_matrix matrix for Euler `angles` in \(ZYX\) order. More...

template<class T , int N>
Rotation_matrix< T, N >	make_rotation_xyz (const Vertex< T, N > &angles)

template<class T , int N>
bstream &	operator<< (bstream &out, const Coordinate_system< T, N > &rhs)

template<class T , int N>
bstream &	operator>> (bstream &in, Coordinate_system< T, N > &rhs)

template<class T , int N>
Coordinate_system< T, N >	make_coordinate_system (const Basis< T, N > &basis, const Vertex< T, N > &origin)

template<class T , int N>
Coordinate_system< T, N >	make_coordinate_system (const Basis< T, N > &basis, const Basis< T, N > &ibasis, const Vertex< T, N > &origin)

template<class T , int N>
Coordinate_system< T, N >	make_coordinate_system (const Rotation_matrix< T, N > &rot, const Vertex< T, N > &origin)

template<class T , int N>
Vertex< T, N >	to (const Coordinate_system< T, N > &cs, const Vertex< T, N > &v)

template<class T , int N>
Vertex< T, N >	from (const Coordinate_system< T, N > &cs, const Vertex< T, N > &v)

template<class T , int N>
Vertex< T, N >	vector_to (const Rotation_matrix< T, N > &r, const Vertex< T, N > &v)

template<class T , int N>
Vertex< T, N >	vector_to (const Coordinate_system< T, N > &cs, const Vertex< T, N > &v)

template<class T , int N>
Vertex< T, N >	vector_from (const Coordinate_system< T, N > &cs, const Vertex< T, N > &v)

template<class T , int N>
Vertex< T, N >	from (const Basis< T, N > &basis, const Vertex< T, N > &origin, const Vertex< T, N > &v)

template<class T , int N>
BSP_tree< T, N >	set_union (const BSP_tree< T, N > &lhs, const BSP_tree< T, N > &rhs)

template<class T , int N>
BSP_tree< T, N >	set_difference (const BSP_tree< T, N > &lhs, const BSP_tree< T, N > &rhs)

template<class T , int N>
BSP_tree< T, N >	set_intersection (const BSP_tree< T, N > &lhs, const BSP_tree< T, N > &rhs)

template<class V , class T >
V	difference (const V &a, const V &b, T delta)

template<class V >
V	difference (const V &a, const V &b)

template<int N>
bool	operator== (const Face< N > &lhs, const Face< N > &rhs)

template<int N>
bool	operator!= (const Face< N > &lhs, const Face< N > &rhs)

template<int N>
bool	operator< (const Face< N > &lhs, const Face< N > &rhs)

template<int N>
std::ostream &	operator<< (std::ostream &out, const Face< N > &rhs)

template<int N>
std::istream &	operator>> (std::istream &in, Face< N > &rhs)

template<int N>
vtb::core::bstream &	operator<< (vtb::core::bstream &out, const Face< N > &rhs)

template<int N>
vtb::core::bstream &	operator>> (vtb::core::bstream &in, Face< N > &rhs)

template<class T >
void	check_matrix (const char *name, const Matrix< T, 3 > &m, const Matrix< T, 3 > &im)

template<class T , int N>
bool	near (const Line_segment< T, N > &lhs, const Line_segment< T, N > &rhs, T eps)

template<class T , int N>
bool	operator< (const Line_segment< T, N > &lhs, const Line_segment< T, N > &rhs)

template<class T , int N>
bool	operator== (const Line_segment< T, N > &lhs, const Line_segment< T, N > &rhs)

template<class T , int N>
bool	operator!= (const Line_segment< T, N > &lhs, const Line_segment< T, N > &rhs)

template<class T , int N>
Vertex< Plane_position, 2 >	compare (const Plane< T, N > plane, const Line_segment< T, N > &s, T eps)

template<class T , int N>
Vertex< T, N >	intersection_point (const Plane< T, N > &plane, const Line_segment< T, N > &segment)

template<int dim, class T , int N>
Vertex< T, N >	intersection_point (const Line_segment< T, N > &segment, T level)

template<class T , int N>
Vertex< T, N >	centroid (const Line_segment< T, N > &s)

template<class T , int N>
Vertex< T, N >	unit (const Vertex< T, N > &v)

template<class T >
Vertex< T, 3 >	surface_normal (const Vertex< T, 3 > &v0, const Vertex< T, 3 > &v1, const Vertex< T, 3 > &v2)

template<class T >
Vertex< T, 2 >	line_normal (const Vertex< T, 2 > &v0, const Vertex< T, 2 > &v1)
	Rotates line segment by 90 degrees counterclockwise and normalises resulting vector. More...

template<class T >
Vertex< T, 1 >	orientation (const Vertex< T, 2 > &origin, const Vertex< T, 2 > &a, const Vertex< T, 2 > &b)

template<class T >
T	det (const Vertex< T, 2 > &a, const Vertex< T, 2 > &b)

template<class T >
T	det (const Vertex< T, 2 > &origin, const Vertex< T, 2 > &a, const Vertex< T, 2 > &b)

template<class T >
T	det (const Vertex< T, 3 > &a, const Vertex< T, 3 > &b, const Vertex< T, 3 > &c)

template<class T >
bool	clockwise (const Vertex< T, 2 > &origin, const Vertex< T, 2 > &a, const Vertex< T, 2 > &b)

template<class Container , class T >
int	winding_number (const Container &vertices, const Vertex< T, 2 > &origin)

template<class T , int N>
T	cosine (const Vertex< T, N > &a, const Vertex< T, N > &b)

template<class Figure >
Figure::value_type	centroid (const Figure &figure)

template<class Figure >
Figure::value_type	perimeter (const Figure &figure)

template<class Figure >
bool	border_contains (const Figure &figure, const typename Figure::value_type &vertex, const typename Figure::scalar_type eps)

template<class Figure >
bool	interior_contains (const Figure &figure, const typename Figure::value_type &vertex)

template<class Figure >
bool	contains (const Figure &figure, const typename Figure::value_type &vertex, const typename Figure::scalar_type eps)

template<class Figure >
std::enable_if< is_figure< Figure >::value, std::ostream & >::type	operator<< (std::ostream &out, const Figure &figure)

template<class Figure >
auto	bounding_box (const Figure &figure) -> Rectangle< typename Figure::scalar_type, Figure::dimensions >

template<int dimension, int degrees, class T , int N>
Vertex< T, N >	rotate (const Vertex< T, N > &v)

template<class T , int N>
std::ostream &	operator<< (std::ostream &out, const Plane< T, N > &rhs)

template<class T , int N>
Vertex< T, N >	intersection (const Ray< T, N > &ray, const Plane< T, N > &plane)
	Returns intersection point of `ray` and `plane`. Edge cases are ignored. More...

template<class T , int N>
Plane_position	compare (const Plane< T, N > plane, const Vertex< T, N > &point, T eps)

template<class T , int N>
Plane_position	compare (const Plane< T, N > lhs, const Plane< T, N > &rhs, T eps)

constexpr Plane_position	operator\| (Plane_position a, Plane_position b)

const char *	to_string (Plane_position rhs)

std::ostream &	operator<< (std::ostream &out, Plane_position rhs)

template<class T >
Vertex< T, 2 >	centroid (const Polygon< T, 2 > &p)

template<class T , int N>
void	swap (Polyhedron< T, N > &lhs, Polyhedron< T, N > &rhs)

template<class T , int N>
Vertex< T, N >	centroid (const Polyhedron< T, N > &geometry)

template<class T , int N>
T	signed_volume (const Polyhedron< T, N > &geometry)

template<class T , int N>
T	volume (const Polyhedron< T, N > &geometry)

template<class T , int N>
Polyhedron< T, N >	operator+ (const Polyhedron< T, N > &lhs, const Polyhedron< T, N > &rhs)

template<class T , int N>
vtb::core::bstream &	operator<< (vtb::core::bstream &out, const Polyhedron< T, N > &rhs)

template<class T , int N>
vtb::core::bstream &	operator>> (vtb::core::bstream &in, Polyhedron< T, N > &rhs)

template<class T , int N>
T	winding_number (const Polyhedron< T, N > &geometry, const Vertex< T, N > &origin)

template<class T , int N>
Inertia_tensor< T, N >	inertia_tensor (const Polyhedron< T, N > &body)
	Calculate inertia tensor (matrix) of a body as a sum of inertia tensors for tetrahedrons. More...

template<class T , int N>
Mass_moments< T, N >	mass_moments (const Polyline< T, N > &polyline)
	Calculate area, centroid and inertia tensor. More...

template<class T , int N>
Polyhedron< T >	cube (const Vertex< T, N > &a, const Vertex< T, N > &b)

template<class T >
std::ostream &	operator<< (std::ostream &out, const Quaternion< T > &q)

template<class T >
T	real (const Quaternion< T > &q)

template<class T >
Vertex< T, 3 >	imag (const Quaternion< T > &q)

template<class T >
Quaternion< T >	operator * (const Quaternion< T > &a, const Quaternion< T > &b)
	Hamilton product.

template<class T >
Quaternion< T >	*operator =** (Quaternion< T > &a, const Quaternion< T > &b)

template<class T >
Quaternion< T >	operator * (const Quaternion< T > &a, T b)

template<class T >
Quaternion< T >	operator * (T a, const Quaternion< T > &b)

template<class T >
Quaternion< T >	operator/ (const Quaternion< T > &a, T b)

template<class T >
Quaternion< T >	operator+ (Quaternion< T > &a, const Quaternion< T > &b)

template<class T >
Quaternion< T >	operator+= (Quaternion< T > &a, const Quaternion< T > &b)

template<class T >
Quaternion< T >	unit (const Quaternion< T > &q)

template<class T >
T	length (const Quaternion< T > &q)

template<class T >
Vertex< T, 3 >	to_euler_angles (const Quaternion< T > &q)
	Convert quaternion to Euler angles. More...

template<class T >
Quaternion< T >	from_euler_angles (const Vertex< T, 3 > &angles)

template<class T >
Rotation_matrix< T, 3 >	rotation_matrix (const Quaternion< T > &q)

template<class T >
Quaternion< T >	from_vector (const Quaternion< T > &q)

template<class T >
Quaternion< T >	to_vector (const Quaternion< T > &q)

template<class T >
Quaternion< T >	conj (const Quaternion< T > &q)

template<class T >
Vertex< T, 3 >	rotate (const Vertex< T, 3 > &v, const Quaternion< T > &q)

template<class T >
Quaternion_coordinate_system< T >	make_coordinate_system (const Quaternion< T > &q, const Vertex< T, 3 > &origin)

template<class T >
Quaternion_coordinate_system< T >	make_coordinate_system (const Quaternion< T > &q, const Quaternion< T > &q_conj, const Vertex< T, 3 > &origin)

template<class T >
Vertex< T, 3 >	to (const Quaternion_coordinate_system< T > &cs, const Vertex< T, 3 > &v)

template<class T >
Vertex< T, 3 >	from (const Quaternion_coordinate_system< T > &cs, const Vertex< T, 3 > &v)

template<class T >
Vertex< T, 3 >	vector_to (const Quaternion_coordinate_system< T > &cs, const Vertex< T, 3 > &v)

template<class T >
Vertex< T, 3 >	vector_from (const Quaternion_coordinate_system< T > &cs, const Vertex< T, 3 > &v)

template<class T , int N>
Vertex< T, N >	centroid (const Rectangle< T, N > &r)

template<class T , int N>
Vertex< T, N >	area (const Rectangle< T, N > &r)

template<class T , int N>
Vertex< T, N >	centroid (const Tetrahedron< T, N > &t)

template<class T , int N>
T	signed_volume (const Tetrahedron< T, N > &t)

template<class T , int N>
T	volume (const Tetrahedron< T, N > &t)

template<class T >
T	solid_angle (const Tetrahedron< T, 3 > &t)

template<class T >
T	tetrahedron_signed_volume (const Triangle< T, 3 > &tr)
	Signed volume of a tetrahedron with the origin \((0,0,0)\). More...

template<class T >
T	tetrahedron_signed_volume (const Triangle< T, 2 > &tr)

template<class T , int N>
bool	intersect (const Ray< T, N > &ray, const Triangle< T, N > &triangle, T eps)
	Check if `ray` intersects `triangle`. More...

template<class T , int N>
Vertex< Plane_position, 3 >	compare (const Plane< T, N > plane, const Triangle< T, N > &triangle, T eps)

template<class T , int N>
void	intersect (const Plane< T, N > &plane, const Triangle< T, N > &triangle, const Vertex< Plane_position, 3 > &positions, Polygon< T, N > &front, Polygon< T, N > &back)

template<class T , int N>
Vertex< T, N >	centroid (const Triangle< T, N > &t)

template<class T , int N>
T	area (const Triangle< T, N > &t)

template<class T >
Vertex< T, 3 >	surface_normal (const Triangle< T, 3 > &t)

Detailed Description

Computational geometry.

Function Documentation

◆ inertia_tensor()

template<class T , int N>

Inertia_tensor<T,N> vtb::geometry::inertia_tensor ( const Polyhedron< T, N > & body )

Calculate inertia tensor (matrix) of a body as a sum of inertia tensors for tetrahedrons.

Date: 2019-06-06

Author: Ivan Gankevich

Uses formulae from [tonon2004explicit].

◆ intersect()

template<class T , int N>

bool vtb::geometry::intersect	(	const Ray< T, N > &	ray,
		const Triangle< T, N > &	triangle,
		T	eps
	)

inline

Check if ray intersects triangle.

Date: 2018-08-27

Author: Ivan Gankevich

Uses Moller—Trumbore algorithm.

Definition at line 88 of file triangle.hh.

◆ intersection()

template<class T , int N>

Vertex<T,N> vtb::geometry::intersection	(	const Ray< T, N > &	ray,
		const Plane< T, N > &	plane
	)

inline

Returns intersection point of ray and plane. Edge cases are ignored.

Date: 2018-09-24

Author: Ivan Gankevich

Definition at line 174 of file plane.hh.

References vtb::geometry::Plane< T, N >::normal(), and vtb::geometry::Plane< T, N >::origin().

◆ line_normal()

template<class T >

Vertex<T,2> vtb::geometry::line_normal	(	const Vertex< T, 2 > &	v0,
		const Vertex< T, 2 > &	v1
	)

inline

Rotates line segment by 90 degrees counterclockwise and normalises resulting vector.

Date: 2019-04-08

Author: Ivan Gankevich

Definition at line 44 of file geometry/math.hh.

◆ make_rotation_zyx()

template<class T , int N>

Rotation_matrix<T,N> vtb::geometry::make_rotation_zyx ( const Vertex< T, N > & angles )

Rotation_matrix matrix for Euler angles in \(ZYX\) order.

Date: 2019-06-07

Author: Ivan Gankevich

◆ mass_moments()

template<class T , int N>

Mass_moments<T,N> vtb::geometry::mass_moments ( const Polyline< T, N > & polyline )

Calculate area, centroid and inertia tensor.

Date: 2020-02-13

Author: Ivan Gankevich

Uses algorithm adapted from [eberly2002polyhedral].
See also
https://en.wikipedia.org/wiki/Second_moment_of_area

https://en.wikipedia.org/wiki/Centroid#Of_a_polygon

Referenced by vtb::geometry::Polyhedron< T >::move_to_centre_of_mass().

◆ rotation_matrix_zyx()

template<class T , int N>

Basis<T,N> vtb::geometry::rotation_matrix_zyx ( const Vertex< T, N > & angle )

Return rotation matrix specified by Euler angles.

Date: 2018-08-23

Author: Ivan Gankevich

Rotation matrix is computed as the product of rotation matrices for each dimension. For Euler angles \((\phi,\theta,\psi)\) the matrix is written as

\[ \mathcal{T} = \left[ \begin{array}{ccc} \cos\theta \cos\psi & \cos\theta \sin\psi & -\sin\theta \\ \cos\psi \sin\theta \sin\phi-\cos\phi \sin\psi & \cos\phi \cos\psi+\sin\theta \sin\phi \sin\psi & \cos\theta \sin\phi \\ \cos\phi \cos\psi \sin\theta+\sin\phi \sin\psi & \cos\phi \sin\theta \sin\psi -\cos\psi \sin\phi & \cos\theta \cos\phi \\ \end{array} \right] = \left[ \begin{array}{rrr} 1 & 0 & 0 \\ 0 & \cos\phi & \sin\phi \\ 0 & -\sin\phi & \cos\phi \\ \end{array} \right] \times \left[ \begin{array}{rrr} \cos\theta & 0 & -\sin\theta \\ 0 & 1 & 0 \\ \sin\theta & 0 & \cos\theta \\ \end{array} \right] \times \left[ \begin{array}{rrr} \cos\psi & \sin\psi & 0 \\ -\sin\psi & \cos\psi & 0 \\ 0 & 0 & 1 \\ \end{array} \right]. \]

◆ tetrahedron_signed_volume()

template<class T >

T vtb::geometry::tetrahedron_signed_volume ( const Triangle< T, 3 > & tr )

Signed volume of a tetrahedron with the origin \((0,0,0)\).

Date: 2019-04-01

Author: Ivan Gankevich

Definition at line 70 of file triangle.hh.

◆ to_euler_angles()

template<class T >

Vertex<T,3> vtb::geometry::to_euler_angles ( const Quaternion< T > & q )

Convert quaternion to Euler angles.

Date: 2019-06-13

Author: Ivan Gankevich

See also: http://www.euclideanspace.com/maths/geometry/rotations/conversions/quaternionToEuler/

Classes

Typedefs

Enumerations

Functions

Detailed Description

Function Documentation

◆ inertia_tensor()

◆ intersect()

◆ intersection()

◆ line_normal()

◆ make_rotation_zyx()

◆ mass_moments()

◆ rotation_matrix_zyx()

◆ tetrahedron_signed_volume()

◆ to_euler_angles()