igl.predicates

Python API reference for igl.predicates.

cubic_winding_number

cubic_winding_number(C: float64[m, n], q: float64[2]) -> float

Exact winding number of a 2D cubic Bézier curve about a query point.

Parameters

• C — 4 by 2 matrix of control points for the cubic Bézier curve
• q — 2D query point

Returns

• the (fractional) winding number of the curve about q

delaunay_triangulation

delaunay_triangulation(V: float64[m, n]) -> int32[m, n]

Compute a Delaunay triangulation of a 2D point set using exact predicates.

Parameters

• V — #V by 2 list of 2D vertex positions

Returns

• F #F by 3 list of triangle indices into V.

ear_clipping

C++ reference

ear_clipping(P: float64[m, n]) -> tuple[bool, int32[m, n]]

Ear-clipping triangulation of a 2D polygon.

Reverses P if necessary so output orientation matches input.

Parameters

• P — #P by 2 list of 2D polygon vertices (CCW for proper mesh)

Returns

• (ok, eF) where ok is true if mesh is proper (input is a simple polygon) and eF is #eF by 3 list of triangle indices into P.

ear_clipping(P: float64[m, n], RT: int64[m, n]) -> tuple[int32[m, n], int64[m, n]]

Ear-clipping triangulation with reserved (non-clippable) vertices.

Parameters

• P — #P by 2 list of 2D polygon vertices
• RT — #P list, vertices marked 1 are preserved (not clipped)

Returns

• (eF, I) where eF is the clipped ears (original indices into P) and I maps indices of the remaining polygon to original P indices.

find_intersections

find_intersections(V1: float64[m, n], F1: int64[m, n], V2: float64[m, n], F2: int64[m, n], first_only: bool = False) -> tuple[bool, int64[m, n], int64[m, n]]

Find intersecting triangle pairs between two meshes.

Uses AABB tree and exact predicates.

Parameters

• V1 — #V1 by 3 vertex positions of first mesh
• F1 — #F1 by 3 triangle indices of first mesh
• V2 — #V2 by 3 vertex positions of second mesh
• F2 — #F2 by 3 triangle indices of second mesh
• first_only — stop after finding the first intersection

Returns

• (found, IF, CP) where found is true if any intersections exist, IF is #IF by 2 list of intersecting face index pairs (into F1, F2), CP is #IF list of whether each intersection is coplanar.

find_self_intersections

find_self_intersections(V: float64[m, n], F: int64[m, n], first_only: bool = False) -> tuple[bool, int64[m, n], int64[m, n]]

Find self-intersecting triangle pairs within a mesh.

Uses AABB tree and exact predicates.

Parameters

• V — #V by 3 vertex positions
• F — #F by 3 triangle indices
• first_only — stop after finding the first intersection

Returns

• (found, IF, CP) where found is true if any self-intersections exist, IF is #IF by 2 list of intersecting face index pairs, CP is #IF list of whether each intersection is coplanar.

incircle

incircle(pa: float64[2], pb: float64[2], pc: float64[2], pd: float64[2]) -> Orientation

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

Uses exact arithmetic (Shewchuk predicates).

Parameters

• pa — 2D point on circle
• pb — 2D point on circle
• pc — 2D point on circle
• pd — 2D query point

Returns

• INSIDE if pd is inside the circle defined by pa,pb,pc, OUTSIDE if outside, COCIRCULAR if exactly on the circle.

insphere

insphere(pa: float64[3], pb: float64[3], pc: float64[3], pd: float64[3], pe: float64[3]) -> Orientation

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

Uses exact arithmetic (Shewchuk predicates).

Parameters

• pa — 3D point on sphere
• pb — 3D point on sphere
• pc — 3D point on sphere
• pd — 3D point on sphere
• pe — 3D query point

Returns

• INSIDE if pe is inside the sphere defined by pa,pb,pc,pd, OUTSIDE if outside, COSPHERICAL if exactly on the sphere.

lexicographic_triangulation

lexicographic_triangulation(V: float64[m, n]) -> int32[m, n]

Compute a lexicographic triangulation of a 2D point set using exact predicates.

Parameters

• V — #V by 2 list of 2D vertex positions

Returns

• F #F by 3 list of triangle indices into V.

orient2d

orient2d(pa: float64[2], pb: float64[2], pc: float64[2]) -> Orientation

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

Uses exact arithmetic (Shewchuk predicates).

Parameters

• pa — 2D point
• pb — 2D point
• pc — 2D point

Returns

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

orient3d

orient3d(pa: float64[3], pb: float64[3], pc: float64[3], pd: float64[3]) -> Orientation

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

Uses exact arithmetic (Shewchuk predicates).

Parameters

• pa — 3D point
• pb — 3D point
• pc — 3D point
• pd — 3D query point

Returns

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

orient3d(A: float64[m, n], B: float64[m, n], C: float64[m, n], D: float64[m, n]) -> int32[m]

Vectorized orient3d: compute orientation for each row-tuple (A[i], B[i], C[i], D[i]).

Parameters

• A — #P by 3 matrix of 3D points
• B — #P by 3 matrix of 3D points
• C — #P by 3 matrix of 3D points
• D — #P by 3 matrix of 3D points

Returns

• #P vector of orientation values (+1, -1, or 0)

point_in_convex_hull

point_in_convex_hull(q: float64[2], a: float64[2], b: float64[2], c: float64[2], d: float64[2]) -> Orientation

Test whether a 2D point lies in the convex hull of four points using exact predicates.

Parameters

• q — 2D query point
• a — 2D point
• b — 2D point
• c — 2D point
• d — 2D point

Returns

• POSITIVE if q is strictly inside the convex hull of {a,b,c,d}, NEGATIVE if strictly outside, COLLINEAR if on the boundary.

point_inside_convex_polygon

C++ reference

point_inside_convex_polygon(P: float64[m, 2], q: float64[2]) -> bool

Check whether a 2D point lies inside a 2D convex polygon.

Parameters

• P — #P by 2 list of polygon vertices (n >= 3)
• q — 2D query point

Returns

• true if q is inside P.

polygons_to_triangles

polygons_to_triangles(V: float64[m, n], I: int64[m], C: int64[m]) -> tuple[int32[m, n], int64[m]]

Triangulate each polygon of a polygon mesh with a fan.

Parameters

• V — #V by dim vertex positions (used for orientation in 3D)
• I — #I list of polygon corner indices into rows of V
• C — #polygons+1 cumulative polygon sizes (C[i+1]-C[i] = size of polygon i)

Returns

• (F, J) where F is #F by 3 list of triangle indices and J is #F list of source polygon indices.

segment_segment_intersect

segment_segment_intersect(A: float64[2], B: float64[2], C: float64[2], D: float64[2]) -> bool

Test whether two 2D segments intersect using exact orient2d predicates.

Parameters

• A — 1st endpoint of segment 1
• B — 2nd endpoint of segment 1
• C — 1st endpoint of segment 2
• D — 2nd endpoint of segment 2

Returns

• true if the segments intersect.

spline_winding_number

spline_winding_number(P: float64[m, n], C: int64[m, n], B1: float64[m, n], B2: float64[m, n], leaf: int64[m], Q: float64[m, n]) -> float64[m]

Winding number of a closed spline of cubic Bézier curves about query points.

Uses the Eytzinger-layout AABB tree produced by igl.cycodebase.spline_eytzinger_aabb for acceleration.

Parameters

• P — #P by 2 matrix of spline control points
• C — #C by 4 matrix of indices into P defining the cubic Bézier curves
• B1 — #B by 2 matrix of AABB min box corners
• B2 — #B by 2 matrix of AABB max box corners
• leaf — #B vector of AABB leaf node indices/flags
• Q — #Q by 2 matrix of query points

Returns

• W #Q vector of winding numbers about each query point

triangle_triangle_intersect

triangle_triangle_intersect(a1: float64[3], a2: float64[3], a3: float64[3], b1: float64[3], b2: float64[3], b3: float64[3]) -> tuple[bool, bool]

Test whether two 3D triangles intersect using exact predicates.

Parameters

• a1 — 1st vertex of triangle A
• a2 — 2nd vertex of triangle A
• a3 — 3rd vertex of triangle A
• b1 — 1st vertex of triangle B
• b2 — 2nd vertex of triangle B
• b3 — 3rd vertex of triangle B

Returns

• (intersects, coplanar) where intersects is true if the triangles intersect, and coplanar is true if they are coplanar.

Orientation