计算多边形旋转角度后的外接矩形

Question

计算多边形旋转角度后的外接矩形

algorithmgraphicsgeometry

7

我需要确定一个任意角度多边形的边界矩形。这张图片展示了我的需求： alt text http://kevlar.net/RotatedBoundingRectangle.png 对于简单的2D多边形，我需要在不同角度下确定粉色矩形。

非常感谢任何解决方案！

编辑：

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

- kevin42

“各种角度”是指边界矩形必须处于某个角度，还是内部形状必须处于某个角度？ - Welbog

你需要在这里调整一些角度，否则会有多个解决方案。 - Glenn

边界矩形的角度是变化的。我考虑过将多边形逆向旋转，然后围绕它拟合一个矩形，并将矩形的点旋转回来，但我认为我在正确地识别中心点方面出现了问题。 - kevin42

只需围绕0,0旋转即可，不需要中心点。 - Matthias Wandel

5个回答

3

要得到最小的矩形，需要获得直角。这可以通过在碰撞检测中使用的一种算法来实现：定向边界框。基本步骤如下：获取所有顶点坐标构建协方差矩阵找到特征值将所有顶点投影到特征值空间中在每个特征值空间中找到最大和最小值。

要了解更多信息，请搜索OBB“碰撞检测”。

提示：如果只是投影所有顶点并找到最大和最小值，则会产生AABB（轴对齐边界框）。这样做更容易且需要更少的计算工作，但不能保证得到最小的矩形。

- RMAAlmeida

2

我理解您的问题是“针对给定的2D多边形，如何计算边界矩形的位置，使其方向角已预先确定？” 我会通过将多边形旋转到所需方向角度，并使用适合于存储多边形点结构的搜索算法，在两个基本方向上寻找其最大和最小点。（简单来说，你需要找到最高和最低的X值，以及最高和最低的Y值。）然后，这些最小值和最大值就定义了您的矩形。您也可以在不先旋转多边形的情况下做同样的事情，但您的最小值和最大值点搜索必须更加复杂。

- Welbog

这是正确的。不应该为旋转角度为0的多边形计算边界框，然后再旋转边界框。这可能会导致bbox过大。我假设使用AABB（轴对齐）。 - ralphtheninja

1

为了获得一个包含多边形的最小面积矩形，您可以使用旋转卡壳算法。

关键的洞见是（与您的示例图像不同，因此我假设您实际上并不需要最小区域？），任何这样的最小矩形都与（凸包的）多边形至少一条边共线。

- Doug McClean

1

这是@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

- Noe

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- schnaader · Accepted Answer

要获得一个具有特定角度的边界框，请将多边形按相反的角度旋转。然后，可以使用最小/最大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;