Categories &

Functions List

Function Reference: geom.triangulate

drafting: T = geom.triangulate (P)
drafting: T = geom.triangulate (P, HOLES)
drafting: [T, V] = geom.triangulate (…)
drafting: [T, V, COVERAGE] = geom.triangulate (…)

Triangulate a polygon, optionally one with holes.

T = geom.triangulate (P) returns an M-by-3 matrix of vertex indices, one row per triangle, covering the interior of the polygon P.

T = geom.triangulate (P, HOLES) excludes the interiors of the polygons in HOLES, a cell array of N-by-2 vertex matrices. Each hole must lie inside P and the holes must not overlap one another; neither is checked.

[T, V] = geom.triangulate (…) returns the vertex list the indices refer to: P followed by each hole in turn.

[T, V, COVERAGE] = geom.triangulate (…) returns the fraction of the true area the triangles actually cover. Read it; see below.

The intended use is generating end caps for an extruded solid, where the profile carries a central bore and a ring of holes.

This is not a constrained triangulation, and the distinction matters. The triangles come from an unconstrained Delaunay triangulation of the vertices, filtered by testing whether each triangle’s centroid lies inside P and outside every hole. That construction cannot guarantee that the edges of P appear in the result, so at a strongly concave part of the boundary a sliver of the true area may go uncovered: a triangle bridging the concavity has its centroid outside and is discarded, and nothing replaces it.

The consequence is that a triangulated region can be slightly smaller than the polygon, never larger. Denser sampling of the boundary shrinks the shortfall, and COVERAGE measures it, so a caller that needs a guarantee can assert on a number rather than trust a description. For a printed prototype the shortfall is invisible well before it is zero; for anything dimensionally critical, a constrained triangulation is the right tool and this is not it.

See also: geom.signedarea, geom.selfintersects, geom.bbox

Source Code: geom.triangulate

Triangulating a plate with a bore and a ring of holes --- the end cap of an extruded solid. COVERAGE reports how much of the true area the triangles actually reach, so a caller can assert on a number rather than trust a description.

 a = linspace (0, 2*pi, 65)(1:64)';
 b = linspace (0, 2*pi, 33)(1:32)';
 outer = 40 * [cos(a), sin(a)];
 H = {10 * [cos(b), sin(b)]};
 for k = 1:5
   c = 26 * [cos(2*pi*(k-1)/5), sin(2*pi*(k-1)/5)];
   H{end+1} = c + 5 * [cos(b), sin(b)];
 endfor
 [T, V, COVERAGE] = geom.triangulate (outer, H);
 printf ('%d triangles covering %.4f of the area\n', rows (T), COVERAGE);
266 triangles covering 1.0000 of the area
 D = draw.Drawing ();
 for k = 1:rows (T)
   D = D.polyline (V(T(k,:),:), true);
 endfor
 plot (D);
 title ('an end cap triangulated around its bore and holes');
plotted figure