Free functions to compute barycentric weights and coordinates.

Functions
template<typename PointRange , typename OutIterator , typename GeomTraits >
OutIterator	CGAL::Barycentric_coordinates::discrete_harmonic_weights_2 (const PointRange &polygon, const typename GeomTraits::Point_2 &query, OutIterator w_begin, const GeomTraits &traits, const Computation_policy_2 policy=Computation_policy_2::FAST_WITH_EDGE_CASES)
	computes 2D discrete harmonic weights. More...

template<typename PointRange , typename OutIterator , typename GeomTraits >
OutIterator	CGAL::Barycentric_coordinates::discrete_harmonic_coordinates_2 (const PointRange &polygon, const typename GeomTraits::Point_2 &query, OutIterator c_begin, const GeomTraits &traits, const Computation_policy_2 policy=Computation_policy_2::PRECISE_WITH_EDGE_CASES)
	computes 2D discrete harmonic coordinates. More...

template<typename PointRange , typename OutIterator , typename GeomTraits >
OutIterator	CGAL::Barycentric_coordinates::mean_value_weights_2 (const PointRange &polygon, const typename GeomTraits::Point_2 &query, OutIterator w_begin, const GeomTraits &traits, const Computation_policy_2 policy=Computation_policy_2::FAST_WITH_EDGE_CASES)
	computes 2D mean value weights. More...

template<typename PointRange , typename OutIterator , typename GeomTraits >
OutIterator	CGAL::Barycentric_coordinates::mean_value_coordinates_2 (const PointRange &polygon, const typename GeomTraits::Point_2 &query, OutIterator c_begin, const GeomTraits &traits, const Computation_policy_2 policy=Computation_policy_2::PRECISE_WITH_EDGE_CASES)
	computes 2D mean value coordinates. More...

template<typename PointRange , typename OutIterator , typename GeomTraits >
OutIterator	CGAL::Barycentric_coordinates::wachspress_weights_2 (const PointRange &polygon, const typename GeomTraits::Point_2 &query, OutIterator w_begin, const GeomTraits &traits, const Computation_policy_2 policy=Computation_policy_2::FAST_WITH_EDGE_CASES)
	computes 2D Wachspress weights. More...

template<typename PointRange , typename OutIterator , typename GeomTraits >
OutIterator	CGAL::Barycentric_coordinates::wachspress_coordinates_2 (const PointRange &polygon, const typename GeomTraits::Point_2 &query, OutIterator c_begin, const GeomTraits &traits, const Computation_policy_2 policy=Computation_policy_2::PRECISE_WITH_EDGE_CASES)
	computes 2D Wachspress coordinates. More...

template<typename VertexRange , typename OutIterator , typename GeomTraits , typename PointMap >
std::pair< OutIterator, bool >	CGAL::Barycentric_coordinates::boundary_coordinates_2 (const VertexRange &polygon, const typename GeomTraits::Point_2 &query, OutIterator c_begin, const GeomTraits &traits, const PointMap point_map)
	computes 2D boundary coordinates. More...

template<typename VertexRange , typename Query_2 , typename OutIterator , typename PointMap = CGAL::Identity_property_map<Query_2>>
std::pair< OutIterator, bool >	CGAL::Barycentric_coordinates::boundary_coordinates_2 (const VertexRange &polygon, const Query_2 &query, OutIterator c_begin, const PointMap point_map=PointMap())
	computes 2D boundary coordinates. More...

template<typename OutIterator , typename GeomTraits >
OutIterator	CGAL::Barycentric_coordinates::segment_coordinates_2 (const typename GeomTraits::Point_2 &p0, const typename GeomTraits::Point_2 &p1, const typename GeomTraits::Point_2 &query, OutIterator c_begin, const GeomTraits &traits)
	computes segment coordinates. More...

template<typename OutIterator , typename GeomTraits >
OutIterator	CGAL::Barycentric_coordinates::triangle_coordinates_2 (const typename GeomTraits::Point_2 &p0, const typename GeomTraits::Point_2 &p1, const typename GeomTraits::Point_2 &p2, const typename GeomTraits::Point_2 &query, OutIterator c_begin, const GeomTraits &traits)
	computes triangle coordinates. More...

Function Documentation

◆ boundary_coordinates_2() [1/2]

template<typename VertexRange , typename OutIterator , typename GeomTraits , typename PointMap >

std::pair<OutIterator, bool> CGAL::Barycentric_coordinates::boundary_coordinates_2	(	const VertexRange &	polygon,
		const typename GeomTraits::Point_2 &	query,
		OutIterator	c_begin,
		const GeomTraits &	traits,
		const PointMap	point_map
	)

#include <CGAL/Barycentric_coordinates_2/boundary_coordinates_2.h>

computes 2D boundary coordinates.

This function computes boundary barycentric coordinates at a given query point with respect to the vertices of a simple polygon, that is one coordinate per vertex. The coordinates are stored in a destination range beginning at c_begin.

If query is at the vertex, the corresponding coordinate is set to one, while all other coordinates are zero. If query is on the edge, the two corresponding coordinates are segment coordinates, while all other coordinates are set to zero. If query is not on the boundary, all the coordinates are set to zero.

Internally, segment_coordinates_2() are used.

Template Parameters

VertexRange	a model of `ConstRange` whose iterator type is `RandomAccessIterator`
OutIterator	a model of `OutputIterator` that accepts values of type `GeomTraits::FT`
GeomTraits	a model of `BarycentricTraits_2`
PointMap	a model of `ReadablePropertyMap` whose key type is `VertexRange::value_type` and value type is `GeomTraits::Point_2`

Parameters

polygon	an instance of `VertexRange` with 2D points, which form a simple polygon
query	a query point
c_begin	the beginning of the destination range with the computed coordinates
traits	a traits class with geometric objects, predicates, and constructions; this parameter can be omitted if the traits class can be deduced from the point type
point_map	an instance of `PointMap` that maps a vertex from `polygon` to `Point_2`

Returns: an output iterator to the element in the destination range, one past the last coordinate stored + the flag indicating whether the query point belongs to the polygon boundary

Precondition: polygon.size() >= 3

Examples:: Barycentric_coordinates_2/discrete_harmonic_coordinates.cpp.

◆ boundary_coordinates_2() [2/2]

template<typename VertexRange , typename Query_2 , typename OutIterator , typename PointMap = CGAL::Identity_property_map<Query_2>>

std::pair<OutIterator, bool> CGAL::Barycentric_coordinates::boundary_coordinates_2	(	const VertexRange &	polygon,
		const Query_2 &	query,
		OutIterator	c_begin,
		const PointMap	point_map = `PointMap()`
	)

#include <CGAL/Barycentric_coordinates_2/boundary_coordinates_2.h>

computes 2D boundary coordinates.

This is an overload of the function boundary_coordinates_2.

Template Parameters

VertexRange	a model of `ConstRange` whose iterator type is `RandomAccessIterator`
Query_2	a model of `Kernel::Point_2`
OutIterator	a model of `OutputIterator` that accepts values of type `GeomTraits::FT`
PointMap	a model of `ReadablePropertyMap` whose key type is `VertexRange::value_type` and value type is `Query_2`. The default is `CGAL::Identity_property_map`.

Parameters

polygon	an instance of `VertexRange` with 2D points, which form a simple polygon
query	a query point
c_begin	the beginning of the destination range with the computed coordinates
point_map	an instance of `PointMap` that maps a vertex from `polygon` to `Query_2`; the default initialization is provided

Returns: an output iterator to the element in the destination range, one past the last coordinate stored + the flag indicating whether the query point belongs to the polygon boundary

Precondition: polygon.size() >= 3

◆ discrete_harmonic_coordinates_2()

template<typename PointRange , typename OutIterator , typename GeomTraits >

OutIterator CGAL::Barycentric_coordinates::discrete_harmonic_coordinates_2	(	const PointRange &	polygon,
		const typename GeomTraits::Point_2 &	query,
		OutIterator	c_begin,
		const GeomTraits &	traits,
		const Computation_policy_2	policy = `Computation_policy_2::PRECISE_WITH_EDGE_CASES`
	)

#include <CGAL/Barycentric_coordinates_2/Discrete_harmonic_coordinates_2.h>

computes 2D discrete harmonic coordinates.

This function computes 2D discrete harmonic coordinates at a given query point with respect to the vertices of a strictly convex polygon, that is one coordinate per vertex. The coordinates are stored in a destination range beginning at c_begin.

Internally, the class Discrete_harmonic_coordinates_2 is used. If one wants to process multiple query points, it is better to use that class. When using the free function, internal memory is allocated for each query point, while when using the class, it is allocated only once, which is much more efficient. However, for a few query points, it is easier to use this function. It can also be used when the processing time is not a concern.

Template Parameters

PointRange	a model of `ConstRange` whose iterator type is `RandomAccessIterator` and value type is `GeomTraits::Point_2`
OutIterator	a model of `OutputIterator` that accepts values of type `GeomTraits::FT`
GeomTraits	a model of `BarycentricTraits_2`

Parameters

polygon	an instance of `PointRange` with 2D points, which form a strictly convex polygon
query	a query point
c_begin	the beginning of the destination range with the computed coordinates
traits	a traits class with geometric objects, predicates, and constructions; this parameter can be omitted if the traits class can be deduced from the point type
policy	one of the `Computation_policy_2`; the default is `Computation_policy_2::PRECISE_WITH_EDGE_CASES`

Returns: an output iterator to the element in the destination range, one past the last coordinate stored

Precondition: polygon.size() >= 3; polygon is simple; polygon is strictly convex

◆ discrete_harmonic_weights_2()

template<typename PointRange , typename OutIterator , typename GeomTraits >

OutIterator CGAL::Barycentric_coordinates::discrete_harmonic_weights_2	(	const PointRange &	polygon,
		const typename GeomTraits::Point_2 &	query,
		OutIterator	w_begin,
		const GeomTraits &	traits,
		const Computation_policy_2	policy = `Computation_policy_2::FAST_WITH_EDGE_CASES`
	)

#include <CGAL/Barycentric_coordinates_2/Discrete_harmonic_coordinates_2.h>

computes 2D discrete harmonic weights.

This function computes 2D discrete harmonic weights at a given query point with respect to the vertices of a strictly convex polygon, that is one weight per vertex. The weights are stored in a destination range beginning at w_begin.

Internally, the class Discrete_harmonic_coordinates_2 is used. If one wants to process multiple query points, it is better to use that class. When using the free function, internal memory is allocated for each query point, while when using the class, it is allocated only once, which is much more efficient. However, for a few query points, it is easier to use this function. It can also be used when the processing time is not a concern.

Template Parameters

PointRange	a model of `ConstRange` whose iterator type is `RandomAccessIterator` and value type is `GeomTraits::Point_2`
OutIterator	a model of `OutputIterator` that accepts values of type `GeomTraits::FT`
GeomTraits	a model of `BarycentricTraits_2`

Parameters

polygon	an instance of `PointRange` with 2D points, which form a strictly convex polygon
query	a query point
w_begin	the beginning of the destination range with the computed weights
traits	a traits class with geometric objects, predicates, and constructions; this parameter can be omitted if the traits class can be deduced from the point type
policy	one of the `Computation_policy_2`; the default is `Computation_policy_2::FAST_WITH_EDGE_CASES`

Returns: an output iterator to the element in the destination range, one past the last weight stored

Precondition: polygon.size() >= 3; polygon is simple; polygon is strictly convex

◆ mean_value_coordinates_2()

template<typename PointRange , typename OutIterator , typename GeomTraits >

OutIterator CGAL::Barycentric_coordinates::mean_value_coordinates_2	(	const PointRange &	polygon,
		const typename GeomTraits::Point_2 &	query,
		OutIterator	c_begin,
		const GeomTraits &	traits,
		const Computation_policy_2	policy = `Computation_policy_2::PRECISE_WITH_EDGE_CASES`
	)

#include <CGAL/Barycentric_coordinates_2/Mean_value_coordinates_2.h>

computes 2D mean value coordinates.

This function computes 2D mean value coordinates at a given query point with respect to the vertices of a simple polygon, that is one coordinate per vertex. The coordinates are stored in a destination range beginning at c_begin.

Internally, the class Mean_value_coordinates_2 is used. If one wants to process multiple query points, it is better to use that class. When using the free function, internal memory is allocated for each query point, while when using the class, it is allocated only once, which is much more efficient. However, for a few query points, it is easier to use this function. It can also be used when the processing time is not a concern.

Template Parameters

PointRange	a model of `ConstRange` whose iterator type is `RandomAccessIterator` and value type is `GeomTraits::Point_2`
OutIterator	a model of `OutputIterator` that accepts values of type `GeomTraits::FT`
GeomTraits	a model of `BarycentricTraits_2`

Parameters

polygon	an instance of `PointRange` with 2D points, which form a simple polygon
query	a query point
c_begin	the beginning of the destination range with the computed coordinates
traits	a traits class with geometric objects, predicates, and constructions; this parameter can be omitted if the traits class can be deduced from the point type
policy	one of the `Computation_policy_2`; the default is `Computation_policy_2::PRECISE_WITH_EDGE_CASES`

Returns: an output iterator to the element in the destination range, one past the last coordinate stored

Precondition: polygon.size() >= 3; polygon is simple

Examples:: Barycentric_coordinates_2/mean_value_coordinates.cpp, and Barycentric_coordinates_2/terrain_height_modeling.cpp.

◆ mean_value_weights_2()

template<typename PointRange , typename OutIterator , typename GeomTraits >

OutIterator CGAL::Barycentric_coordinates::mean_value_weights_2	(	const PointRange &	polygon,
		const typename GeomTraits::Point_2 &	query,
		OutIterator	w_begin,
		const GeomTraits &	traits,
		const Computation_policy_2	policy = `Computation_policy_2::FAST_WITH_EDGE_CASES`
	)

#include <CGAL/Barycentric_coordinates_2/Mean_value_coordinates_2.h>

computes 2D mean value weights.

This function computes 2D mean value weights at a given query point with respect to the vertices of a simple polygon, that is one weight per vertex. The weights are stored in a destination range beginning at w_begin.

Internally, the class Mean_value_coordinates_2 is used. If one wants to process multiple query points, it is better to use that class. When using the free function, internal memory is allocated for each query point, while when using the class, it is allocated only once, which is much more efficient. However, for a few query points, it is easier to use this function. It can also be used when the processing time is not a concern.

Template Parameters

PointRange	a model of `ConstRange` whose iterator type is `RandomAccessIterator` and value type is `GeomTraits::Point_2`
OutIterator	a model of `OutputIterator` that accepts values of type `GeomTraits::FT`
GeomTraits	a model of `BarycentricTraits_2`

Parameters

polygon	an instance of `PointRange` with 2D points, which form a simple polygon
query	a query point
w_begin	the beginning of the destination range with the computed weights
traits	a traits class with geometric objects, predicates, and constructions; this parameter can be omitted if the traits class can be deduced from the point type
policy	one of the `Computation_policy_2`; the default is `Computation_policy_2::FAST_WITH_EDGE_CASES`

Returns: an output iterator to the element in the destination range, one past the last weight stored

Precondition: polygon.size() >= 3; polygon is simple

◆ segment_coordinates_2()

template<typename OutIterator , typename GeomTraits >

OutIterator CGAL::Barycentric_coordinates::segment_coordinates_2	(	const typename GeomTraits::Point_2 &	p0,
		const typename GeomTraits::Point_2 &	p1,
		const typename GeomTraits::Point_2 &	query,
		OutIterator	c_begin,
		const GeomTraits &	traits
	)

#include <CGAL/Barycentric_coordinates_2/segment_coordinates_2.h>

computes segment coordinates.

This function computes barycentric coordinates at a given query point with respect to the end points p0 and p1 of a segment that is one coordinate per end point. The coordinates are stored in a destination range beginning at c_begin.

After the coordinates \(b_0\) and \(b_1\) are computed, the query point \(q\) can be obtained as \(q = b_0p_0 + b_1p_1\). If \(q\) does not belong to the line through \(p_0\) and \(p_1\), it is projected onto this line, and only then the coordinates are computed. See more details in the user manual here.

Template Parameters

OutIterator	a model of `OutputIterator` that accepts values of type `GeomTraits::FT`
GeomTraits	a model of `BarycentricTraits_2`

Parameters

p0	the first vertex of a segment
p1	the second vertex of a segment
query	a query point
c_begin	the beginning of the destination range with the computed coordinates
traits	a traits class with geometric objects, predicates, and constructions; this parameter can be omitted if the traits class can be deduced from the point type

Returns: an output iterator to the element in the destination range, one past the last coordinate stored

Precondition: p0 != p1

Examples:: Barycentric_coordinates_2/segment_coordinates.cpp.

◆ triangle_coordinates_2()

template<typename OutIterator , typename GeomTraits >

OutIterator CGAL::Barycentric_coordinates::triangle_coordinates_2	(	const typename GeomTraits::Point_2 &	p0,
		const typename GeomTraits::Point_2 &	p1,
		const typename GeomTraits::Point_2 &	p2,
		const typename GeomTraits::Point_2 &	query,
		OutIterator	c_begin,
		const GeomTraits &	traits
	)

#include <CGAL/Barycentric_coordinates_2/triangle_coordinates_2.h>

computes triangle coordinates.

This function computes barycentric coordinates at a given query point with respect to the points p0, p1, and p2, which form a triangle, that is one coordinate per point. The coordinates are stored in a destination range beginning at c_begin.

After the coordinates \(b_0\), \(b_1\), and \(b_2\) are computed, the query point \(q\) can be obtained as \(q = b_0p_0 + b_1p_1 + b_2p_2\). See more details in the user manual here.

Template Parameters

OutIterator	a model of `OutputIterator` that accepts values of type `GeomTraits::FT`
GeomTraits	a model of `BarycentricTraits_2`

Parameters

p0	the first vertex of a triangle
p1	the second vertex of a triangle
p2	the third vertex of a triangle
query	a query point
c_begin	the beginning of the destination range with the computed coordinates
traits	a traits class with geometric objects, predicates, and constructions; this parameter can be omitted if the traits class can be deduced from the point type

Returns: an output iterator to the element in the destination range, one past the last coordinate stored

Precondition: area_2(p0, p1, p2) != 0

Examples:: Barycentric_coordinates_2/triangle_coordinates.cpp.

◆ wachspress_coordinates_2()

template<typename PointRange , typename OutIterator , typename GeomTraits >

OutIterator CGAL::Barycentric_coordinates::wachspress_coordinates_2	(	const PointRange &	polygon,
		const typename GeomTraits::Point_2 &	query,
		OutIterator	c_begin,
		const GeomTraits &	traits,
		const Computation_policy_2	policy = `Computation_policy_2::PRECISE_WITH_EDGE_CASES`
	)

#include <CGAL/Barycentric_coordinates_2/Wachspress_coordinates_2.h>

computes 2D Wachspress coordinates.

This function computes 2D Wachspress coordinates at a given query point with respect to the vertices of a strictly convex polygon, that is one coordinate per vertex. The coordinates are stored in a destination range beginning at c_begin.

Internally, the class Wachspress_coordinates_2 is used. If one wants to process multiple query points, it is better to use that class. When using the free function, internal memory is allocated for each query point, while when using the class, it is allocated only once, which is much more efficient. However, for a few query points, it is easier to use this function. It can also be used when the processing time is not a concern.

Template Parameters

PointRange	a model of `ConstRange` whose iterator type is `RandomAccessIterator` and value type is `GeomTraits::Point_2`
OutIterator	a model of `OutputIterator` that accepts values of type `GeomTraits::FT`
GeomTraits	a model of `BarycentricTraits_2`

Parameters

polygon	an instance of `PointRange` with 2D points, which form a strictly convex polygon
query	a query point
c_begin	the beginning of the destination range with the computed coordinates
traits	a traits class with geometric objects, predicates, and constructions; this parameter can be omitted if the traits class can be deduced from the point type
policy	one of the `Computation_policy_2`; the default is `Computation_policy_2::PRECISE_WITH_EDGE_CASES`

Returns: an output iterator to the element in the destination range, one past the last coordinate stored

Precondition: polygon.size() >= 3; polygon is simple; polygon is strictly convex

Examples:: Barycentric_coordinates_2/wachspress_coordinates.cpp.

◆ wachspress_weights_2()

template<typename PointRange , typename OutIterator , typename GeomTraits >

OutIterator CGAL::Barycentric_coordinates::wachspress_weights_2	(	const PointRange &	polygon,
		const typename GeomTraits::Point_2 &	query,
		OutIterator	w_begin,
		const GeomTraits &	traits,
		const Computation_policy_2	policy = `Computation_policy_2::FAST_WITH_EDGE_CASES`
	)

#include <CGAL/Barycentric_coordinates_2/Wachspress_coordinates_2.h>

computes 2D Wachspress weights.

This function computes 2D Wachspress weights at a given query point with respect to the vertices of a strictly convex polygon, that is one weight per vertex. The weights are stored in a destination range beginning at w_begin.

Internally, the class Wachspress_coordinates_2 is used. If one wants to process multiple query points, it is better to use that class. When using the free function, internal memory is allocated for each query point, while when using the class, it is allocated only once, which is much more efficient. However, for a few query points, it is easier to use this function. It can also be used when the processing time is not a concern.

Template Parameters

PointRange	a model of `ConstRange` whose iterator type is `RandomAccessIterator` and value type is `GeomTraits::Point_2`
OutIterator	a model of `OutputIterator` that accepts values of type `GeomTraits::FT`
GeomTraits	a model of `BarycentricTraits_2`

Parameters

polygon	an instance of `PointRange` with 2D points, which form a strictly convex polygon
query	a query point
w_begin	the beginning of the destination range with the computed weights
traits	a traits class with geometric objects, predicates, and constructions; this parameter can be omitted if the traits class can be deduced from the point type
policy	one of the `Computation_policy_2`; the default is `Computation_policy_2::FAST_WITH_EDGE_CASES`

Returns: an output iterator to the element in the destination range, one past the last weight stored

Precondition: polygon.size() >= 3; polygon is simple; polygon is strictly convex

Functions

Function Documentation

◆ boundary_coordinates_2() [1/2]

◆ boundary_coordinates_2() [2/2]

◆ discrete_harmonic_coordinates_2()

◆ discrete_harmonic_weights_2()

◆ mean_value_coordinates_2()

◆ mean_value_weights_2()

◆ segment_coordinates_2()

◆ triangle_coordinates_2()

◆ wachspress_coordinates_2()

◆ wachspress_weights_2()