计算多边形在网格中旋转后所占的位置
Calculate positions occupied by a polygon after rotation in a grid
我找了一些类似的问题，但我认为没有一个与我的问题相关。
我正在用 C++ 编写 10x10 网格单元中简单多边形（即矩形、L 形多边形...）的平移和旋转编码。
假设我有一个宽度 = 1 个单元格、高度 = 3 个单元格的矩形。在 8 个方向上翻译它很容易。但是如果我想把这个多边形旋转45º，我可以得到，但是我想计算哪些是现在被矩形占据或部分占据的单元格。
我有矩形的质心，也就是它的一个单元格。我可以根据大小计算旋转前矩形所占的位置。但是，旋转后，我找不到计算矩形所占单元格位置的方法。
非常感谢！
您绝对可以将其视为边界框问题 -
取矩形的四个角，这些角的 x,y 坐标是它们占据的单元格编号 - 例如对于以 o(2,2) 为中心的 width = 1 cell 和 height = 3 cells 的矩形，以角（x，y）格式表示的这 4 个角将是 - a(1.5,3.5) b(2.5,3.5) c(2.5,0.5) d(1.5,0.5)。
一旦清楚了这一点，我认为您可能已经理解了剩余的过程，因为它已经在此处进行了多次解释 -
Calculate Bounding box coordinates from a rotated rectangle
总而言之，将 2D 旋转的标准矩阵应用于这 4 个角并获得新的角，例如
a'.x = o.x + (a.x - o.x) * cos(t) + (a.y - o.y) * sin(t)
a'.y = o.y - (a.x - o.x) * sin(t) + (a.y - o.y) * cos(t)
其他点也类似。然后找到 max and min x and y ，它们将代表您的矩形占据的单元格。其他凸多边形也可以做类似的事情。
更新：
正如 Fang 所评论的那样，要获得旋转多边形占用的准确单元数，您仍然需要对边界框内的所有方形单元进行正方形到多边形的交集检查-您可以看看这个 -
How to check intersection between 2 rotated rectangles?
这是我会做的：
1) 获取原始多边形的顶点。由于您的多边形由连接的网格单元组成，因此我认为这些顶点的坐标都是整数。
2) 旋转多边形顶点。我假设您知道如何执行此操作，因为您知道如何旋转多边形。
3) 要检测给定的单元格是否仍被旋转的多边形占据，请检查该单元格是否与旋转的多边形有任何交集。所以，这基本上是一个正方形到多边形的交叉检查。当完全没有交点或者交点是边或顶点时，可以断定这个单元格没有被旋转的多边形占据。
4) 对所有单元格执行第 3 步。
在第 4 步中，您实际上可以使用旋转多边形的边界框来轻松地从正方形到多边形的相交检查中排除一些单元格，而不是遍历所有单元格。但是，如果您只有 10x10 个单元格，您可能可以在没有它的情况下逃脱，而不会看到任何性能差异。
我找了一些类似的问题，但我认为没有一个与我的问题相关。
我正在用 C++ 编写 10x10 网格单元中简单多边形（即矩形、L 形多边形...）的平移和旋转编码。
假设我有一个宽度 = 1 个单元格、高度 = 3 个单元格的矩形。在 8 个方向上翻译它很容易。但是如果我想把这个多边形旋转45º，我可以得到，但是我想计算哪些是现在被矩形占据或部分占据的单元格。
我有矩形的质心，也就是它的一个单元格。我可以根据大小计算旋转前矩形所占的位置。但是，旋转后，我找不到计算矩形所占单元格位置的方法。
非常感谢！
您绝对可以将其视为边界框问题 -
取矩形的四个角，这些角的 x,y 坐标是它们占据的单元格编号 - 例如对于以 o(2,2) 为中心的 width = 1 cell 和 height = 3 cells 的矩形，以角（x，y）格式表示的这 4 个角将是 - a(1.5,3.5) b(2.5,3.5) c(2.5,0.5) d(1.5,0.5)。
一旦清楚了这一点，我认为您可能已经理解了剩余的过程，因为它已经在此处进行了多次解释 -
Calculate Bounding box coordinates from a rotated rectangle
总而言之，将 2D 旋转的标准矩阵应用于这 4 个角并获得新的角，例如
a'.x = o.x + (a.x - o.x) * cos(t) + (a.y - o.y) * sin(t)
a'.y = o.y - (a.x - o.x) * sin(t) + (a.y - o.y) * cos(t)
其他点也类似。然后找到 max and min x and y ，它们将代表您的矩形占据的单元格。其他凸多边形也可以做类似的事情。
更新： 正如 Fang 所评论的那样，要获得旋转多边形占用的准确单元数，您仍然需要对边界框内的所有方形单元进行正方形到多边形的交集检查-您可以看看这个 -
How to check intersection between 2 rotated rectangles?
这是我会做的：
1) 获取原始多边形的顶点。由于您的多边形由连接的网格单元组成，因此我认为这些顶点的坐标都是整数。
2) 旋转多边形顶点。我假设您知道如何执行此操作，因为您知道如何旋转多边形。
3) 要检测给定的单元格是否仍被旋转的多边形占据，请检查该单元格是否与旋转的多边形有任何交集。所以，这基本上是一个正方形到多边形的交叉检查。当完全没有交点或者交点是边或顶点时，可以断定这个单元格没有被旋转的多边形占据。
4) 对所有单元格执行第 3 步。
在第 4 步中，您实际上可以使用旋转多边形的边界框来轻松地从正方形到多边形的相交检查中排除一些单元格，而不是遍历所有单元格。但是，如果您只有 10x10 个单元格，您可能可以在没有它的情况下逃脱，而不会看到任何性能差异。