logo标签列表

光栅路径跟随算法

algorithmraster
8

我有一个类似下面图片的值的栅格网格（白色是高值，黑色背景值为零）：

RasterGridExample

我正在尝试编写某种路径跟踪代码，从线的一端开始并跟踪到另一端，经过可能的最高值（也就是说，选择在线中的像素越白越好），但仍然要到达另一端。

我已经在这个问题上挣扎了一段时间，似乎无法让我尝试的任何东西起作用。那么我想知道，是否已经针对这种问题开发了通用算法？我做了很多搜索，但大多数路径算法似乎都是设计用于矢量/网络，而不是像这样的栅格网格。

有什么想法吗？

这是一个经典的成本距离问题，已经针对栅格数据进行了多次开发。例如，在R中，您可以使用gdistance包。 - Robert Hijmans
谢谢@RobertH - 那看起来是个有用的包。我仍然困扰于如何在不确定行的起始和结束位置时进行操作：也就是说，我必须识别出线的终点！如果您对此有任何想法，请告诉我。 - robintw
假设白色是大于250的值，可以这样写：r <- raster('file'); start <- which(r[1,] > 250); end <- ncell(r) -ncol(cell) + which(r[nrow(r), ] > 250) 通过start和end，你可以像这样计算坐标：xyFromCell(r, start)。 - Robert Hijmans
4个回答
8

最简单的想法可能是使用A*算法，其中每个像素都是一个节点，节点的成本是像素的黑暗程度。

更新：找到了一个不错的教程。

2
一种方法是：
  1. 将图像滤镜处理，使其更接近黑白像素。
  2. 通过白色像素绘制一条直线。要做到这一点，从一个白色像素开始。从该像素到每个距离为2（或3左右）的其他白色像素绘制一条线，但忽略靠近之前线条的像素。一直继续，直到覆盖了每个不接近（2或3个像素）于一条线的像素。在此过程中需要进行一些微调才能使其正常工作。
  3. 连接您绘制的线的端点。如果两个端点彼此相近（1或2个像素？），则将它们连接起来。您最终应该得到由许多短线段组成的几条线，可能带有一些环和分叉。
  4. 清除线条中的任何小环，并在分叉处分开线条，使您得到由许多短线段组成的几条线。
  5. 减少点数。对于每条线，请检查是否近似直线。如果是，则删除所有内部点。如果不是，则递归检查该线的两半，直到达到最小线段长度。
  6. 您可以选择在此时通过这些线拟合样条曲线。
  7. 获利。
需要进行一些微调才能使其正常工作，但这种方法是可行的。另一种变体是在白色部分周围绘制轮廓线，如果它们宽于1或2或3个像素，则在之后将双线条组合起来。
1

我认为你不需要遗传算法或任何荒谬的东西；好老式递归和动态规划应该足够。我最初的想法是，你应该能够通过进行广度优先搜索来实现你的目标。从起点开始，你访问所有得分大于该路径值的邻居--所有单元格最初都是无限的，黑色单元格的成本将是无限的，这些是你可以剪枝的路径。一旦到达目的地，如果可达，你应该能够回溯找到路径。这是贪婪的，但如果你的路径像这些一样表现良好，那就没问题。

对于更多灰色和曲折的路径，将光栅图像转换为图形，并将边缘权重设置为邻居的灰度值（或灰度值之间的差异，具体取决于这个数据实际意义）。因此，你应该能够使用基于该解释的任何最短路径算法。

感谢回复。很抱歉 - 我指的是一种通用算法，可以应用于各种寻路问题，而不是专门针对某些特定问题的算法。我将研究广度优先搜索。 - robintw
哎呀...这就是整天盯着屏幕的后果。当1/I/l或o/0混淆时，你可能有字体问题；当r/t混淆时，你可能有心理问题。但在这种情况下，一旦你将光栅图像转换为图形，或者将其视为图形，你应该能够使用任何最短路径算法。 - nlucaroni
1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接