algorithm - 将平行线与正交二维网格相交

Question

我有两条平行线，可以向任何方向延伸。它们保证不会相同。

我有一个二维网格(具有从 0.0 到 1.0 的非整数坐标，但我怀疑这可以通过缩放整个问题来解决)，以通常的方式正交对齐。

我需要一种算法来生成所有正方形的列表，这些正方形的面积在两条线之间。

我当前的算法非常低效(将两条线表示为旋转的矩形，然后在每个正方形上测试多边形与多边形的交集)。它有效，但速度慢得可怕。

Answer 1

如果您知道这两条线的方向和位置，那么您可以使用 Bresenham line algorithm计算任何一条线将“接触”的所有“正方形”。添加中间方 block 将是一项简单的工作。如果这两条线被整数个“正方形”隔开，那么您只需为其中一个解决 Bresenham，但如果它们具有非整数分隔，您将不得不为它们解决两个问题(后者也可以即使这些线不平行)。