Victor Liu

One basic operation upon shapes is to compute bounding regions. For a shape made up of pieces of simple curves, this amounts to computing directional extrema on the curve. In other words, given a curve and a direction vector $d$ (without loss of generality we assume it is normalized), determine the point that maximizes the dot product of $d$ and the vector from the origin to the point. In addition to the point, we typically would also like to know the parameter value of the extremal point.

The point E is the extremum of the arc in the direction d.

For a circular arc, there are two cases: the extremum may be an endpoint, or it may be interior to the arc. For any parameter value $s$, we shall call the aforementioned dot product $P(s) = \left[p(s)-0\right]\cdot d$, where $0$ is the origin. Clearly, it is trivial to compute $P(0)$ and $P(1)$ and we shall compare the value at any other interior points against the extremal point.

For $g$ sufficiently far from zero, one may compute the center of the circle $C$ and its radius $r$, and any interior extremum must be at $E = C+rd$. The only task is determining if $E$ lies on the arc. For the smaller half of a circle when $g<1$, $E$ lies on the arc if $(A-C)\times(E-C) > 0$ and $(E-C)\times(B-C)> 0$. Otherwise for $g>1$, then we require that then "and" is replaced by "or". The parameter value can be obtained by any parameterization method discussed in the previous article.

For $g$ near zero, the situation is slightly trickier. From the algorithm for evaluation, differentiation provides a method to compute the tangents to the arc, particularly at the endpoints. Therefore, the outward normals to the arc are readily computable, and let us denote them by $n_A$ and $n_B$. Since $g$ is small in magnitude, we can determine inclusion of the extremum within the arc again using cross products. We simply require than $n_A \times d > 0$ and $d \times n_B > 0$. The harder task is determining the point itself, and it is perhaps easiest to compute the parameter value directly through trigonometry:

$$ s = \frac{\tan^{-1}\frac{n_A\times d}{n_A\cdot d}}{2\theta} = \frac{\tan^{-1}\frac{n_A\times d}{n_A\cdot d}}{4\tan^{-1}g} \in [0,1] $$

In implementation, there are a few additional annoying details, such as correctly handling the sign of $g$, and ensuring that the arctangents are computed on the right branch, &c.