igl::predicates Namespace Reference

Functions
template<typename DerivedC, typename Derivedq>
DerivedC::Scalar	cubic_winding_number (const Eigen::MatrixBase< DerivedC > &C, const Eigen::MatrixBase< Derivedq > &q)
	Computes the (generalized) winding number of a cubic Bézier curve around a query.
template<typename DerivedV, typename DerivedF>
void	delaunay_triangulation (const Eigen::MatrixBase< DerivedV > &V, Eigen::PlainObjectBase< DerivedF > &F)
	Given a set of points in 2D, return a Delaunay triangulation of these points using predicates.
template<typename DerivedP, typename DerivedRT, typename DerivedF, typename DerivedI>
void	ear_clipping (const Eigen::MatrixBase< DerivedP > &P, const Eigen::MatrixBase< DerivedRT > &RT, Eigen::PlainObjectBase< DerivedF > &eF, Eigen::PlainObjectBase< DerivedI > &I)
	Implementation of ear clipping triangulation algorithm for a 2D polygon.
template<typename DerivedP, typename DerivedF>
bool	ear_clipping (const Eigen::MatrixBase< DerivedP > &P, Eigen::PlainObjectBase< DerivedF > &eF)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
void	exactinit ()
	Initialize internal variable used by predciates.
template<typename DerivedV1, typename DerivedF1, typename DerivedV2, typename DerivedF2, typename DerivedIF, typename DerivedCP>
bool	find_intersections (const AABB< DerivedV1, 3 > &tree1, const Eigen::MatrixBase< DerivedV1 > &V1, const Eigen::MatrixBase< DerivedF1 > &F1, const Eigen::MatrixBase< DerivedV2 > &V2, const Eigen::MatrixBase< DerivedF2 > &F2, const bool first_only, Eigen::PlainObjectBase< DerivedIF > &IF, Eigen::PlainObjectBase< DerivedCP > &CP)
	Identify triangles where two meshes interesect using AABBTree and igl::predicates::triangle_triangle_intersect.
template<typename DerivedV1, typename DerivedF1, typename DerivedV2, typename DerivedF2, typename DerivedIF, typename DerivedCP>
bool	find_intersections (const Eigen::MatrixBase< DerivedV1 > &V1, const Eigen::MatrixBase< DerivedF1 > &F1, const Eigen::MatrixBase< DerivedV2 > &V2, const Eigen::MatrixBase< DerivedF2 > &F2, const bool first_only, Eigen::PlainObjectBase< DerivedIF > &IF, Eigen::PlainObjectBase< DerivedCP > &CP)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
template<typename DerivedV1, typename DerivedF1, typename DerivedV2, typename DerivedF2, typename DerivedIF, typename DerivedCP, typename DerivedEV, typename DerivedEE, typename DerivedEI>
bool	find_intersections (const Eigen::MatrixBase< DerivedV1 > &V1, const Eigen::MatrixBase< DerivedF1 > &F1, const Eigen::MatrixBase< DerivedV2 > &V2, const Eigen::MatrixBase< DerivedF2 > &F2, Eigen::PlainObjectBase< DerivedIF > &IF, Eigen::PlainObjectBase< DerivedCP > &CP, Eigen::PlainObjectBase< DerivedEV > &EV, Eigen::PlainObjectBase< DerivedEE > &EE, Eigen::PlainObjectBase< DerivedEI > &EI)
template<typename DerivedV1, typename DerivedF1, typename DerivedV2, typename DerivedF2, typename DerivedIF, typename DerivedCP, typename DerivedEV, typename DerivedEE, typename DerivedEI>
bool	find_intersections (const igl::AABB< DerivedV1, 3 > &tree1, const Eigen::MatrixBase< DerivedV1 > &V1, const Eigen::MatrixBase< DerivedF1 > &F1, const Eigen::MatrixBase< DerivedV2 > &V2, const Eigen::MatrixBase< DerivedF2 > &F2, Eigen::PlainObjectBase< DerivedIF > &IF, Eigen::PlainObjectBase< DerivedCP > &CP, Eigen::PlainObjectBase< DerivedEV > &EV, Eigen::PlainObjectBase< DerivedEE > &EE, Eigen::PlainObjectBase< DerivedEI > &EI)
template<typename DerivedV, typename DerivedF, typename DerivedIF, typename DerivedCP>
bool	find_self_intersections (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedF > &F, const bool first_only, Eigen::PlainObjectBase< DerivedIF > &IF, Eigen::PlainObjectBase< DerivedCP > &CP)
	Identify triangle-triangle interesections within the same mesh using AABBTree and igl::predicates::triangle_triangle_intersect.
template<typename DerivedV, typename DerivedF, typename DerivedIF, typename DerivedCP, typename DerivedEV, typename DerivedEE, typename DerivedEI>
bool	find_self_intersections (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedF > &F, Eigen::PlainObjectBase< DerivedIF > &IF, Eigen::PlainObjectBase< DerivedCP > &CP, Eigen::PlainObjectBase< DerivedEV > &EV, Eigen::PlainObjectBase< DerivedEE > &EE, Eigen::PlainObjectBase< DerivedEI > &EI)
template<typename Vector2D>
Orientation	incircle (const Eigen::MatrixBase< Vector2D > &pa, const Eigen::MatrixBase< Vector2D > &pb, const Eigen::MatrixBase< Vector2D > &pc, const Eigen::MatrixBase< Vector2D > &pd)
	Decide whether a point is inside/outside/on a circle.
template<typename Vector3D>
Orientation	insphere (const Eigen::MatrixBase< Vector3D > &pa, const Eigen::MatrixBase< Vector3D > &pb, const Eigen::MatrixBase< Vector3D > &pc, const Eigen::MatrixBase< Vector3D > &pd, const Eigen::MatrixBase< Vector3D > &pe)
	Decide whether a point is inside/outside/on a sphere.
template<typename DerivedV, typename DerivedF>
void	lexicographic_triangulation (const Eigen::MatrixBase< DerivedV > &V, Eigen::PlainObjectBase< DerivedF > &F)
	Given a set of points in 2D, return a lexicographic triangulation of these points using predicates.
template<typename Derivedpa, typename Derivedpb, typename Derivedpc>
Orientation	orient2d (const Eigen::MatrixBase< Derivedpa > &pa, const Eigen::MatrixBase< Derivedpb > &pb, const Eigen::MatrixBase< Derivedpc > &pc)
	Compute the orientation of the triangle formed by pa, pb, pc.
template<typename DerivedA, typename DerivedB, typename DerivedC, typename DerivedR>
void	orient2d (const Eigen::MatrixBase< DerivedA > &A, const Eigen::MatrixBase< DerivedB > &B, const Eigen::MatrixBase< DerivedC > &C, Eigen::PlainObjectBase< DerivedR > &R)
	Compute the orientation of the tetrahedron formed by each 4-tuple of points.
template<typename Vector3D>
Orientation	orient3d (const Eigen::MatrixBase< Vector3D > &pa, const Eigen::MatrixBase< Vector3D > &pb, const Eigen::MatrixBase< Vector3D > &pc, const Eigen::MatrixBase< Vector3D > &pd)
	Compute the orientation of the tetrahedron formed by pa, pb, pc, pd.
template<typename DerivedA, typename DerivedB, typename DerivedC, typename DerivedD, typename DerivedR>
void	orient3d (const Eigen::MatrixBase< DerivedA > &A, const Eigen::MatrixBase< DerivedB > &B, const Eigen::MatrixBase< DerivedC > &C, const Eigen::MatrixBase< DerivedD > &D, Eigen::PlainObjectBase< DerivedR > &R)
	Compute the orientation of the tetrahedron formed by each 4-tuple of points.
template<typename Derivedq, typename Deriveda, typename Derivedb, typename Derivedc, typename Derivedd>
Orientation	point_in_convex_hull (const Eigen::MatrixBase< Derivedq > &q, const Eigen::MatrixBase< Deriveda > &a, const Eigen::MatrixBase< Derivedb > &b, const Eigen::MatrixBase< Derivedc > &c, const Eigen::MatrixBase< Derivedd > &d)
	Determine if the 2D point q is inside, outside, or on the boundary of the convex hull of the 2D points a,b,c,d.
template<typename DerivedP, typename DerivedQ>
bool	point_inside_convex_polygon (const Eigen::MatrixBase< DerivedP > &P, const Eigen::MatrixBase< DerivedQ > &q)
	check whether 2d point lies inside 2d convex polygon
template<typename DerivedV, typename DerivedI, typename DerivedC, typename DerivedF, typename DerivedJ>
void	polygons_to_triangles (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedI > &I, const Eigen::MatrixBase< DerivedC > &C, Eigen::PlainObjectBase< DerivedF > &F, Eigen::PlainObjectBase< DerivedJ > &J)
	Given a polygon mesh, trivially triangulate each polygon with a fan.
template<typename DerivedP>
bool	segment_segment_intersect (const Eigen::MatrixBase< DerivedP > &A, const Eigen::MatrixBase< DerivedP > &B, const Eigen::MatrixBase< DerivedP > &C, const Eigen::MatrixBase< DerivedP > &D)
	Given two segments in 2d test whether they intersect each other using predicates orient2d.
template<typename DerivedP, typename DerivedC, typename DerivedB, typename Derivedleaf, typename DerivedQ, typename DerivedW>
void	spline_winding_number (const Eigen::MatrixBase< DerivedP > &P, const Eigen::MatrixBase< DerivedC > &C, const Eigen::MatrixBase< DerivedB > &B1, const Eigen::MatrixBase< DerivedB > &B2, const Eigen::MatrixBase< Derivedleaf > &leaf, const Eigen::MatrixBase< DerivedQ > &Q, Eigen::PlainObjectBase< DerivedW > &W)
	Computes the (generalized) winding number of a spline of cubic Bézier curves around a set of query points.
template<typename Vector3D>
bool	triangle_triangle_intersect (const Vector3D &a1, const Vector3D &a2, const Vector3D &a3, const Vector3D &b1, const Vector3D &b2, const Vector3D &b3, bool &coplanar)
	Triangle-triangle intersection test using exact predicates.

Function Documentation

cubic_winding_number()

template<typename DerivedC, typename Derivedq>

DerivedC::Scalar igl::predicates::cubic_winding_number	(	const Eigen::MatrixBase< DerivedC > &	C,
		const Eigen::MatrixBase< Derivedq > &	q )

Computes the (generalized) winding number of a cubic Bézier curve around a query.

This implementation is similar to "Robust Containment Queries Over Collections of Rational Parametric Curves via Generalized Winding Numbers" [Spainhour et al. 2024].

Parameters

[in]	C	4 by dimensions matrix of control points for a cubic Bézier curve
[in]	q	1 by dimensions query point

delaunay_triangulation()

template<typename DerivedV, typename DerivedF>

void igl::predicates::delaunay_triangulation	(	const Eigen::MatrixBase< DerivedV > &	V,
		Eigen::PlainObjectBase< DerivedF > &	F )

Given a set of points in 2D, return a Delaunay triangulation of these points using predicates.

Parameters

[in]	V	#V by 2 list of vertex positions
[out]	F	#F by 3 of faces in Delaunay triangulation.

ear_clipping() [1/2]

template<typename DerivedP, typename DerivedRT, typename DerivedF, typename DerivedI>

void igl::predicates::ear_clipping	(	const Eigen::MatrixBase< DerivedP > &	P,
		const Eigen::MatrixBase< DerivedRT > &	RT,
		Eigen::PlainObjectBase< DerivedF > &	eF,
		Eigen::PlainObjectBase< DerivedI > &	I )

Implementation of ear clipping triangulation algorithm for a 2D polygon.

https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf If the polygon is simple and oriented counter-clockwise, all vertices will be clipped and the result mesh is (P,eF) Otherwise, the function will try to clip as many ears as possible.

Parameters

[in]	P	: n*2, size n 2D polygon
[in]	RT	n*1, preserved vertices (do not clip) marked as 1, otherwise 0
[out]	eF	clipped ears, in original index of P
[out]	I	: size #nP vector, maps index from nP to P, e.g. nP's ith vertex is origianlly I(i) in P

Precondition

To result in a proper mesh, P should be oriented counter-clockwise with no self-intersections.

Note

This implementation does not handle polygons with holes.

ear_clipping() [2/2]

template<typename DerivedP, typename DerivedF>

bool igl::predicates::ear_clipping	(	const Eigen::MatrixBase< DerivedP > &	P,
		Eigen::PlainObjectBase< DerivedF > &	eF )

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Reverses P if necessary. Orientation of output will match input

Returns

true if mesh is proper (should correspond to input being a simple polygon in either orientation), false otherwise.

exactinit()

void igl::predicates::exactinit

(

)

Initialize internal variable used by predciates.

Must be called before using exact predicates. It is safe to call this function from multiple threads.

include/igl/predicates/exactinit.h

find_intersections() [1/4]

template<typename DerivedV1, typename DerivedF1, typename DerivedV2, typename DerivedF2, typename DerivedIF, typename DerivedCP>

bool igl::predicates::find_intersections	(	const AABB< DerivedV1, 3 > &	tree1,
		const Eigen::MatrixBase< DerivedV1 > &	V1,
		const Eigen::MatrixBase< DerivedF1 > &	F1,
		const Eigen::MatrixBase< DerivedV2 > &	V2,
		const Eigen::MatrixBase< DerivedF2 > &	F2,
		const bool	first_only,
		Eigen::PlainObjectBase< DerivedIF > &	IF,
		Eigen::PlainObjectBase< DerivedCP > &	CP )

Identify triangles where two meshes interesect using AABBTree and igl::predicates::triangle_triangle_intersect.

Parameters

[in]	tree1	AABB tree for the first mesh
[in]	V1	#V1 by 3 list representing vertices on the first mesh
[in]	F1	#F1 by 3 list representing triangles on the first mesh
[in]	V2	#V2 by 3 list representing vertices on the second mesh
[in]	F2	#F2 by 3 list representing triangles on the second mesh
[out]	IF	#IF by 2 list of intersecting triangle pairs, so that F1(IF(i,0),:) intersects F2(IF(i,1),:)
[out]	CP	#IF list of whether the intersection is coplanar

See also

copyleft::cgal::intersect_other

find_intersections() [2/4]

template<typename DerivedV1, typename DerivedF1, typename DerivedV2, typename DerivedF2, typename DerivedIF, typename DerivedCP>

bool igl::predicates::find_intersections	(	const Eigen::MatrixBase< DerivedV1 > &	V1,
		const Eigen::MatrixBase< DerivedF1 > &	F1,
		const Eigen::MatrixBase< DerivedV2 > &	V2,
		const Eigen::MatrixBase< DerivedF2 > &	F2,
		const bool	first_only,
		Eigen::PlainObjectBase< DerivedIF > &	IF,
		Eigen::PlainObjectBase< DerivedCP > &	CP )

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Tree built internally.

find_intersections() [3/4]

template<typename DerivedV1, typename DerivedF1, typename DerivedV2, typename DerivedF2, typename DerivedIF, typename DerivedCP, typename DerivedEV, typename DerivedEE, typename DerivedEI>

bool igl::predicates::find_intersections	(	const Eigen::MatrixBase< DerivedV1 > &	V1,
		const Eigen::MatrixBase< DerivedF1 > &	F1,
		const Eigen::MatrixBase< DerivedV2 > &	V2,
		const Eigen::MatrixBase< DerivedF2 > &	F2,
		Eigen::PlainObjectBase< DerivedIF > &	IF,
		Eigen::PlainObjectBase< DerivedCP > &	CP,
		Eigen::PlainObjectBase< DerivedEV > &	EV,
		Eigen::PlainObjectBase< DerivedEE > &	EE,
		Eigen::PlainObjectBase< DerivedEI > &	EI )

Parameters

[out]	EV	#EV by 3 list of vertex positions of intersection segments
[out]	EE	#EE by 2 list of edge indices into EV
[out]	EI	#EI by 1 list of indices into rows IF indicating source of intersection.

find_intersections() [4/4]

template<typename DerivedV1, typename DerivedF1, typename DerivedV2, typename DerivedF2, typename DerivedIF, typename DerivedCP, typename DerivedEV, typename DerivedEE, typename DerivedEI>

bool igl::predicates::find_intersections	(	const igl::AABB< DerivedV1, 3 > &	tree1,
		const Eigen::MatrixBase< DerivedV1 > &	V1,
		const Eigen::MatrixBase< DerivedF1 > &	F1,
		const Eigen::MatrixBase< DerivedV2 > &	V2,
		const Eigen::MatrixBase< DerivedF2 > &	F2,
		Eigen::PlainObjectBase< DerivedIF > &	IF,
		Eigen::PlainObjectBase< DerivedCP > &	CP,
		Eigen::PlainObjectBase< DerivedEV > &	EV,
		Eigen::PlainObjectBase< DerivedEE > &	EE,
		Eigen::PlainObjectBase< DerivedEI > &	EI )

find_self_intersections() [1/2]

template<typename DerivedV, typename DerivedF, typename DerivedIF, typename DerivedCP>

bool igl::predicates::find_self_intersections	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedF > &	F,
		const bool	first_only,
		Eigen::PlainObjectBase< DerivedIF > &	IF,
		Eigen::PlainObjectBase< DerivedCP > &	CP )

Identify triangle-triangle interesections within the same mesh using AABBTree and igl::predicates::triangle_triangle_intersect.

Parameters

[in]	V	#V by 3 list representing vertices on the first mesh
[in]	F	#F by 3 list representing triangles on the first mesh
[out]	IF	#IF by 2 list of intersecting triangle pairs, so that F1(IF(i,0),:) intersects F2(IF(i,1),:)
[out]	CP	#IF list of whether the intersection is coplanar

See also

copyleft::cgal::SelfIntersectMesh

find_self_intersections() [2/2]

template<typename DerivedV, typename DerivedF, typename DerivedIF, typename DerivedCP, typename DerivedEV, typename DerivedEE, typename DerivedEI>

bool igl::predicates::find_self_intersections	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedF > &	F,
		Eigen::PlainObjectBase< DerivedIF > &	IF,
		Eigen::PlainObjectBase< DerivedCP > &	CP,
		Eigen::PlainObjectBase< DerivedEV > &	EV,
		Eigen::PlainObjectBase< DerivedEE > &	EE,
		Eigen::PlainObjectBase< DerivedEI > &	EI )

Parameters

[out]	EV	#EV by 3 list of vertex positions of intersection segments
[out]	EE	#EE by 2 list of edge indices into EV
[out]	EI	#EI by 1 list of indices into rows IF indicating source of intersection.

incircle()

template<typename Vector2D>

Orientation igl::predicates::incircle	(	const Eigen::MatrixBase< Vector2D > &	pa,
		const Eigen::MatrixBase< Vector2D > &	pb,
		const Eigen::MatrixBase< Vector2D > &	pc,
		const Eigen::MatrixBase< Vector2D > &	pd )

Decide whether a point is inside/outside/on a circle.

Parameters

[in]	pa	2D point on circle
[in]	pb	2D point on circle
[in]	pc	2D point on circle
[in]	pd	2D point query

Returns

INSIDE if pd is inside of the circle defined by pa, pb and pc. OUSIDE if pd is outside of the circle. COCIRCULAR pd is exactly on the circle.

include/igl/predicates/incircle.h

insphere()

template<typename Vector3D>

Orientation igl::predicates::insphere	(	const Eigen::MatrixBase< Vector3D > &	pa,
		const Eigen::MatrixBase< Vector3D > &	pb,
		const Eigen::MatrixBase< Vector3D > &	pc,
		const Eigen::MatrixBase< Vector3D > &	pd,
		const Eigen::MatrixBase< Vector3D > &	pe )

Decide whether a point is inside/outside/on a sphere.

Parameters

[in]	pa	2D point on sphere
[in]	pb	2D point on sphere
[in]	pc	2D point on sphere
[in]	pd	2D point on sphere
[in]	pe	2D point query

Returns

INSIDE if pe is inside of the sphere defined by pa, pb, pc and pd. OUSIDE if pe is outside of the sphere. COSPHERICAL pd is exactly on the sphere.

include/igl/predicates/insphere.h

lexicographic_triangulation()

template<typename DerivedV, typename DerivedF>

void igl::predicates::lexicographic_triangulation	(	const Eigen::MatrixBase< DerivedV > &	V,
		Eigen::PlainObjectBase< DerivedF > &	F )

Given a set of points in 2D, return a lexicographic triangulation of these points using predicates.

Parameters

[in]	V	#V by 2 list of vertex positions
[out]	F	#F by 3 of faces in Delaunay triangulation.

orient2d() [1/2]

template<typename Derivedpa, typename Derivedpb, typename Derivedpc>

Orientation igl::predicates::orient2d	(	const Eigen::MatrixBase< Derivedpa > &	pa,
		const Eigen::MatrixBase< Derivedpb > &	pb,
		const Eigen::MatrixBase< Derivedpc > &	pc )

Compute the orientation of the triangle formed by pa, pb, pc.

Parameters

[in]	pa	2D point on line
[in]	pb	2D point on line
[in]	pc	2D query point.

Returns

POSITIVE if pa, pb, pc are counterclockwise oriented. NEGATIVE if they are clockwise oriented. COLLINEAR if they are collinear.

include/igl/predicates/orient2d.h

orient2d() [2/2]

template<typename DerivedA, typename DerivedB, typename DerivedC, typename DerivedR>

void igl::predicates::orient2d	(	const Eigen::MatrixBase< DerivedA > &	A,
		const Eigen::MatrixBase< DerivedB > &	B,
		const Eigen::MatrixBase< DerivedC > &	C,
		Eigen::PlainObjectBase< DerivedR > &	R )

Compute the orientation of the tetrahedron formed by each 4-tuple of points.

Parameters

[in]	A	#P|1 by 3 matrix of 3D points
[in]	B	#P|1 by 3 matrix of 3D points
[in]	C	#P|1 by 3 matrix of 3D points
[out]	R	#P vector of orientations

orient3d() [1/2]

template<typename Vector3D>

Orientation igl::predicates::orient3d	(	const Eigen::MatrixBase< Vector3D > &	pa,
		const Eigen::MatrixBase< Vector3D > &	pb,
		const Eigen::MatrixBase< Vector3D > &	pc,
		const Eigen::MatrixBase< Vector3D > &	pd )

Compute the orientation of the tetrahedron formed by pa, pb, pc, pd.

Parameters

[in]	pa	3D point on plane
[in]	pb	3D point on plane
[in]	pc	3D point on plane
[in]	pd	3D query point

Returns

POSITIVE if pd is "below" the oriented plane formed by pa, pb and pc. NEGATIVE if pd is "above" the plane. COPLANAR if pd is on the plane.

include/igl/predicates/orient3d.h

orient3d() [2/2]

template<typename DerivedA, typename DerivedB, typename DerivedC, typename DerivedD, typename DerivedR>

void igl::predicates::orient3d	(	const Eigen::MatrixBase< DerivedA > &	A,
		const Eigen::MatrixBase< DerivedB > &	B,
		const Eigen::MatrixBase< DerivedC > &	C,
		const Eigen::MatrixBase< DerivedD > &	D,
		Eigen::PlainObjectBase< DerivedR > &	R )

Compute the orientation of the tetrahedron formed by each 4-tuple of points.

Parameters

[in]	A	#P|1 by 3 matrix of 3D points
[in]	B	#P|1 by 3 matrix of 3D points
[in]	C	#P|1 by 3 matrix of 3D points
[in]	D	#P|1 by 3 matrix of 3D points
[out]	R	#P vector of orientations

point_in_convex_hull()

template<typename Derivedq, typename Deriveda, typename Derivedb, typename Derivedc, typename Derivedd>

Orientation igl::predicates::point_in_convex_hull	(	const Eigen::MatrixBase< Derivedq > &	q,
		const Eigen::MatrixBase< Deriveda > &	a,
		const Eigen::MatrixBase< Derivedb > &	b,
		const Eigen::MatrixBase< Derivedc > &	c,
		const Eigen::MatrixBase< Derivedd > &	d )

Determine if the 2D point q is inside, outside, or on the boundary of the convex hull of the 2D points a,b,c,d.

The points a,b,c,d may be given in any order and the convex hull may be a point, segment, triangle or quadrilateral.

Parameters

[in]	q	2D query point
[in]	a	2D point possibly on the convex hull
[in]	b	2D point possibly on the convex hull
[in]	c	2D point possibly on the convex hull
[in]	d	2D point possibly on the convex hull

Returns

Returns +1 if q is inside the convex hull, -1 if outside, and 0 if on the boundary.

point_inside_convex_polygon()

template<typename DerivedP, typename DerivedQ>

bool igl::predicates::point_inside_convex_polygon	(	const Eigen::MatrixBase< DerivedP > &	P,
		const Eigen::MatrixBase< DerivedQ > &	q )

check whether 2d point lies inside 2d convex polygon

Parameters

[in]	P	n*2 polygon, n >= 3
[in]	q	2d query point

Returns

true if point is inside polygon

polygons_to_triangles()

template<typename DerivedV, typename DerivedI, typename DerivedC, typename DerivedF, typename DerivedJ>

void igl::predicates::polygons_to_triangles	(	const Eigen::MatrixBase< DerivedV > &	V,
		const Eigen::MatrixBase< DerivedI > &	I,
		const Eigen::MatrixBase< DerivedC > &	C,
		Eigen::PlainObjectBase< DerivedF > &	F,
		Eigen::PlainObjectBase< DerivedJ > &	J )

Given a polygon mesh, trivially triangulate each polygon with a fan.

This purely combinatorial triangulation will work well for convex/flat polygons and degrade otherwise.

Parameters

[in]	V	#V by dim list of vertex positions
[in]	I	#I vectorized list of polygon corner indices into rows of some matrix V
[in]	C	#polygons+1 list of cumulative polygon sizes so that C(i+1)-C(i) = size of the ith polygon, and so I(C(i)) through I(C(i+1)-1) are the indices of the ith polygon
[out]	F	#F by 3 list of triangle indices into rows of V
[out]	J	#F list of indices into 0:#P-1 of corresponding polygon

segment_segment_intersect()

template<typename DerivedP>

bool igl::predicates::segment_segment_intersect	(	const Eigen::MatrixBase< DerivedP > &	A,
		const Eigen::MatrixBase< DerivedP > &	B,
		const Eigen::MatrixBase< DerivedP > &	C,
		const Eigen::MatrixBase< DerivedP > &	D )

Given two segments in 2d test whether they intersect each other using predicates orient2d.

Parameters

[in]	A	1st endpoint of segment 1
[in]	B	2st endpoint of segment 1
[in]	C	1st endpoint of segment 2
[in]	D	2st endpoint of segment 2

Returns

true if they intersect

spline_winding_number()

template<typename DerivedP, typename DerivedC, typename DerivedB, typename Derivedleaf, typename DerivedQ, typename DerivedW>

void igl::predicates::spline_winding_number	(	const Eigen::MatrixBase< DerivedP > &	P,
		const Eigen::MatrixBase< DerivedC > &	C,
		const Eigen::MatrixBase< DerivedB > &	B1,
		const Eigen::MatrixBase< DerivedB > &	B2,
		const Eigen::MatrixBase< Derivedleaf > &	leaf,
		const Eigen::MatrixBase< DerivedQ > &	Q,
		Eigen::PlainObjectBase< DerivedW > &	W )

Computes the (generalized) winding number of a spline of cubic Bézier curves around a set of query points.

Parameters

[in]	q	1 by dim query point
[in]	P	#P by dim matrix of spline control points
[in]	C	#C by 4 matrix of indices into P defining the cubic Bézier curves making up the spline
[in]	B1	#B by dim matrix of AABB min box corners
[in]	B2	#B by dim matrix of AABB max box corners
[in]	leaf	#B by 1 matrix of AABB leaf node indices/flags
[in]	Q	#Q by dim matrix of query points
[out]	W	#Q by 1 matrix of winding numbers for each query point

See also

igl::cycodebase::box_cubic, igl::predicates::cubic_winding_number, igl::eytzinger_aabb, igl::cycodebase::spline_eytzinger_aabb

triangle_triangle_intersect()

template<typename Vector3D>

bool igl::predicates::triangle_triangle_intersect	(	const Vector3D &	a1,
		const Vector3D &	a2,
		const Vector3D &	a3,
		const Vector3D &	b1,
		const Vector3D &	b2,
		const Vector3D &	b3,
		bool &	coplanar )

Triangle-triangle intersection test using exact predicates.

Parameters

[in]	a1	First vertex of triangle A.
[in]	a2	Second vertex of triangle A.
[in]	a3	Third vertex of triangle A.
[in]	b1	First vertex of triangle B.
[in]	b2	Second vertex of triangle B.
[in]	b3	Third vertex of triangle B.
[out]	coplanar	True if the triangles are coplanar.

Returns

True if the triangles intersect.