pythonoptimizationgeometrygeometry-surface

Scale a shape to fully include another shape


I have an optimization problem that I can't seem to wrap my head around. I have two shapes, both of which are described by parametric equations. Call them a(theta) and b(theta).

What I would like to do is, given one shape a(theta), scale another shape b(theta) to completely enclose the first shape. The complexity comes in that the actual geometric shape of a(theta) and b(theta) may change depending on user-defined parameters.

I can do this by checking every point on the surface of a(theta) and b(theta), but I was hoping that there is a more computationally-efficient method. Does anyone have any suggestions?

Thanks!

Here's a figure showing what I mean by "one shape inside another:"

Two shapes, one within another.


Solution

  • If you need merely to scale the outer figure, with no need to find even a near-optimal solution, then it's relatively simple.

    Convert both equations to polar coordinates. Parameterize the radius coefficient of b. Subtract, so that you have something of the form

    c(theta, r) = r * b(theta) - a(theta)
    

    Now, you simply solve for r, find a value such that c is positive for all theta. this will be as complex as your parameterized descriptions of the shapes.


    If you need a minimal solution, or a near-minimal solution, then there is no good, closed-form solution. Consider the definition of (r, theta) above, but add more parameters: you can translate or rotate the equation as well, giving you

    c(theta, alpha, r, (h, k)) = r * b(theta + alpha, (h, k)) - a(theta)
    

    This 5-dimensional space is harder to search. A typical heuristic is gradient descent on the search space, but this does not work with arbitrary spaces -- only those with nicely-behaved gradients.


    If you have known restrictions on your shapes, there may be a good general solution with rotations and translations. For instance, if you know that the shapes are convex, the problem becomes much easier: you identify maximum and minimum spans, or iteratively expand and move the outer shape until all overlaps are resolved. However, that would require a new problem definition and a new question posted.