c# - 查找包含在任意旋转矩形中的网格单元的算法（光栅化）

Question

我正在寻找一种算法，可以计算定义区域中二维空间中任意矩形占用的所有网格单元。矩形由它的 4 个角坐标定义。在下图中，我将其中两个标记为红色，网格单元格的坐标为黑色。我正在寻找一个通用案例，它还涵盖未对齐的网格（网格中心！= 底层坐标系的中心），但是在单元坐标 <=> 坐标系之间进行转换是微不足道的并且已经实现。所有单元格都是正方形。

计算在很短的时间内完成了数千次，并且需要尽可能快。

我现在在做什么：

现在我正在计算矩形的边缘（AB、BC、CD、DA）并每sampleRate = cellWidth / 4隔一段时间对它们进行采样。为了找到中间单元格，我从AB + sampleRate * xto构造新行CD + sampleRate * x并在 处再次对这些行进行采样sampleRate。我将在每个采样点找到的所有单元格放入 HashSet 以删除重复项。但我觉得这是非常低效的。

我还考虑将相关区域中的所有单元格抓取到缓冲区中并生成范围树或索引树。然后我可以对矩形的边界进行排队并在 O(log n+m) 处获取所有包含的单元格，但我不确定如何实现它，我什至找不到任何 C# 范围树实现。

我在计算机图形学方面的知识非常生疏，但不应该有一种简单的几何方法无需采样即可工作吗？

Answer 1

您关心的点在下图中标有一个点。每个点代表给定 Y 值的最小 X 值或最大 X 值。对于每个 Y 值，X 值很容易从直线的等式计算：

x = x ₀ + (y - y ₀ )(x ₁ - x ₀ ) / (y ₁ - y ₀ )

请注意，轴对齐的矩形（其中 (y ₁ - y ₀ ) 为 0）需要作为特殊（但微不足道）的情况进行处理。

另请注意，一旦您沿矩形边缘计算了第一个 X 值，其他 X 值将等距分布。间距是直线斜率的倒数。所以除法
M = (x ₁ - x ₀ ) / (y ₁ - y ₀ )
只需要做一次，然后重复加到 X 值上。例如，计算图像中A点的X坐标后，B点的X坐标为B _x = A _x + M。C点的X坐标为C _x = B _x + M。

一旦有了每个 Y 值的最小和最大 X 值，就可以通过一个简单的for循环来获取具有该 Y 值的所有单元格。