计算多边形角度处的边界矩形

Question

我需要确定任意角度的多边形的外接矩形。这张图说明了我需要做什么：

替代文本http://kevlar.net/RotatedBoundingRectangle.png

粉色矩形是我需要在不同角度确定简单的二维多边形的矩形。

非常感谢任何解决方案！

编辑：

感谢您的回答，一旦中心点正确，我就可以正常工作了。你们太棒了！

Answer 1

要获得具有特定角度的边界框，请将多边形反向旋转该角度。然后，您可以使用最小/最大 x/y 坐标来获取一个简单的边界框，并将其旋转一定角度以获得最终结果。

从您的评论看来，您在获取多边形的中心点时遇到了问题。多边形的中心应该是每个点的坐标和的平均值。因此对于点 P1,...,PN，计算：

xsum = p1.x + ... + pn.x;
ysum = p1.y + ... + pn.y;
xcenter = xsum / n;
ycenter = ysum / n;

为了完成此任务，我还添加了一些涉及旋转的公式。要围绕中心点 (cx, cy) 旋转点 (x,y)，请执行以下操作：

// Translate center to (0,0)
xt = x - cx;
yt = y - cy;
// Rotate by angle alpha (make sure to convert alpha to radians if needed)
xr = xt * cos(alpha) - yt * sin(alpha);
yr = xt * sin(alpha) + yt * cos(alpha);
// Translate back to (cx, cy)
result.x = xr + cx;
result.y = yr + cx;

Answer 2

要获得最小的矩形，您应该获得正确的角度。这可以通过碰撞检测中使用的算法来完成：定向边界框。 基本步骤：

获取所有顶点坐标
构建协方差矩阵
求特征值
投影特征值空间中的所有顶点
找到每个特征值空间中的最大值和最小值。

欲了解更多信息，只需谷歌 OBB“碰撞检测”

Ps：如果你只是投影所有顶点并找到最大值和最小值，你就会制作 AABB（轴对齐边界框）。它更容易并且需要更少的计算量，但不能保证最小框。

Answer 3

我将你的问题解释为“对于给定的二维多边形，如何计算预定方向角的边界矩形的位置？”

我会通过逆方向角度旋转多边形来实现这一点，然后使用适合存储多边形点的结构的任何搜索算法，在两个基本方向上简单搜索其最大和最小点。 （简单来说，你需要找到最高和最低的X值，以及最高和最低的Y值。）

然后最小值和最大值定义你的矩形。

您可以在不先旋转多边形的情况下执行相同的操作，但对最小和最大点的搜索必须更加复杂。

Answer 4

要获得包围多边形的最小面积的矩形，您可以使用旋转卡尺算法。

关键的见解是（与您的示例图像不同，所以我假设您实际上不需要最小面积？），任何这样的最小矩形都与多边形（的凸包）的至少一个边缘共线。

Answer 5

这里是 @schnaader 答案的 python 实现。 给定一个具有坐标 x 和 y 的点集以及限制这些点的矩形的度数，该函数返回一个具有四个角（以及第一个角的重复）的点集。

def BoundingRectangleAnglePoints(x,y, alphadeg):
    #convert to radians and reverse direction    
    alpha = np.radians(alphadeg)
    
    #calculate center
    cx = np.mean(x)
    cy = np.mean(y)

    #Translate center to (0,0)
    xt = x - cx
    yt = y - cy

    #Rotate by angle alpha (make sure to convert alpha to radians if needed)
    xr = xt * np.cos(alpha) - yt * np.sin(alpha)
    yr = xt * np.sin(alpha) + yt * np.cos(alpha)

    #Find the min and max in rotated space
    minx_r = np.min(xr)
    miny_r = np.min(yr)
    maxx_r = np.max(xr)
    maxy_r = np.max(yr)
    #Set up  the minimum and maximum points of the bounding rectangle    
    xbound_r = np.asarray([minx_r, minx_r, maxx_r, maxx_r,minx_r])
    ybound_r = np.asarray([miny_r, maxy_r, maxy_r, miny_r,miny_r])
    
    #Rotate and Translate back to (cx, cy)
    xbound = (xbound_r * np.cos(-alpha) - ybound_r * np.sin(-alpha))+cx
    ybound = (xbound_r * np.sin(-alpha) + ybound_r * np.cos(-alpha))+cy
  
    return xbound, ybound