查找包含在任意旋转矩形中的网格单元的算法（栅格化）
Algorithm for finding grid cells contained in arbitrary rotated rectangle (rasterizing)
我正在寻找一种算法，该算法可以计算定义区域中 2d space 中任意矩形所占据的所有网格单元。矩形由它的 4 个角坐标定义。在下图中，我将其中两个标记为红色，网格单元格的坐标为黑色。我正在寻找一个通用案例，它也涵盖未对齐的网格（网格中心！= 底层坐标系统的中心），但是在单元格坐标 <=> 坐标系之间转换是微不足道的并且已经实现。所有单元格都是正方形。
计算在非常短的时间内完成数千次，需要尽可能快。
我现在在做什么：
现在我正在计算矩形的边缘（AB、BC、CD、DA）并以 sampleRate = cellWidth / 4 间隔对它们进行采样。为了找到中间的单元格，我构建了从 AB + sampleRate * x 到 CD + sampleRate * x 的新行，并在 sampleRate 处再次对这些行进行采样。我将在每个采样点找到的所有单元格放入 HashSet 中以删除重复项。但是我觉得这样效率低得令人难以置信。
我还考虑过将相关区域中的所有单元格抓取到缓冲区中并生成一个 范围树 或 索引树。然后我可以对矩形的边界进行排队并在 O(log n+m) 处获取所有包含的单元格，但我不确定如何实现它，我什至找不到任何 C# 范围树实现。
我在计算机图形学方面的知识很生疏，但难道不应该有一种无需采样即可工作的简单几何方法吗？
您关心的点在下图中用圆点标出。每个点代表给定 Y 值的最小 X 值或最大 X 值。对于每个 Y 值，X 值很容易从直线的方程式计算：
x = x0 + (y - y0)(x1 - x0) / (y1 - y0)
请注意，轴对齐的矩形（其中 (y1 - y0) 为 0）需要作为特殊（但微不足道）的情况。
另请注意，一旦您计算出沿矩形边缘的第一个 X 值，其他 X 值的间距就会相等。间距是直线斜率的倒数。所以除法
M = (x1 - x0) / (y1 - y 0)
只需要做一次，然后重复添加到X值。例如，计算图像中A点的X坐标后，B点的X坐标为Bx = Ax + M。 C点的X坐标是Cx = Bx + M.
获得每个 Y 值的最小 X 值和最大 X 值后，只需一个简单的 for 循环即可获取具有该 Y 值的所有单元格。
我正在寻找一种算法，该算法可以计算定义区域中 2d space 中任意矩形所占据的所有网格单元。矩形由它的 4 个角坐标定义。在下图中，我将其中两个标记为红色，网格单元格的坐标为黑色。我正在寻找一个通用案例，它也涵盖未对齐的网格（网格中心！= 底层坐标系统的中心），但是在单元格坐标 <=> 坐标系之间转换是微不足道的并且已经实现。所有单元格都是正方形。
计算在非常短的时间内完成数千次，需要尽可能快。
我现在在做什么：
现在我正在计算矩形的边缘（AB、BC、CD、DA）并以 sampleRate = cellWidth / 4 间隔对它们进行采样。为了找到中间的单元格，我构建了从 AB + sampleRate * x 到 CD + sampleRate * x 的新行，并在 sampleRate 处再次对这些行进行采样。我将在每个采样点找到的所有单元格放入 HashSet 中以删除重复项。但是我觉得这样效率低得令人难以置信。
我还考虑过将相关区域中的所有单元格抓取到缓冲区中并生成一个 范围树 或 索引树。然后我可以对矩形的边界进行排队并在 O(log n+m) 处获取所有包含的单元格，但我不确定如何实现它，我什至找不到任何 C# 范围树实现。
我在计算机图形学方面的知识很生疏，但难道不应该有一种无需采样即可工作的简单几何方法吗？
您关心的点在下图中用圆点标出。每个点代表给定 Y 值的最小 X 值或最大 X 值。对于每个 Y 值，X 值很容易从直线的方程式计算：
x = x0 + (y - y0)(x1 - x0) / (y1 - y0)
请注意，轴对齐的矩形（其中 (y1 - y0) 为 0）需要作为特殊（但微不足道）的情况。
另请注意，一旦您计算出沿矩形边缘的第一个 X 值，其他 X 值的间距就会相等。间距是直线斜率的倒数。所以除法
M = (x1 - x0) / (y1 - y 0)
只需要做一次，然后重复添加到X值。例如，计算图像中A点的X坐标后，B点的X坐标为Bx = Ax + M。 C点的X坐标是Cx = Bx + M.
获得每个 Y 值的最小 X 值和最大 X 值后，只需一个简单的 for 循环即可获取具有该 Y 值的所有单元格。