Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
81.08%
120 / 148
66.67%
4 / 6
 CRAP
0.00%
0 / 1
PathLengthMeasure
81.08%
120 / 148
66.67%
4 / 6
 37.51
0.00%
0 / 1
 ofPathData
75.56%
68 / 90
0.00%
0 / 1
 27.44
 resolve
100.00%
1 / 1
100.00%
1 / 1
 2
 arcLength
76.92%
20 / 26
0.00%
0 / 1
 4.20
 cubicLength
100.00%
14 / 14
100.00%
1 / 1
 1
 quadraticLength
100.00%
10 / 10
100.00%
1 / 1
 1
 gauss
100.00%
7 / 7
100.00%
1 / 1
 2
1<?php
2
3declare(strict_types=1);
4
5namespace Phpdftk\SvgToPdf\Path;
6
7use Phpdftk\Svg\Path\ArcTo;
8use Phpdftk\Svg\Path\ClosePath;
9use Phpdftk\Svg\Path\CurveTo;
10use Phpdftk\Svg\Path\HorizontalLineTo;
11use Phpdftk\Svg\Path\LineTo;
12use Phpdftk\Svg\Path\MoveTo;
13use Phpdftk\Svg\Path\PathData;
14use Phpdftk\Svg\Path\QuadraticCurveTo;
15use Phpdftk\Svg\Path\SmoothCurveTo;
16use Phpdftk\Svg\Path\SmoothQuadraticCurveTo;
17use Phpdftk\Svg\Path\VerticalLineTo;
18
19/**
20 * Geometric length of a parsed `d` attribute, in user units.
21 *
22 * This is the denominator of the SVG 2 §9.6 `pathLength` scaling
23 * factor: the user agent's own computation of how long the path really
24 * is, against which the author's declared `pathLength` is calibrated.
25 *
26 * Two properties matter more than raw speed:
27 *
28 *  - **Exactness on the easy cases.** Straight segments measure as
29 *    their chord and a circular arc measures as `r·Δθ`, so a square
30 *    path is exactly `4w` and a circle exactly `2πr`. WPT's
31 *    `pathLength` reftests draw the test side as a shape and the
32 *    reference side as a hand-written path; the two must agree to
33 *    well under a device pixel after the dash phase has accumulated
34 *    around the whole outline.
35 *  - **Measuring the TRUE ellipse, not its Bézier approximation.** The
36 *    painter lowers an `A` command to cubics because PDF has no arc
37 *    operator, but a quarter-circle cubic is ~1.4·10⁻⁵ longer than the
38 *    quarter circle. Measuring the approximation would make
39 *    `<circle r="100">` and the equivalent `<path>` disagree.
40 *
41 * Bézier segments have no closed-form arc length, so they are
42 * integrated with 24-point Gauss–Legendre quadrature over the
43 * derivative magnitude. That is exact for the degenerate
44 * straight-line cubics authors write constantly, and converges far
45 * faster than chord subdivision on real curves.
46 */
47final class PathLengthMeasure
48{
49    /**
50     * Gauss–Legendre abscissae on [-1, 1] for n = 24, paired with
51     * their weights. Only the non-negative half is stored; the rule is
52     * symmetric, so each entry is evaluated at ±x.
53     *
54     * @var list<array{float, float}>
55     */
56    private const array GAUSS_HALF = [
57        [0.0640568928626056, 0.1279381953467522],
58        [0.1911188674736163, 0.1258374563468283],
59        [0.3150426796961634, 0.1216704729278034],
60        [0.4337935076260451, 0.1155056680537256],
61        [0.5454214713888396, 0.1074442701159656],
62        [0.6480936519369755, 0.0976186521041139],
63        [0.7401241915785544, 0.0861901615319533],
64        [0.8200019859739029, 0.0733464814110803],
65        [0.8864155270044011, 0.0592985849154368],
66        [0.9382745520027328, 0.0442774388174198],
67        [0.9747285559713095, 0.0285313886289337],
68        [0.9951872199970213, 0.0123412297999872],
69    ];
70
71    /** Below this, a coordinate delta is noise rather than geometry. */
72    private const float EPSILON = 1.0e-12;
73
74    public static function ofPathData(PathData $data): float
75    {
76        $total = 0.0;
77        // Current point, and the start of the current subpath (where a
78        // `Z` returns to). Also the previous curve's second control
79        // point, which the smooth (`S` / `T`) commands reflect.
80        $cx = $cy = 0.0;
81        $startX = $startY = 0.0;
82        $lastCubicControlX = $lastCubicControlY = null;
83        $lastQuadControlX = $lastQuadControlY = null;
84
85        foreach ($data->commands as $command) {
86            $isCubic = false;
87            $isQuad = false;
88
89            switch (true) {
90                case $command instanceof MoveTo:
91                    [$x, $y] = self::resolve($command->absolute, $command->x, $command->y, $cx, $cy);
92                    $cx = $startX = $x;
93                    $cy = $startY = $y;
94                    break;
95
96                case $command instanceof LineTo:
97                    [$x, $y] = self::resolve($command->absolute, $command->x, $command->y, $cx, $cy);
98                    $total += hypot($x - $cx, $y - $cy);
99                    $cx = $x;
100                    $cy = $y;
101                    break;
102
103                case $command instanceof HorizontalLineTo:
104                    $x = $command->absolute ? $command->x : $cx + $command->x;
105                    $total += abs($x - $cx);
106                    $cx = $x;
107                    break;
108
109                case $command instanceof VerticalLineTo:
110                    $y = $command->absolute ? $command->y : $cy + $command->y;
111                    $total += abs($y - $cy);
112                    $cy = $y;
113                    break;
114
115                case $command instanceof CurveTo:
116                    [$x1, $y1] = self::resolve($command->absolute, $command->x1, $command->y1, $cx, $cy);
117                    [$x2, $y2] = self::resolve($command->absolute, $command->x2, $command->y2, $cx, $cy);
118                    [$x, $y] = self::resolve($command->absolute, $command->x, $command->y, $cx, $cy);
119                    $total += self::cubicLength($cx, $cy, $x1, $y1, $x2, $y2, $x, $y);
120                    $lastCubicControlX = $x2;
121                    $lastCubicControlY = $y2;
122                    $cx = $x;
123                    $cy = $y;
124                    $isCubic = true;
125                    break;
126
127                case $command instanceof SmoothCurveTo:
128                    $x1 = $lastCubicControlX === null ? $cx : 2.0 * $cx - $lastCubicControlX;
129                    $y1 = $lastCubicControlY === null ? $cy : 2.0 * $cy - $lastCubicControlY;
130                    [$x2, $y2] = self::resolve($command->absolute, $command->x2, $command->y2, $cx, $cy);
131                    [$x, $y] = self::resolve($command->absolute, $command->x, $command->y, $cx, $cy);
132                    $total += self::cubicLength($cx, $cy, $x1, $y1, $x2, $y2, $x, $y);
133                    $lastCubicControlX = $x2;
134                    $lastCubicControlY = $y2;
135                    $cx = $x;
136                    $cy = $y;
137                    $isCubic = true;
138                    break;
139
140                case $command instanceof QuadraticCurveTo:
141                    [$x1, $y1] = self::resolve($command->absolute, $command->x1, $command->y1, $cx, $cy);
142                    [$x, $y] = self::resolve($command->absolute, $command->x, $command->y, $cx, $cy);
143                    $total += self::quadraticLength($cx, $cy, $x1, $y1, $x, $y);
144                    $lastQuadControlX = $x1;
145                    $lastQuadControlY = $y1;
146                    $cx = $x;
147                    $cy = $y;
148                    $isQuad = true;
149                    break;
150
151                case $command instanceof SmoothQuadraticCurveTo:
152                    $x1 = $lastQuadControlX === null ? $cx : 2.0 * $cx - $lastQuadControlX;
153                    $y1 = $lastQuadControlY === null ? $cy : 2.0 * $cy - $lastQuadControlY;
154                    [$x, $y] = self::resolve($command->absolute, $command->x, $command->y, $cx, $cy);
155                    $total += self::quadraticLength($cx, $cy, $x1, $y1, $x, $y);
156                    $lastQuadControlX = $x1;
157                    $lastQuadControlY = $y1;
158                    $cx = $x;
159                    $cy = $y;
160                    $isQuad = true;
161                    break;
162
163                case $command instanceof ArcTo:
164                    [$x, $y] = self::resolve($command->absolute, $command->x, $command->y, $cx, $cy);
165                    $total += self::arcLength($command, $cx, $cy, $x, $y);
166                    $cx = $x;
167                    $cy = $y;
168                    break;
169
170                case $command instanceof ClosePath:
171                    $total += hypot($startX - $cx, $startY - $cy);
172                    $cx = $startX;
173                    $cy = $startY;
174                    break;
175
176                default:
177                    // Third-party `PathCommand` implementations are not
178                    // part of the spec; the painter no-ops on them, so
179                    // they contribute no length either.
180                    break;
181            }
182
183            // Only a cubic seeds `S`'s reflection and only a quadratic
184            // seeds `T`'s — SVG 2 §9.3.6/§9.3.7. Anything else clears
185            // the respective anchor so the next smooth command starts
186            // from the current point.
187            if (!$isCubic) {
188                $lastCubicControlX = $lastCubicControlY = null;
189            }
190            if (!$isQuad) {
191                $lastQuadControlX = $lastQuadControlY = null;
192            }
193        }
194
195        return $total;
196    }
197
198    /** @return array{float, float} */
199    private static function resolve(
200        bool $absolute,
201        float $x,
202        float $y,
203        float $cx,
204        float $cy,
205    ): array {
206        return $absolute ? [$x, $y] : [$cx + $x, $cy + $y];
207    }
208
209    /**
210     * Arc length of one `A` command, measured on the TRUE ellipse.
211     *
212     * A zero radius (or a zero-length chord) is not an arc at all: SVG
213     * 2 §9.5.1 renders it as a straight line to the endpoint, and the
214     * painter does the same, so it measures as the chord.
215     */
216    private static function arcLength(
217        ArcTo $arc,
218        float $fromX,
219        float $fromY,
220        float $toX,
221        float $toY,
222    ): float {
223        $centre = ArcToCubic::centreParameters(
224            $fromX,
225            $fromY,
226            $arc->rx,
227            $arc->ry,
228            $arc->xAxisRotation,
229            $arc->largeArc,
230            $arc->sweep,
231            $toX,
232            $toY,
233        );
234        if ($centre === null) {
235            return hypot($toX - $fromX, $toY - $fromY);
236        }
237        $rx = $centre['rx'];
238        $ry = $centre['ry'];
239        $theta1 = $centre['theta1'];
240        $delta = $centre['delta'];
241        if (abs($delta) < self::EPSILON) {
242            return 0.0;
243        }
244        // A circular arc integrates in closed form; skip the quadrature
245        // so `<circle>` and an `A`-command circle agree bit for bit.
246        if (abs($rx - $ry) < self::EPSILON) {
247            return $rx * abs($delta);
248        }
249        // |dP/dθ| on the ellipse. The x-axis rotation φ is a rigid
250        // rotation, so it leaves arc length alone and drops out.
251        return self::gauss(
252            static fn(float $t): float => hypot($rx * sin($t), $ry * cos($t)),
253            $theta1,
254            $theta1 + $delta,
255        );
256    }
257
258    private static function cubicLength(
259        float $x0,
260        float $y0,
261        float $x1,
262        float $y1,
263        float $x2,
264        float $y2,
265        float $x3,
266        float $y3,
267    ): float {
268        return self::gauss(
269            static function (float $t) use ($x0, $y0, $x1, $y1, $x2, $y2, $x3, $y3): float {
270                $u = 1.0 - $t;
271                $dx = 3.0 * $u * $u * ($x1 - $x0)
272                    + 6.0 * $u * $t * ($x2 - $x1)
273                    + 3.0 * $t * $t * ($x3 - $x2);
274                $dy = 3.0 * $u * $u * ($y1 - $y0)
275                    + 6.0 * $u * $t * ($y2 - $y1)
276                    + 3.0 * $t * $t * ($y3 - $y2);
277                return hypot($dx, $dy);
278            },
279            0.0,
280            1.0,
281        );
282    }
283
284    private static function quadraticLength(
285        float $x0,
286        float $y0,
287        float $x1,
288        float $y1,
289        float $x2,
290        float $y2,
291    ): float {
292        return self::gauss(
293            static function (float $t) use ($x0, $y0, $x1, $y1, $x2, $y2): float {
294                $u = 1.0 - $t;
295                $dx = 2.0 * $u * ($x1 - $x0) + 2.0 * $t * ($x2 - $x1);
296                $dy = 2.0 * $u * ($y1 - $y0) + 2.0 * $t * ($y2 - $y1);
297                return hypot($dx, $dy);
298            },
299            0.0,
300            1.0,
301        );
302    }
303
304    /**
305     * 24-point Gauss–Legendre quadrature of `$f` over `[$a, $b]`.
306     *
307     * @param callable(float): float $f
308     */
309    private static function gauss(callable $f, float $a, float $b): float
310    {
311        $half = ($b - $a) / 2.0;
312        $mid = ($a + $b) / 2.0;
313        $sum = 0.0;
314        foreach (self::GAUSS_HALF as [$x, $w]) {
315            $offset = $half * $x;
316            $sum += $w * ($f($mid - $offset) + $f($mid + $offset));
317        }
318        return abs($half) * $sum;
319    }
320}