algorithm - 沿已知轴在外部路径边缘内查找内部路径的位置

Question

我正在寻找一种算法来计算包含在另一个封闭路径中的封闭路径的位置，以便它的中心点沿着已知轴并且它的壁橱尽可能靠近外部路径的边缘(不相交) .

路径很可能是简单的形状(椭圆形、矩形)，但如果有更通用的算法可以处理更复杂的路径(即由 CGPath/BezierPath 表示)，那就更好了。

这些例子更好地说明了:

在所有这三种情况下，我都有点A、点B和路径1/路径2。

我正在寻找P点的位置，它是Path 2的中心并且最接近Path 1的边缘> 沿着轴 A-B

是否有通用的方法来实现这一点，还是我需要针对特定​​形状分别计算它？

(第三个例子在只处理圆圈时显然很容易解决，但这只是一个具体案例)

我在 iOS 上使用 SpriteKit，所以如果有任何现有的 API 可供我利用，那就太好了。但是指向通用算法的指针也会有所帮助。

Answer 1

为了尽可能保持一般性，我会进行二分法搜索。这样你就可以完全不知道你的路径，只要你有一个黑盒函数告诉你路径是否相交。

这会浮现在脑海中，而且会非常简单，因为您只有一个参数，即一维问题。然后，您可以简单地描述 P 在 [0,1] 中具有实数 t 的位置:P = A + t * (B - A)，因此可能的空间很小

我假设您有一个函数 contained，给定 A 和 P 两个路径，当且仅当 Shape2 完全包含在 Shape1 中时返回 true(您定义的“无交集”)。

那么这个算法的一些伪代码可能如下:

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;
}