Circular arcs 4 - extrema

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.