 CGAL 5.3 - 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...

decltype(auto) 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()

 decltype(auto) 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 of intersecting two objects of the types Type1 and Type2 can be specified through the placeholder type specifier auto. 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)
{
// use auto
auto 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

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