\( \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 4.4 - dD Geometry Kernel
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Functions
Global Kernel Functions
dD Geometry Kernel Reference

Functions

template<class ForwardIterator >
Point_d< R > CGAL::center_of_sphere (ForwardIterator first, ForwardIterator last)
 returns the center of the sphere spanned by the points in A = tuple[first,last). More...
 
Point_d< R > CGAL::lift_to_paraboloid (const Point_d< R > &p)
 returns the projection of \( p = (x_0,\ldots,x_{d-1})\) onto the paraboloid of revolution which is the point \( (p_0, \ldots,p_{d-1},\sum_{0 \le i < d}p_i^2)\) in \( (d+1)\)-space.
 
template<class ForwardIterator , class OutputIterator >
OutputIterator CGAL::linear_base (ForwardIterator first, ForwardIterator last, OutputIterator result)
 computes a basis of the linear space spanned by the vectors in A = tuple [first,last) and returns it via an iterator range starting in result. More...
 
Point_d< R > CGAL::midpoint (const Point_d< R > &p, const Point_d< R > &q)
 computes the midpoint of the segment \( pq\). More...
 
Point_d< R > CGAL::project_along_d_axis (const Point_d< R > &p)
 returns \( p\) projected along the \( d\)-axis onto the hyperspace spanned by the first \( d-1\) standard base vectors.
 
FT CGAL::squared_distance (Point_d< R > p, Point_d< R > q)
 computes the square of the Euclidean distance between the two points \( p\) and \( q\). More...
 
bool CGAL::do_intersect (Type1< R > obj1, Type2< R > obj2)
 checks whether obj1 and obj2 intersect. More...
 
cpp11::result_of
< R::Intersect_d(Type1< R >
, Type2< R >)>::type 		CGAL::intersection (Type1< R > f1, Type2< R > f2)
 returns the intersection between f1 and f2. More...
 
template<class ForwardIterator >
bool CGAL::affinely_independent (ForwardIterator first, ForwardIterator last)
 returns true iff the points in A = tuple [first,last) are affinely independent. More...
 
template<class ForwardIterator >
int CGAL::affine_rank (ForwardIterator first, ForwardIterator last)
 computes the affine rank of the points in A = tuple [first,last). More...
 
Comparison_result CGAL::compare_lexicographically (const Point_d< R > &p, const Point_d< R > &q)
 Compares the Cartesian coordinates of points p and q lexicographically in ascending order of its Cartesian components p[i] and q[i] for \( i = 0,\ldots,d-1\). More...
 
template<class ForwardIterator >
bool CGAL::contained_in_affine_hull (ForwardIterator first, ForwardIterator last, const Point_d< R > &p)
 determines whether \( p\) is contained in the affine hull of the points in A = tuple [first,last). More...
 
template<class ForwardIterator >
bool CGAL::contained_in_linear_hull (ForwardIterator first, ForwardIterator last, const Vector_d< R > &v)
 determines whether \( v\) is contained in the linear hull of the vectors in A = tuple [first,last). More...
 
template<class ForwardIterator >
bool CGAL::contained_in_simplex (ForwardIterator first, ForwardIterator last, const Point_d< R > &p)
 determines whether \( p\) is contained in the simplex of the points in A = tuple [first,last). More...
 
bool CGAL::lexicographically_smaller (const Point_d< R > &p, const Point_d< R > &q)
 returns true iff p is lexicographically smaller than q with respect to Cartesian lexicographic order of points. More...
 
bool CGAL::lexicographically_smaller_or_equal (const Point_d< R > &p, const Point_d< R > &q)
 returns true iff \( p\) is lexicographically smaller than \( q\) with respect to Cartesian lexicographic order of points or equal to \( q\). More...
 
template<class ForwardIterator >
bool CGAL::linearly_independent (ForwardIterator first, ForwardIterator last)
 decides whether the vectors in A = tuple [first,last) are linearly independent. More...
 
template<class ForwardIterator >
int CGAL::linear_rank (ForwardIterator first, ForwardIterator last)
 computes the linear rank of the vectors in A = tuple [first,last). More...
 
template<class ForwardIterator >
Orientation CGAL::orientation (ForwardIterator first, ForwardIterator last)
 determines the orientation of the points of the tuple A = tuple [first,last) where \( A\) consists of \( d+1\) points in \( d\)-space. More...
 
template<class ForwardIterator >
Bounded_side CGAL::side_of_bounded_sphere (ForwardIterator first, ForwardIterator last, const Point_d< R > &p)
 returns the relative position of point p to the sphere defined by A = tuple [first,last). More...
 
template<class ForwardIterator >
Oriented_side CGAL::side_of_oriented_sphere (ForwardIterator first, ForwardIterator last, const Point_d< R > &p)
 returns the relative position of point p to the oriented sphere defined by the points in A = tuple [first,last) The order of the points in \( A\) is important, since it determines the orientation of the implicitly constructed sphere. More...
 

Function Documentation

template<class ForwardIterator >
int CGAL::affine_rank ( ForwardIterator  first,
ForwardIterator  last 
)

computes the affine rank of the points in A = tuple [first,last).

Precondition
The objects in \( A\) are of the same dimension.
Requires:
The value type of ForwardIterator is Point_d<R>.

#include <CGAL/predicates_d.h>

template<class ForwardIterator >
bool CGAL::affinely_independent ( ForwardIterator  first,
ForwardIterator  last 
)

returns true iff the points in A = tuple [first,last) are affinely independent.

Precondition
The objects are of the same dimension.
Requires:
The value type of ForwardIterator is Point_d<R>

#include <CGAL/predicates_d.h>

template<class ForwardIterator >
Point_d<R> CGAL::center_of_sphere ( ForwardIterator  first,
ForwardIterator  last 
)

returns the center of the sphere spanned by the points in A = tuple[first,last).

Precondition
\( A\) contains \( d+1\) affinely independent points of dimension \( d\).
Requires:
The value type of ForwardIterator is Point_d<R>.

#include <CGAL/constructions_d.h>

Comparison_result CGAL::compare_lexicographically ( const Point_d< R > &  p,
const Point_d< R > &  q 
)

Compares the Cartesian coordinates of points p and q lexicographically in ascending order of its Cartesian components p[i] and q[i] for \( i = 0,\ldots,d-1\).

Precondition
p.dimension() == q.dimension().

#include <CGAL/predicates_d.h>

template<class ForwardIterator >
bool CGAL::contained_in_affine_hull ( ForwardIterator  first,
ForwardIterator  last,
const Point_d< R > &  p 
)

determines whether \( p\) is contained in the affine hull of the points in A = tuple [first,last).

Precondition
The objects in A are of the same dimension.
Requires:
The value type of ForwardIterator is Point_d<R>.

#include <CGAL/predicates_d.h>

template<class ForwardIterator >
bool CGAL::contained_in_linear_hull ( ForwardIterator  first,
ForwardIterator  last,
const Vector_d< R > &  v 
)

determines whether \( v\) is contained in the linear hull of the vectors in A = tuple [first,last).

Precondition
The objects in \( A\) are of the same dimension.
Requires:
The value type of ForwardIterator is Vector_d<R>.

#include <CGAL/predicates_d.h>

template<class ForwardIterator >
bool CGAL::contained_in_simplex ( ForwardIterator  first,
ForwardIterator  last,
const Point_d< R > &  p 
)

determines whether \( p\) is contained in the simplex of the points in A = tuple [first,last).

Precondition
The objects in \( A\) are of the same dimension and affinely independent.
Requires:
The value type of ForwardIterator is Point_d<R>.

#include <CGAL/predicates_d.h>

bool CGAL::do_intersect ( Type1< R >  obj1,
Type2< R >  obj2 
)

checks whether obj1 and obj2 intersect.

Two objects obj1 and obj2 intersect if there is a point p that is part of both obj1 and obj2. The intersection region of those two objects is defined as the set of all points p that are part of both obj1 and obj2.

Precondition
The objects are of the same dimension.

The types Type1 and Type2 can be any of the following:

See Also
intersection

#include <CGAL/intersections_d.h>

cpp11::result_of<R::Intersect_d(Type1<R>, Type2<R>)>::type CGAL::intersection ( Type1< R >  f1,
Type2< R >  f2 
)

returns the intersection between f1 and f2.

Precondition
The objects are of the same dimension.

The same functionality is also available through the functor Kernel::Intersect_d.

The following table gives the possible values for Type1 and Type2.

The return type can be obtained through cpp11::result_of<Kernel::Intersect_d(A, B)>::type. It is equivalent to boost::optional< boost::variant< T... > >, the last column in the table providing the template parameter pack.

Type1 Type2 T...
Line_d Line_d
Point_d
Line_d
Segment_d Line_d
Point_d
Segment_d
Segment_d Segment_d
Point_d
Segment_d
Ray_d Line_d
Point_d
Ray_d
Ray_d Segment_d
Point_d
Segment_d
Ray_d Ray_d
Point_d
Segment_d
Ray_d
Hyperplane_d Line_d
Point_d
Line_d
Hyperplane_d Ray_d
Point_d
Ray_d
Hyperplane_d Segment_d
Point_d
Segment_d

Example

The following example demonstrates the most common use of intersection routines.

#include <CGAL/intersections_d.h>
template<typename R>
struct Intersection_visitor {
typedef void result_type;
void operator()(const Point_d<R>& p) const {
// handle point
}
void operator()(const Segment_d<R>& s) const {
// handle segment
}
};
template <class R>
void foo(Segment_d<R> seg, Line_d<R> lin)
{
// with C++11 support
// auto result = intersection(seg, lin);
// without C++11 support
typename cpp11::result_of<R::Intersect_d(Segment_d<R>, Line_d<R>)>::type
result = intersection(seg, lin);
if(result) { boost::apply_visitor(Intersection_visitor<R>(), *result); }
else { // no intersection
}
}
See Also
do_intersect
Kernel_d::Intersect_d
CGAL_INTERSECTION_VERSION
boost::optional
boost::variant
cpp11::result_of

#include <CGAL/intersections_d.h>

bool CGAL::lexicographically_smaller ( const Point_d< R > &  p,
const Point_d< R > &  q 
)

returns true iff p is lexicographically smaller than q with respect to Cartesian lexicographic order of points.

Precondition
p.dimension() == q.dimension().

#include <CGAL/predicates_d.h>

bool CGAL::lexicographically_smaller_or_equal ( const Point_d< R > &  p,
const Point_d< R > &  q 
)

returns true iff \( p\) is lexicographically smaller than \( q\) with respect to Cartesian lexicographic order of points or equal to \( q\).

Precondition
p.dimension() == q.dimension().

#include <CGAL/predicates_d.h>

template<class ForwardIterator , class OutputIterator >
OutputIterator CGAL::linear_base ( ForwardIterator  first,
ForwardIterator  last,
OutputIterator  result 
)

computes a basis of the linear space spanned by the vectors in A = tuple [first,last) and returns it via an iterator range starting in result.

The returned iterator marks the end of the output.

Precondition
\( A\) contains vectors of the same dimension \( d\).
Requires:
The value type of ForwardIterator and OutputIterator is Vector_d<R>.

#include <CGAL/constructions_d.h>

template<class ForwardIterator >
int CGAL::linear_rank ( ForwardIterator  first,
ForwardIterator  last 
)

computes the linear rank of the vectors in A = tuple [first,last).

Precondition
The objects are of the same dimension.
Requires:
The value type of ForwardIterator is Vector_d<R>.

#include <CGAL/predicates_d.h>

template<class ForwardIterator >
bool CGAL::linearly_independent ( ForwardIterator  first,
ForwardIterator  last 
)

decides whether the vectors in A = tuple [first,last) are linearly independent.

Precondition
The objects in A are of the same dimension.
Requires:
The value type of ForwardIterator is Vector_d<R>.

#include <CGAL/predicates_d.h>

Point_d<R> CGAL::midpoint ( const Point_d< R > &  p,
const Point_d< R > &  q 
)

computes the midpoint of the segment \( pq\).

Precondition
p.dimension() == q.dimension().

#include <CGAL/constructions_d.h>

template<class ForwardIterator >
Orientation CGAL::orientation ( ForwardIterator  first,
ForwardIterator  last 
)

determines the orientation of the points of the tuple A = tuple [first,last) where \( A\) consists of \( d+1\) points in \( d\)-space.

This is the sign of the determinant

\[ \left| \begin{array}{cccc} 1 & 1 & 1 & 1 \\ A[0] & A[1] & \dots& A[d] \end{array} \right| \]

where A[i] denotes the Cartesian coordinate vector of the \( i\)-th point in \( A\).

Precondition
size [first,last) == d+1 and A[i].dimension() == d \( \forall0 \leq i \leq d\).
Requires:
The value type of ForwardIterator is Point_d<R>.

#include <CGAL/predicates_d.h>

template<class ForwardIterator >
Bounded_side CGAL::side_of_bounded_sphere ( ForwardIterator  first,
ForwardIterator  last,
const Point_d< R > &  p 
)

returns the relative position of point p to the sphere defined by A = tuple [first,last).

The order of the points of \( A\) does not matter.

Precondition
orientation(first,last) is not ZERO.
Requires:
The value type of ForwardIterator is Point_d<R>.

#include <CGAL/predicates_d.h>

template<class ForwardIterator >
Oriented_side CGAL::side_of_oriented_sphere ( ForwardIterator  first,
ForwardIterator  last,
const Point_d< R > &  p 
)

returns the relative position of point p to the oriented sphere defined by the points in A = tuple [first,last) The order of the points in \( A\) is important, since it determines the orientation of the implicitly constructed sphere.

If the points in \( A\) are positively oriented, the positive side is the bounded interior of the sphere.

Precondition
A contains \( d+1\) points in \( d\)-space.
Requires:
The value type of ForwardIterator is Point_d<R>.

#include <CGAL/predicates_d.h>

FT CGAL::squared_distance ( Point_d< R >  p,
Point_d< R >  q 
)

computes the square of the Euclidean distance between the two points \( p\) and \( q\).

Precondition
The dimensions of \( p\) and \( q\) are the same.

#include <CGAL/constructions_d.h>