 CGAL 5.0 - dD Geometry Kernel
Global Kernel Functions

## 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...

## ◆ affine_rank()

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

#include <CGAL/predicates_d.h>

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

Precondition
The objects in $$A$$ are of the same dimension.
Template Parameters
 ForwardIterator has Point_d as value type.

## ◆ affinely_independent()

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

#include <CGAL/predicates_d.h>

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

Precondition
The objects are of the same dimension.
Template Parameters
 ForwardIterator has Point_d as value type.

## ◆ center_of_sphere()

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

#include <CGAL/constructions_d.h>

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$$.
Template Parameters
 ForwardIterator has Point_d as value type.

## ◆ compare_lexicographically()

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

#include <CGAL/predicates_d.h>

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().

## ◆ contained_in_affine_hull()

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

#include <CGAL/predicates_d.h>

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.
Template Parameters
 ForwardIterator has Point_d as value type.

## ◆ contained_in_linear_hull()

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

#include <CGAL/predicates_d.h>

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.
Template Parameters
 ForwardIterator has Vector_d as value type.

## ◆ contained_in_simplex()

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

#include <CGAL/predicates_d.h>

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.
Template Parameters
 ForwardIterator has Point_d as value type.

## ◆ do_intersect()

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

#include <CGAL/intersections_d.h>

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:

• Point_d<R>
• Line_d<R>
• Ray_d<R>
• Segment_d<R>
• Hyperplane_d<R>
intersection

## ◆ intersection()

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

#include <CGAL/intersections_d.h>

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
Segment_d Line_d
Segment_d Segment_d
Ray_d Line_d
 Point_d Ray_d
Ray_d Segment_d
Ray_d Ray_d
 Point_d Segment_d Ray_d
Hyperplane_d Line_d
Hyperplane_d Ray_d
 Point_d Ray_d
Hyperplane_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
}
}
do_intersect
Kernel_d::Intersect_d
boost::optional
boost::variant
cpp11::result_of

## ◆ lexicographically_smaller()

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

#include <CGAL/predicates_d.h>

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

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

## ◆ lexicographically_smaller_or_equal()

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

#include <CGAL/predicates_d.h>

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().

## ◆ linear_base()

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

#include <CGAL/constructions_d.h>

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$$.
Template Parameters
 ForwardIterator has Vector_d as value type.

## ◆ linear_rank()

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

#include <CGAL/predicates_d.h>

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

Precondition
The objects are of the same dimension.
Template Parameters
 ForwardIterator has Vector_d as value type.

## ◆ linearly_independent()

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

#include <CGAL/predicates_d.h>

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

Precondition
The objects in A are of the same dimension.
Template Parameters
 ForwardIterator has Vector_d as value type.

## ◆ midpoint()

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

#include <CGAL/constructions_d.h>

computes the midpoint of the segment $$pq$$.

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

## ◆ orientation()

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

#include <CGAL/predicates_d.h>

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 & A & \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$$.
Template Parameters
 ForwardIterator has Point_d as value type.

## ◆ side_of_bounded_sphere()

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

#include <CGAL/predicates_d.h>

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.
Template Parameters
 ForwardIterator has Point_d as value type.

## ◆ side_of_oriented_sphere()

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

#include <CGAL/predicates_d.h>

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.
Template Parameters
 ForwardIterator has Point_d as value type.

## ◆ squared_distance()

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

#include <CGAL/constructions_d.h>

computes the square of the Euclidean distance between the two points $$p$$ and $$q$$.

Precondition
The dimensions of $$p$$ and $$q$$ are the same.