Finding the position of an inner path within the edges of an outer path along a known axis
I am looking for an algorithm to calculate the position of a closed path contained within another closed path so that its center point along a known axis and its cabinets to the edge of the outer path as much as possible (without crossing it).
The paths will most likely be simple shapes (oval, rectangular), but it would be nice if there was a more general algorithm that can work with more complex paths (i.e. represented by CGPath / BezierPath).
Better illustrated with 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 that is the center of Path 2 and places it closer to the edges of Path 1 along the AB axis
Is there a general way to achieve this or do I need to calculate it for individual forms separately?
(the third example is obviously easy to solve when working with circles only, but this is just one specific case)
I am using SpriteKit for iOS, so if there is any existing API that I can use, great. But pointers to the general algorithm will help too.
source to share
To make this as general as possible, I would go on a dichotomous search. This way you can be completely agnostic about your paths if you have a black box function that tells you if paths intersect.
This comes to mind and is going to be really simple because you only have one parameter, which is the 1D problem. Then you have a simple characterization of the position of P with a real number t at [0,1]: P = A + t * (B - A)
and therefore a small space of possibilities for P.
I suppose you have a function contained
that, given both paths A and P, returns true
if and only if Shape2 is entirely contained in Shape1 ("no intersection" as you define it).
Then some pseudocode for this algorithm might be as follows:
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;
}
source to share