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.

Template Parameters

ForwardIterator has Point_d<R> as value type.

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

Template Parameters

ForwardIterator has Point_d<R> as value type.

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

Template Parameters

ForwardIterator has Point_d<R> as value type.

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

Template Parameters

ForwardIterator has Point_d<R> as value type.

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

Template Parameters

ForwardIterator has Vector_d<R> as value type.

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

Template Parameters

ForwardIterator has Point_d<R> as value type.

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

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

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

Ray_d

Line_d

Ray_d

Line_d

Ray_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\).

Template Parameters

ForwardIterator has Vector_d<R> as value type.

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

Template Parameters

ForwardIterator has Vector_d<R> as value type.

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

Template Parameters

ForwardIterator has Vector_d<R> as value type.

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

Template Parameters

ForwardIterator has Point_d<R> as value type.

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

Template Parameters

ForwardIterator has Point_d<R> as value type.

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

Template Parameters

ForwardIterator has Point_d<R> as value type.

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

Functions

Function Documentation