Categories &

Functions List

Function Reference: geom.simplify

drafting: Q = geom.simplify (P, TOL)
drafting: [Q, KEPT] = geom.simplify (P, TOL)

Remove the points of a curve that carry no shape, within a tolerance.

Q = geom.simplify (P, TOL) returns the polyline P with points dropped wherever doing so moves the curve by no more than TOL. The first and last points are always kept.

[Q, KEPT] = geom.simplify (…) also returns the indices of the rows of P that survived, so a caller can carry along anything it had attached to those points.

What the tolerance guarantees

No point of the original curve ends up further than TOL from the simplified one. That is a statement about the whole curve, not about the points removed, and it is what makes the tolerance safe to set from a manufacturing figure: simplifying a cut profile to a tenth of the machine’s own tolerance cannot move the part outside it.

The algorithm is Douglas and Peucker’s: the segment from first point to last is taken, the original point furthest from it found, and if that distance exceeds TOL the curve is split there and each half treated the same way. Points survive because they carry shape, not because of where they fall in the list.

Simplifying, not resampling

Every point of Q is a point of P; nothing is interpolated and no corner is cut, which is what distinguishes this from geom.resample. A polygon may be simplified without losing its vertices, since a corner is exactly the sort of point the algorithm keeps.

The saving can be large. A curve sampled to a chordal tolerance far finer than the drawing needs — as a cycloidal profile at a micron is, for a part made to a hundredth — carries points that no reader or machine can use, and every one of them reaches the file.

See also: geom.resample, geom.arclength, geom.curvesample

Source Code: geom.simplify

Simplifying removes the points that carry no shape, guaranteeing that no point of the original ends further than the tolerance from the result. Every point kept is a point of the original: nothing is interpolated.

 t = linspace (0, 2*pi, 721)(1:720)';
 P = (30 + 4 * cos (8 * t)) .* [cos(t), sin(t)];
 Q = geom.simplify (P, 0.05);
 printf ('%d points -> %d, within 0.05 mm\n', rows (P), rows (Q));
720 points -> 145, within 0.05 mm
 D = draw.Drawing ().polyline (P, true);
 D.Colour = 'red';
 for k = 1:rows (Q)
   D = D.circle (Q(k,:), 0.7);
 endfor
 plot (D);
 title ('the points that survive are the ones carrying shape');
plotted figure

The saving matters: a profile sampled far finer than the drawing needs carries points no reader or machine can use, and every one reaches the file.

 t = linspace (0, 2*pi, 4001)(1:4000)';
 P = (30 + 4 * cos (9 * t)) .* [cos(t), sin(t)];
 for tol = [0.001, 0.01, 0.1]
   printf ('within %5.3f mm: %5d of %d points kept\n', tol, ...
           rows (geom.simplify (P, tol)), rows (P));
 endfor
within 0.001 mm:  1265 of 4000 points kept
within 0.010 mm:   393 of 4000 points kept
within 0.100 mm:   127 of 4000 points kept