如何離散的線成對準以任意網格段

Question

考慮：

目的是離散的任意直線段，紅線，爲一組上的任意網格對齊的連接的線路段的（藍線段）。這裏僅示出兩種簡單形式的網格，即正方形和旋轉正方形網格。 紅線可以是任何角度和大小。 包含類型和單元大小的網格配置取決於用戶的選擇。 布氏離散可能適用於簡單的情況，但即使如此，有兩個障礙：

1. 它是有限的垂直和水平對齊網格。
2. 它給出需要線段爲 的像素（即方塊）。

重要更新： 重要更新： 我們感興趣的是它適用於任何複雜電網通用的解決方案。

更爲廣泛的方法是有意義的。提供pesudo代碼或代碼非常讚賞。 這個問題也可以找到here。

Answer 1

在旋轉矩形網格的情況下：

• 應用逆旋轉變換的線段端點
• 使用布氏無需傳統半象素偏移（到中心的像素塊）
  • 該算法給出水平和垂直[或短軸，長軸]增量
• 對線段應用正向旋轉變換

在「隨機」網格的情況下，我建議使用基於單元格的方法，其中每個單元格首先在必要時分割爲凸面（Voronoi區域）。例如。六邊形網格已經包含了voronoi區域。保留每個單元格的鄰居列表。

• 第一個任務是從開始的單元格到結束單元格只通過每個單元格的鄰居。幸運的是，在凸面細分的情況下，可以選擇其中心離目標更近/更近的單元格。 （搜索結束，無法進行時）。

• 接下來的任務是在每個單元中找到從入口點到出口點的路徑，CW或CCW。一個更短。

圖：

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

這裏端點 '*' 和 'X' 是在單元的邊界。 由於'b-a'點'd-b'（歸一化）爲零或至少非常接近，所以形成'* abcbdefgx'模式並將其減少到'* abdfgx'或甚至減少到'* adfgx'。