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:

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

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>

Functions

Function Documentation