geometry - 如何将一条线离散为与任意网格对齐的线段

Question

考虑：

目的是将任意线段（红线）离散化为一组在任意网格（蓝线段）上对齐的连接线段。这里只显示了两种简单形式的网格，即正方形和旋转的正方形网格。红线可以是任何角度和大小。包括类型和单元格大小的网格配置由用户选择。Bresenham 的离散化可能适用于简单的情况，但即使这样也有两个障碍：

1. 它仅限于垂直和水平对齐的网格。
2. 它给出了需要线段的像素（即方形块）。

重要更新： 重要更新：我们对适用于任何网格复杂性的通用解决方案感兴趣。

一种更通用的方法是令人感兴趣的。非常感谢提供伪代码或代码。这个问题也可以在这里找到。

Answer 1

在旋转矩形网格的情况下：

• 对线段端点应用逆旋转变换
• 使用 Bresenham 没有传统的半像素偏移（使像素块居中）
  • 该算法给出水平和垂直[或短轴，长轴]增量
• 对线段应用正向旋转变换

在“随机”网格的情况下，我建议使用基于单元格的方法，如果需要，每个单元格首先被分成凸面（Voronoi 区域）。例如。六边形网格已经由 voronoi 区域组成。保留每个单元格的邻居列表。

• 第一个任务是仅通过每个单元的邻居从起始单元到结束单元。幸运的是，在凸曲面细分的情况下，可以选择中心更接近/最接近目标的单元格。（搜索结束，当没有进展时）。

• 下一个任务是在每个单元格中找到从入口点到出口点的路径，CW 或 CCW。一个更短。

数字：

a----------b--------------d  
*          |              |  
     A     c       B      |     C
                          e
                          |           x
                          f-----------g

这里端点“*”和“x”位于单元格的边界内。一种形成模式'*abcbdefgx'并将其简化为'*abdfgx'甚至'*adfgx'，因为'ba' dot 'db'（标准化）为零或至少非常接近。