Finding position of inner path within outer path edges along known axis

Question

I am looking for an algorithm to calculate a position of a closed path contained within another closed path so that its center point is along a known axis and its the closets to the outer path's edge as much as possible (without intersecting it).

The paths are most likely to be simple shapes (oval, rectangle) but would be nice if there is a more general algorithm that can work with more complex paths (i.e. represented by CGPath/BezierPath).

Better illustrated by these examples:

In all three cases, I have point A, point B and Path 1 / Path 2.

I am looking for the position of point P, which is the center of Path 2 and places it closest to the edges of Path 1 along the axis A-B

Is there a general way to achieve this or do I need to calculate it for specific shapes separately?

(the 3rd example is obviously easily solved when dealing with circles only, but this is just one specific case)

I am using SpriteKit on iOS, so if there are any existing API that I can take advantage of, great. But pointers to a general algorithm would help too.

Answer 1

To keep this as general as possible, I would go for a dichotomic search. That way you can be completely agnostic about your paths, as long as you have a black-box function that tells you whether paths intersect.

This comes to mind and would be really simple because you only have one parameter, that is a 1D problem. Then you have a simple characterization of the position of P with a real number t in [0,1] : P = A + t * (B - A), and thus a small space of possibilities for P.

I will suppose you have a function contained that, given both paths, A, and P, returns true if and only if the Shape2 is entirely contained in Shape1 ("without intersection" as you define it).

Then some pseudo-code for this algorithm could be the following :

Point find_P(Path1, Path2, A, B)
{
    if( !contained(Path1,A,Path2,P) )
        throw ("Impossible for P == A !");
    else if( contained(Path1,B,Path2,P) )
        return B;

    double dt = 0.5;
    Point P=A, V = B-A;

    while(dt > eps) // where eps is your precision parameter
    {
        if( contained(Path1,A,Path2, P+dt*V ) )
             P += dt * V;
        dt /= 2;
    }
    return P;
}