How to effectively check whether a path is inside a series of bounding boxes?

Question

Given a series of interconnected rectangular bounding boxes, and a path that is a described by a polynomial (or a polynomial spline), how can I check whether the path is entirely inside the bounding boxes, precisely? (as shown in the below figure)

Answer 1

Let the curves in the spline be given by parametric expressions $(x(t),y(t))$ with $0\le t\le1$ as is common in computer graphics.

Consider each pair of curve and rectangle in turn. For the four edges of that rectangle, determine all $t$-values on the curve that correspond to intersections, of which there may be none. This is relatively simple to accomplish by rotating the edge onto an axis and finding roots of the component polynomials of the resulting curve, as detailed for example here.

Then determine if $t=0$ on the curve is in the rectangle; from there mark the found intersection $t$-parameters as entering or exiting the rectangle alternately. This gives a subset of $[0,1]$ corresponding to that part of the curve within the rectangle. For a given curve, take the union of said subsets arising from its pairings with all rectangles; it lies entirely within the bounding boxes if the union is the whole interval $[0,1]$.

The entire spline is then inside the bounding boxes if each of its component curves is.

Answer 2

Another answer has already suggested a specific algorithm, so I won't go into too many details on that. I think it's worth mentioning, though, that there are two properties of splines that you can put to use for this:

• A spline is a parametrized convex combination of its control points, and is thus contained in their convex hull.
• A spline can be efficiently subdivided into shorter splines of the same type.

Together, these allow for a recursive algorithm to check whether a spline is contained in a convex area (e.g. a rectangle): If an endpoint is outside the area, it isn't. If all control points are inside the area, it is. If neither is the case, subdivide and recursively apply the algorithm to the components.

You can find more on these properties at this SO question and the links provided there.