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

Question

是否有任何算法可以将任意矩形放置在任意多边形内（我可以处理仅限于凸多边形的限制）在最近的可用位置（即没有与多边形的交点）？

例如，算法应该将矩形从上图移动到这个位置：

重要的是，我不知道矩形在离开多边形之前的原始位置。所以我应该在多边形中找到最接近的可用位置。

Answer 1

至少对于凸多边形，我相信有一个相当简单的解决方案，它涉及当矩形刚好接触多边形时构造代表矩形中心点轨迹的插入多边形。

图表有望有所帮助 - 蓝色多边形代表输入多边形，红色代表我们需要构建的内部多边形。

一旦我们有了这个内部多边形，我们就可以定位最接近矩形中心的点并将矩形的中心平移到与该点重合的位置。如果内部多边形包含矩形的中心，那么您可以选择保持不变或将其向外平移以使其接触外部多边形。

可以通过将输入多边形的每条边插入等于矩形 angular 宽度一半的距离，并确定相邻插入边的交点来构造内部多边形。如果外多边形的一侧与正 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)。

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

Algorithm to place the rectangular inside the polygon

algorithm

collision-detection

computational-geometry