是否有一种性能/数学方法来查找网格中旋转的矩形重叠的图块？

Question

我正在尝试找出矩形重叠的图块。现在，我只是获取矩形的混合/最大边界，并迭代这些边界内的网格图块。对于每个图块，我检查图块矩形是否与另一个矩形相交。这不是很好的表现，因为我仍然必须迭代很多图块并进行很多交集检查。

我想知道是否有更高性能或数学的方法来实现这一目标。

Answer 1

通过Y坐标对矩形顶点进行排序，并分别处理顶点Y位置之间的水平带（可以得到1、2或3个带）。

对于左侧和右侧的每个Y间隔，请使用Bresenham算法（对于像素）或Amanatides-Woo算法（对于单元格/体素）遍历它们。

对于每个水平，都有最左边和最右边的单元格，也填充它们之间的所有单元格。

也请寻找三角栅格化算法以获取更多想法。