An Efficient Solution to the 2D Visibility Problem in Cartesian Grid Maps and its Application in Heuristic Path Planning

本文介绍了一种新颖的轻量级方法来解决二维网格的可见性问题。所提出的方法在单次遍历中评估源点到所有其他网格单元的视线存在性，无需预处理，且独立于障碍物的数量和形状。它的计算和内存复杂度为$\mathcal{O}(n)$，其中$n=n_{x}\times{} n_{y}$是网格的大小，并且每个网格单元最多需要十次算术运算。在所提出的方法中，我们使用一阶线性双曲型偏微分方程来传输所有方向上的可见性量。为了实现这一点，我们使用了一个熵满足的迎风格式，当步长趋近于零时，它会收敛于真实的可见性多边形。这种动态规划方法比典型的射线投射算法快数个数量级，可以评估整个网格的可见性。我们将可见性量作为一种启发式方法，并实现了一个确定性的、无局部最小值的路径规划器，将所提出的规划器与传统方法区分开来。最后，我们提供了必要的算法和所提出方法的开源实现。

本论文旨在提出一种轻量级的方法，解决2D网格的可见性问题。该方法可以在单次遍历中独立于障碍物的数量和形状，评估从源点到所有其他网格单元的视线存在性。该方法的计算和内存复杂度为O(n)，其中n为网格的大小，每个网格单元最多需要十次算术运算。

本论文提出了一种使用线性一阶双曲型偏微分方程传输视线数量的方法，使用满足熵条件的上风方案，该方案随着步长趋近于零而收敛于真实的可见性多边形。这种动态规划方法比典型的射线投射算法快几个数量级，可以评估整个网格的可见性。

本论文的亮点是将可见性数量作为启发式，并实现确定性、无局部最小值的路径规划器，使其与传统方法区分开。此外，本论文提供了必要的算法和开源实现。

最近在这个领域中，还有一些相关的研究，如：《A Fast Visibility Algorithm for 2D Grids》、《Efficient Shortest Path Finding Algorithms on Road Networks with Turn Costs》等。