2

我想知道是否有任何描述的算法可以将等时线转换为近似区域以显示一些特征的范围（在我的问题中，这个特征是道路网络）。

例子。我在下面的图像上有类似的东西：

公路网

X这是一个简单的网络（我可以在几分钟或Y几公里内从起点到达）。我有所有节点和链接的信息。现在我需要创建一个等时线图，显示我可以到达的大致范围。

问题：

  1. Convex hull- 由于过于笼统的近似而很糟糕，
  2. 我可以在道路上创建缓冲区 - 所以我会得到一些显示范围的多边形，但我也会在连接成圆圈的道路旁有洞。

我需要获得的是这样的：

等时线图

我在这里找到了一些可能有用的信息，但只有一些想法可以做到。如果有人有任何概念，请帮助我解决我的问题。

4

2 回答 2

2

有趣的问题，为了获得更好的答案，您可能想要准确定义显示范围（等时线图）的该区域将用于什么？例如，它是说明性的吗？如果你定义你想要什么样的近似值，它可以帮助你解决问题。

现在这里有一些想法。

1）找到图中的所有循环（见链接），然后消除两个循环之间共享的边。最后取剩余循环的凸包，这与所有道路一起，以便包括不形成循环的异常值，将为等色图提供良好的近似值。

2）更简单的解决方案是在每条道路的每个点周围定义一个厚度，这个厚度应该与从起点到达该点所需的时间成反比。即到达该点所需的时间越长，厚度越薄。然后，您可以缩放所有点的厚度，直到所有整体都被填充，然后您将获得一个近似的等色图。实现这一点的一种可能方法是运行一种算法，该算法从起点同时采用所有可能的路线，在每个新的交叉点处分支，同时跟踪到达每个点所用的时间。在其执行过程中，每时每刻都应加粗所有先前发现的路线。最后，您可以缩放此厚度以填充所有整体。

希望这会有所帮助。祝你好运。

于 2013-08-02T23:21:09.950 回答
1

我已经解决了这个问题（它不是那么快和健壮，但现在必须足够了）。

  1. 我使用A* (A-Star) algorithm.
  2. 我从第一点开始就使用@Artur Gower 的想法来消除循环并简化我的几何形状。

后来我决定生成 2 种类型的几何图形（第一种 - 像在图像上，第 2 种 - 简单缓冲区）：

第一个：
3。然后我使用Douglas-Peucker algorithm（非常快！）删除了其余不必要的点。
4. 最后我使用了Concave Hull algorithm（又名Alpha-Shapes或Non-Convex Hull）。

第二个：
3. 将缓冲区应用于现有几何图形并获取外环（JTS库使这变得非常容易:)）。

于 2013-08-13T10:14:22.683 回答