Polygon Core Algorithms

List of Core Polygon algorithms. More...

Collaboration diagram for Polygon Core Algorithms:

Functions
template<Point2Concept PointType>
bool	vcl::areCounterClockwise (const PointType &p0, const PointType &p1, const PointType &p2)
	Checks if the three points are counter-clockwise.
template<Point2Concept PointType>
auto	vcl::collinearityTest (const PointType &p0, const PointType &p1, const PointType &p2)
	Computes the collinearity test between three points. The test returns a positive value if the points are counter-clockwise, a negative value if the points are clockwise, and zero if the points are collinear.
template<Point2IteratorConcept InputIterator>
auto	vcl::convexHull (InputIterator first, InputIterator end)
	Get the 2D convex hull using Graham scan algorithm on a set of points.
template<Polygon2Concept PolygonType>
PolygonType	vcl::createCircle (uint n, typename PolygonType::ScalarType radius=1.0)
	Create a 2D circle polygon with n vertices and the given radius.
template<FaceConcept Face>
std::vector< uint >	vcl::earCut (const Face &polygon)
	Computes the earcut algorithm of a 3D planar polygonal face, that returns a triangulation of the polygon.
template<Point2IteratorConcept Iterator>
std::vector< uint >	vcl::earCut (Iterator begin, Iterator end)
	Triangulates a simple polygon with no holes using the ear-cutting algorithm.
template<Range R>
std::vector< uint >	vcl::earCut (R &&range)
	Triangulates a simple polygon with no holes using the ear-cutting algorithm.
template<FaceConcept FaceType>
auto	vcl::faceAngleOnVertexRad (const FaceType &f, uint vi)
	Returns the internal angle (in radians) of the vi-th vertex of the face.
template<FaceConcept FaceType>
auto	vcl::faceArea (const FaceType &f)
	Computes the area of a face. Works both for triangle and polygonal faces, and it is optimized in case of triangle faces.
template<FaceConcept FaceType>
FaceType::VertexType::PositionType	vcl::faceBarycenter (const FaceType &f)
	Computes the barycenter of a face. Works both for triangle and polygonal faces, and it is optimized in case of triangle faces.
template<FaceConcept FaceType>
FaceType::VertexType::PositionType	vcl::faceNormal (const FaceType &f)
	Computes the normal of a face, without modifying the face. Works both for triangle and polygonal faces, and it is optimized in case of triangle faces.
template<FaceConcept FaceType>
auto	vcl::facePerimeter (const FaceType &f)
	Computes the perimeter of a face. Works both for triangle and polygonal faces, and it is optimized in case of triangle faces.
template<Point2IteratorConcept Iterator>
bool	vcl::isCounterClockWise (Iterator begin, Iterator end)
	Checks if a set of points that form a polygon are in counter-clockwise order.
template<Point3IteratorConcept Iterator>
auto	vcl::project (Iterator begin, Iterator end)
	Project a 3D polygon onto a plane, and return the 2D polygon.
template<Range R> requires Point3Concept<std::ranges::range_value_t<R>>
auto	vcl::project (R &&polygon)
	Project a 3D polygon defined by the given range onto a plane, and return the 2D polygon.
template<Point2IteratorConcept Iterator>
void	vcl::sortConvexPolygonVertices (Iterator begin, Iterator end)
	Sorts the vertices of a convex polygon in counter-clockwise order.

Detailed Description

List of Core Polygon algorithms.

Function Documentation

areCounterClockwise()

template<Point2Concept PointType>

bool vcl::areCounterClockwise	(	const PointType &	p0,
		const PointType &	p1,
		const PointType &	p2
	)

Checks if the three points are counter-clockwise.

Template Parameters

PointType

the type of the points that satisfies the Point2Concept.

Parameters

[in]	p0	the first point.
[in]	p1	the second point.
[in]	p2	the third point.

Returns

true if the points are counter-clockwise, false otherwise.

collinearityTest()

template<Point2Concept PointType>

auto vcl::collinearityTest	(	const PointType &	p0,
		const PointType &	p1,
		const PointType &	p2
	)

Computes the collinearity test between three points. The test returns a positive value if the points are counter-clockwise, a negative value if the points are clockwise, and zero if the points are collinear.

The function computes the z coordinate of the cross product between the vectors p1 - p0 and p2 - p0:

• If the result is 0, the points are collinear;
• if the result is positive, the three points constitute a "left turn" or counter-clockwise orientation (p0 is at the left of the line p1-p2);
• if the result is negative, a "right turn" or clockwise orientation (p0 is at the right of the line p1-p2).

Template Parameters

PointType

the type of the points that satisfies the Point2Concept.

Parameters

[in]	p0	the first point.
[in]	p1	the second point.
[in]	p2	the third point.

Returns

0 if the points are collinear, a positive value if the points are counter-clockwise, and a negative value if the points are clockwise.

convexHull()

template<Point2IteratorConcept InputIterator>

auto vcl::convexHull	(	InputIterator	first,
		InputIterator	end
	)

Get the 2D convex hull using Graham scan algorithm on a set of points.

Template Parameters

InputIterator

Iterator type of the input container of points. It must Iterate over a range of elements that satisfy the Point2Concept.

Parameters

[in]	first	First iterator of the input container of points.
[in]	end	End iterator of the input container of points.

Returns

A polygon representing the convex hull of the input points.

createCircle()

template<Polygon2Concept PolygonType>

PolygonType vcl::createCircle	(	uint	n,
		typename PolygonType::ScalarType	radius = 1.0
	)

Create a 2D circle polygon with n vertices and the given radius.

Template Parameters

PolygonType

The polygon type.

Parameters

[in]	n	The number of vertices.
[in]	radius	The radius of the circle.

Returns

The circle polygon.

earCut() [1/3]

template<FaceConcept Face>

std::vector< uint > vcl::earCut

(

const Face &

polygon

)

Computes the earcut algorithm of a 3D planar polygonal face, that returns a triangulation of the polygon.

Returns a list of indices in which each index is the index of a point of the 3D input polygon, organized in triplets, each one of these is a triangle of the resulting triangulation.

This algorithm first computes the normal of the given polygon, then projects it in a 2D plane and executes the classic 2D EarCut algorithm.

Template Parameters

Face	the type of the face that satisfies the FaceConcept.

Parameters

[in]

polygon

A (polygonal) face of a vcl::Mesh.

Returns

A vector of indices, representing the triplets of the triangulation of the polygon.

earCut() [2/3]

template<Point2IteratorConcept Iterator>

std::vector< uint > vcl::earCut	(	Iterator	begin,
		Iterator	end
	)

Triangulates a simple polygon with no holes using the ear-cutting algorithm.

Triangulates a simple polygon with no holes in 3D space by projecting it onto a 2D plane and applying the ear-cutting algorithm.

Template Parameters

Iterator

The type of iterator used to represent the vertices of the polygon. It must satisfy the Point2Concept requirement.

Parameters

[in]	begin	An iterator pointing to the first vertex of the polygon.
[in]	end	An iterator pointing to one past the last vertex of the polygon.

Returns

A vector containing the indices of the vertices that form triangles in the triangulated polygon. Each group of three indices represents the vertices of a single triangle, and the indices are ordered in a counter-clockwise direction.

Exceptions

std::logic_error

If the polygon is not simple or has holes.

Remarks

This function uses the ear-cutting algorithm to triangulate a simple polygon with no holes. The polygon is represented as a sequence of vertices, where each vertex is a two-dimensional point. The function returns a vector containing the indices of the vertices that form triangles in the triangulated polygon. The indices are ordered in a counter-clockwise direction, and each group of three indices represents the vertices of a single triangle. The function requires that the type of iterator used to represent the vertices of the polygon satisfies the Point2Concept requirement, which means that it must have a value_type that is a Point2 object with a ScalarType member representing the scalar type used to represent the position of the point. If the polygon is not simple or has holes, the function throws a std::logic_error.

Template Parameters

Iterator

The type of iterator used to represent the vertices of the polygon. It must satisfy the Point3Concept requirement.

Parameters

[in]	begin	An iterator pointing to the first vertex of the polygon.
[in]	end	An iterator pointing to one past the last vertex of the polygon.

Returns

A vector containing the indices of the vertices that form triangles in the triangulated polygon. Each group of three indices represents the vertices of a single triangle, and the indices are ordered in a counter-clockwise direction.

Exceptions

std::logic_error

If the polygon is not simple or has holes.

Remarks

This function triangulates a simple polygon with no holes in 3D space by projecting it onto a 2D plane and applying the ear-cutting algorithm. The polygon is represented as a sequence of vertices, where each vertex is a three-dimensional point. The function first calculates the normal vector of the polygon and an orthonormal basis for the plane containing the polygon. It then projects each vertex onto the plane and triangulates the resulting 2D polygon using the ear-cutting algorithm. The function returns a vector containing the indices of the vertices that form triangles in the triangulated polygon. The indices are ordered in a counter-clockwise direction, and each group of three indices represents the vertices of a single triangle. The function requires that the type of iterator used to represent the vertices of the polygon satisfies the Point3Concept requirement, which means that it must have a value_type that is a Point3 object with a ScalarType member representing the scalar type used to represent the position of the point. If the polygon is not simple or has holes, the function throws a std::logic_error.

earCut() [3/3]

template<Range R>

std::vector< uint > vcl::earCut

(

R &&

range

)

Triangulates a simple polygon with no holes using the ear-cutting algorithm.

Template Parameters

R	a range of points that satisfy the PointConcept.

Parameters

[in]

range

the range of points that define the polygon.

Returns

A vector containing the indices of the vertices that form triangles in the triangulated polygon.

faceAngleOnVertexRad()

template<FaceConcept FaceType>

auto vcl::faceAngleOnVertexRad	(	const FaceType &	f,
		uint	vi
	)

Returns the internal angle (in radians) of the vi-th vertex of the face.

Template Parameters

FaceType

the type of the face that satisfies the FaceConcept.

Parameters

[in]	f	the input face.
[in]	vi	the index of the vertex in the face on which calculate the angle

Returns

the angle in radians at the vi-th vertex.

faceArea()

template<FaceConcept FaceType>

auto vcl::faceArea

(

const FaceType &

f

)

Computes the area of a face. Works both for triangle and polygonal faces, and it is optimized in case of triangle faces.

Template Parameters

FaceType

the type of the face that satisfies the FaceConcept.

Parameters

[in]

f

the input face.

Returns

the area of the face.

faceBarycenter()

template<FaceConcept FaceType>

FaceType::VertexType::PositionType vcl::faceBarycenter

(

const FaceType &

f

)

Computes the barycenter of a face. Works both for triangle and polygonal faces, and it is optimized in case of triangle faces.

Template Parameters

FaceType

the type of the face that satisfies the FaceConcept.

Parameters

[in]

f

the input face.

Returns

the barycenter of the face.

faceNormal()

template<FaceConcept FaceType>

FaceType::VertexType::PositionType vcl::faceNormal

(

const FaceType &

f

)

Computes the normal of a face, without modifying the face. Works both for triangle and polygonal faces, and it is optimized in case of triangle faces.

Template Parameters

FaceType

the type of the face that satisfies the FaceConcept.

Parameters

[in]

f

the input face.

Returns

the normal of the face.

facePerimeter()

template<FaceConcept FaceType>

auto vcl::facePerimeter

(

const FaceType &

f

)

Computes the perimeter of a face. Works both for triangle and polygonal faces, and it is optimized in case of triangle faces.

Template Parameters

FaceType

the type of the face that satisfies the FaceConcept.

Parameters

[in]

f

the input face.

Returns

the perimeter of the face.

isCounterClockWise()

template<Point2IteratorConcept Iterator>

bool vcl::isCounterClockWise	(	Iterator	begin,
		Iterator	end
	)

Checks if a set of points that form a polygon are in counter-clockwise order.

Template Parameters

Iterator

the type of iterator that iterates over a range of points that satisfy the Point2Concept.

Parameters

[in]	begin	the iterator pointing to the first point.
[in]	end	the iterator pointing to one past the last point.

Returns

true if the points are in counter-clockwise order, false otherwise.

project() [1/2]

template<Point3IteratorConcept Iterator>

auto vcl::project	(	Iterator	begin,
		Iterator	end
	)

Project a 3D polygon onto a plane, and return the 2D polygon.

Template Parameters

Iterator

Iterator type, it must iterate over 3D points.

Parameters

[in]	begin	Iterator to the first point of the polygon.
[in]	end	Iterator to the past-the-end point of the polygon.

Returns

The projected polygon.

project() [2/2]

template<Range R>
requires Point3Concept<std::ranges::range_value_t<R>>

auto vcl::project

(

R &&

polygon

)

Project a 3D polygon defined by the given range onto a plane, and return the 2D polygon.

Template Parameters

R	A range of 3D points.

Parameters

[in]

polygon

The input polygon.

Returns

The projected polygon.

sortConvexPolygonVertices()

template<Point2IteratorConcept Iterator>

void vcl::sortConvexPolygonVertices	(	Iterator	begin,
		Iterator	end
	)

Sorts the vertices of a convex polygon in counter-clockwise order.

Given a set of points that form a convex polygon, this function sorts the points in counter-clockwise order. The function assumes that the input points form a convex polygon, and it sorts the points in counter-clockwise order with respect to the point with the lowest y-coordinate. The function uses the atan2 function to compute the angle of each point with respect to the point with the lowest y-coordinate, and it sorts the points based on these angles.

Template Parameters

Iterator

the type of iterator that iterates over a range of points that satisfy the Point2Concept.

Parameters

[in]	begin	the iterator pointing to the first point.
[in]	end	the iterator pointing to one past the last point.