将矩形放置在多边形内的算法

Question

有没有可以将任意矩形放置在任意多边形内的算法（我可以处理仅限凸多边形的限制），并使其处于最接近可用位置（即不与多边形相交）？

例如，一个算法应该将上面图片中的矩形移动到这个位置：

很重要的一点是，我不知道矩形在离开多边形前的原始位置。因此，我应该在多边形内找到最接近的可用位置。

- nitrovatter

---

这应该很容易用线性规划实现。您正在寻找一个最小范数的翻译向量v = (vx, vy)，使得矩形的四个角落都在多边形内部。 "在多边形内"可以转化为一组2n个线性不等式，其中n是多边形的边数：多边形的每条边都给出了一个不等式，表示“在此线上方”（或“在此线下方”）。 - Stef

请注意，在非凸多边形的情况下，矩形的所有4个角可能在多边形内部，而矩形的某些部分却在多边形外部；但是在凸多边形的情况下，如果矩形的四个角都在内部，则整个矩形都在内部。 - Stef

我建议使用scipy.optimize来解决这个最小化问题。 - Stef

我对线性规划有一些了解，但是我甚至不知道如何处理非负约束条件，以及这里的目标函数是什么？它根本不是线性的，因为长度不是线性的：l(v) = sqrt(vx^2 + vy^2)。 - nitrovatter

@Stef 你可能想说的是二次规划，但这可能有些过头了（而且只适用于凸多边形）。相反，计算多边形和矩形之间的Minkowski差，然后计算该点到多边形中“枢轴”点的最近距离。（不确定复杂度会是什么样子） - user202729

Answer 1

至少对于凸多边形，我相信有一个相当简单的解决方案，它涉及构建内嵌多边形，表示矩形与多边形接触时矩形中心点的轨迹。

图表可以帮助理解-蓝色多边形代表输入多边形，红色多边形是我们需要构建的内部多边形。

一旦我们拥有了这个内部多边形，我们只需找到距离矩形中心最近的点，并将矩形的中心平移到该点上。如果内部多边形包含矩形的中心，则可以选择保持不变或向外平移，使其与外部多边形相接触。

内部多边形可以通过将输入多边形的每条边缩进矩形角度宽度的一半的距离，并确定相邻缩进边的交点来构造。如果外部多边形的一条边与正x轴成角度 a ，则缩进距离如下所示。请注意，如果 a 不在第一象限中，则我们必须确保这一点，可能会交换矩形的宽度和高度。

一旦我们得到了相邻边的内嵌距离，就可以根据下面所示的方式计算内部多边形上的对应点，其中b是相邻边之间的角度，p'是计算出的点。

这里有一些Java代码用于说明-我们假设输入的多边形是按逆时针顺序排列的，这样在沿着边行进时内部就在左侧。

List<Point2D> poly = new ArrayList<>(Arrays.asList(p(0, 0), p(10, 0), p(13, 7), p(9, 12), p(4, 15), p(-3, 11), p(-5, 6)));

List<Point2D> innerPoly = new ArrayList<>();
            
int n = poly.size();
for(int i=0, j=n-1; i<n; j=i++)
{
    Point2D p0 = poly.get(j);
    Point2D p1 = poly.get(i);
    Point2D p2 = poly.get((i+1) % n);
    
    Point2D u0 = unit(p0, p1);
    Point2D u1 = unit(p1, p2);
    
    double d0 = rectAngDist(u0, outerRect);
    double d1 = rectAngDist(u1, outerRect);
    
    double phi = Math.PI - angle(u0, u1);
    
    double v0 = d0 / Math.sin(phi);
    double v1 = d1 / Math.sin(phi);

    innerPoly.add(add(p1, add(times(u0, -v1), times(u1, v0))));
}

static double rectAngDist(Point2D u, Rectangle2D r)
{
    double w = r.getWidth();
    double h = r.getHeight();
    
    double s0 = w;
    double s1 = h;
    
    double th0 = angle(u);
    if(th0 < 0) th0 += Math.PI;
    if(th0 > Math.PI/2) 
    {
        s0 = h; s1 = w; 
        th0 -= Math.PI/2;
    }               
    
    return (s0 * Math.sin(th0) + s1 * Math.cos(th0))/2;         
}

一旦我们得到内部多边形，就可以确定最近的点并将矩形平移以重合。

Point2D centre = p(outerRect.getCenterX(), outerRect.getCenterY());
if(innerPoly.contains(centre))
{
    innerRect.setFrame(outerRect);
    return;
}
            
double minDist = 0;
Point2D closestPoint = null;
for(int i=0, j=n-1; i<n; j=i++)
{
    Point2D p0 = innerPoly.get(j);
    Point2D p1 = innerPoly.get(i);
    
    double len = distance(p0, p1);              
    Point2D u = unit(p0, p1);               
    
    Point2D diff = sub(centre, p0);             
    double s = dot(u, diff);
    
    Point2D pp = (s < 0) ? p0 : (s > len) ? p1 : add(p0, times(u, s));  
    
    double dist = distance(pp, centre);             
    if(closestPoint == null || dist < minDist)
    {
        closestPoint = pp;
        minDist = dist;
    }
}

translate(outerRect, sub(closestPoint, centre), innerRect);     

我用Java实现了上述内容以测试这些想法 - 您可以在此处观看应用程序的短片段（Youtube）。

- RaffleBuffle

---

非常感谢您提供如此好的和详细的答案！ - nitrovatter

该方法也适用于凹多边形，尽管构造更加复杂。该操作是闵可夫斯基差。 - user1196549

我不确定当一个边比矩形的边短时，你的解决方案是否有效。 - user1196549