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

Question

我有两条平行线，可以向任何方向移动。他们保证不一样。

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

我需要一种算法来生成所有正方形的列表，其中两条线之间有任何区域。

我目前的算法效率极低（将两条线表示为一个旋转的矩形，然后在每个正方形上测试多边形-多边形相交）。它有效，但速度非常慢。

Answer 1

如果您知道两条线的方向和位置，那么您可以使用Bresenham 线算法来计算将被任何一条线“触及”的所有“正方形”。添加中间方块将是一项简单的工作。如果两条线被整数个“正方形”隔开，那么您只需要为其中之一求解 Bresenham，但如果它们具有非整数分隔，则必须为它们求解（后者也可以即使线条不平​​行）。