我需要确定任意角度的多边形的外接矩形。这张图说明了我需要做什么:
替代文本http://kevlar.net/RotatedBoundingRectangle.png
粉色矩形是我需要在不同角度确定简单的二维多边形的矩形。
非常感谢任何解决方案!
编辑:
感谢您的回答,一旦中心点正确,我就可以正常工作了。你们太棒了!
要获得具有特定角度的边界框,请将多边形反向旋转该角度。然后,您可以使用最小/最大 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;
要获得最小的矩形,您应该获得正确的角度。这可以通过碰撞检测中使用的算法来完成:定向边界框。 基本步骤:
获取所有顶点坐标
构建协方差矩阵
求特征值
投影特征值空间中的所有顶点
找到每个特征值空间中的最大值和最小值。
欲了解更多信息,只需谷歌 OBB“碰撞检测”
Ps:如果你只是投影所有顶点并找到最大值和最小值,你就会制作 AABB(轴对齐边界框)。它更容易并且需要更少的计算量,但不能保证最小框。
我将你的问题解释为“对于给定的二维多边形,如何计算预定方向角的边界矩形的位置?”
我会通过逆方向角度旋转多边形来实现这一点,然后使用适合存储多边形点的结构的任何搜索算法,在两个基本方向上简单搜索其最大和最小点。 (简单来说,你需要找到最高和最低的X值,以及最高和最低的Y值。)
然后最小值和最大值定义你的矩形。
您可以在不先旋转多边形的情况下执行相同的操作,但对最小和最大点的搜索必须更加复杂。
要获得包围多边形的最小面积的矩形,您可以使用旋转卡尺算法。
关键的见解是(与您的示例图像不同,所以我假设您实际上不需要最小面积?),任何这样的最小矩形都与多边形(的凸包)的至少一个边缘共线。
这里是 @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