TL;DR

Let’s take a look at the bounding box for arcs of ellipses, at the very last!

In the previous post Ellipses (for SVG): transformation implementation we saw the implementation of a function to turn the representation of an arc of ellipse inside a SVG path (based on the two endpoints and other parameters) to a more tractable representation (the parametric representation, in particular) for finding the bounding box.

So, we have a representation (from Ellipses (for SVG): parameter and angles):

$x(t) = C_x + cos(\phi) \cdot r_x \cdot cos(t) - sin(\phi) \cdot r_y \cdot sin(t) \\ y(t) = C_y + sin(\phi) \cdot r_x \cdot cos(t) + cos(\phi) \cdot r_y \cdot sin(t)$

and we also have all the needed parameters, including a contiguous range for the parameter $t$ … we can move on towards the bounding box!

Maxima and minima

As before with Bézier curves (see SVG path bounding box: quadratic Bézier curves and SVG path bounding box: cubic Bézier curves) we can treat the two axes independently and use the derivatives to find the candidate values of $t$ that might yield us maxima or minima in the required interval.

The two derivatives are:

$\dot{x}(t) = - cos(\phi) \cdot r_x \cdot sin(t) - sin(\phi) \cdot r_y \cdot cos(t) \\ \dot{y}(t) = - sin(\phi) \cdot r_x \cdot sin(t) + cos(\phi) \cdot r_y \cdot cos(t)$

Finding the zero for the $X$ coordinate means finding $t$ such that:

$cos(\phi) \cdot r_x \cdot sin(t) = - sin(\phi) \cdot r_y \cdot cos(t)$

We can find this with the help of atan2:

$t_{x,1} = atan2(-sin(\phi) \cdot r_y, cos(\phi) \cdot r_x)$

Note that there is also another candidate that is spaced $\pi$ apart:

$t_{x,2} = t_{x,1} + \pi$

Both these two candidates also have equivalents that are spaced by multiples of $2\pi$ , of course. We should find the two equivalents that are closer to $t_{begin}$ and greater than it, then check if the actually fall in the $[t_{begin}, t_{end}]$ interval; if any of them does, then it must be considered for the bounding box evaluation.

Similar equations and reasoning can be done for the $Y$ axis, of course.

Implementation

On to the implementation:

sub ellipse_bb ($C, $R, $phi, $t_start, $t_end) {
  my %retval = (min => {}, max => {});
  my $pi2 = 2 * PI;
  $_ -= floor($_ / $pi2) * $pi2 for ($t_start, $t_end);
  $t_end += $pi2 if $t_end < $t_start;

  # align to a sane range, might be improved...
  my ($Rx, $Ry, $cosp, $sinp) = ($R->{x}, $R->{y}, cos($phi), sin($phi));
  for my $axis (qw< x y >) {
     my @candidates = ($t_start, $t_end);
     my $theta = atan2(-$Ry * $sinp, $Rx * $cosp);
     for (1 .. 2) {
        $theta -= floor($theta / $pi2) * $pi2; # normale
        $theta += $pi2 if $theta < $t_start;  # try to fit in range
        push @candidates, $theta if $theta < $t_end;
        $theta += PI; # prepare for 2nd iteration
     }

     for my $theta (@candidates) {
        my $v = $C->{$axis} +
           $Rx * $cosp * cos($theta) +
           $Ry * $sinp * sin($theta);
        $retval{min}{$axis} //= $retval{max}{$axis} //= $v;
        if    ($v < $retval{min}{$axis}) { $retval{min}{$axis} = $v }
        elsif ($v > $retval{max}{$axis}) { $retval{max}{$axis} = $v }
     }

     ($cosp, $sinp) = (-$sinp, $cosp); # prepare for y-iteration
  }
  return \%retval;
}

Lines 3 through 5 re-normalize the interval putting $t_{begin}$ inside $[0, 2\pi[$ and $t_{end}$ immediately after it.

The two axes are treated separately (line 9), just like we did for Bézier curves. Our candidates for finding the minima and maxima start with our endpoints (line 10), then we calculate $t_1$ using atan2 (line 11) and establish whether it or its $\pi$ -spaced sibling fall in the interval (lines 12 through 17).

Lines 19 through 26 take care to evaluate the parametric function in the candidate values for $t$ and update the bounding box accordingly.

Line 28 is… peculiar. To reuse the same exact formulas of the $X$ axis also for the $Y$ axis, it’s sufficient to do the indicating swapping… cool, this saves us a lot of cut-and-paste!

Conclusions

We now have the last missing piece in our quest for the bounding box of a SVG path… it’s been funny, hasn’t it?!? 🤓

ETOOBUSY 🚀 minimal blogging for the impatient

SVG path bounding box: arcs of ellipses

Maxima and minima

Implementation

Conclusions