寻找Dijkstra算法的起始顶点？

Question

假设我在公园里实施Dijkstra算法。有点和这些点之间的连接; 这些指定用户可以行走的有效路径（例如人行道）。

现在想象一下，用户在草地上（即不在路径上），并希望导航到另一个位置。问题不在于Dijkstra算法（它正常工作），而是确定从哪个顶点开始。

以下是问题的图片：（暂时忽略虚线）

黑线显示Dijkstra算法中的边缘；同样，紫色圆圈显示顶点。 人行道为灰色。 草是绿色的。 用户位于红星处，并希望到达橙色X。

如果我天真地寻找最近的顶点并将其用作起点，则用户通常会被引导到次优路径，该路径在开始时需要更远地步行到达目的地（即红色实线路径）。

蓝色实线路径是我的算法理想情况下提出的最佳路径。

注意事项：

假设没有路径跨越其他路径。

当导航到起始点时，用户不应越过路径（例如人行道）。

在上面的图像中，从星星出来的第一条线段是动态创建的，仅用于帮助用户。 星号不是图中的顶点（因为用户可以在草地区域内的任何地方），从星号到顶点的线段仅用于显示，以便用户知道如何到达图中的第一个有效顶点。

我如何高效正确地实现这一点？

想法＃1：找到包围多边形

如果我找到了围绕起始点的最小多边形，则现在可以为Dijkstra算法创建新路径，从起始点（暂时添加为新顶点）到组成多边形的每个顶点。 在上面的示例中，多边形有6个面，因此这意味着创建6条连接到其每个顶点的新路径（即蓝色虚线）。 然后，我将能够运行Dijkstra算法，并且它将轻松确定蓝色实线是最佳路径。

该方法的问题在于确定哪些顶点组成了围绕我的点的最小多边形。 我不能为图中的每个顶点创建新路径，否则我也会得到红色虚线，这完全违背了使用Dijkstra算法的目的（我不应该允许越过人行道）。 因此，我必须注意仅将路径创建到封闭多边形的顶点。 是否有此算法？

这个解决方案还有一个复杂的问题：假设用户现在从紫色闪电开始。它没有封闭的多边形，但算法仍应通过连接它到右上角的3个点来工作。一旦连接到这些点，运行Dijkstra算法就很容易了。
更新：我们希望连接到这3个点中的一个，而不是绕着一切走到达橙色X，因为我们想要最小化在未铺设道路上的步行路程。（注意：只有当你从多边形外部开始时，这才是一个约束条件。如果在多边形内部行走，我们不关心你在草地上走多久）。

如果这是正确的解决方案，请将其算法作为答案发布。

否则，请发布更好的解决方案。

- Senseful

---

我真的不太理解。有效路径有哪些限制？如果你从外面开始，为什么不能直接沿着外面走到目标处？ - Niklas B.

还有，期望的运行时间是多少？O((n+m) * log n)，像Dijkstra算法一样吗？ - Niklas B.

这里有一些关于编程的内容，包括维基百科(http://en.wikipedia.org/wiki/Point_location)和stackoverflow(http://stackoverflow.com/questions/10915791/how-can-a-find-a-face-containing-a-predefined-point-when-i-have-a-planar-graph-e)。 - G. Bach

Answer 1

你可以从目标点开始运行 Dijkstra 算法，以找到它与所有顶点的距离。

现在我们考虑从“内部”在草地上开始的情况。我们想要找到我们可以通过一条直线到达且不穿越任何边缘的所有顶点。为此，我们可以将表示边缘的所有线段和连接起点到每个顶点的线段组合在一起，使用扫描线算法来查找起始点-顶点线是否与任何边缘相交。

或者，您可以使用任何平面点定位的离线算法，它们也可以使用扫描线。我认为这符合问题中提出的更抽象算法的精神，因为它报告了环绕该点的多边形。

然后，我们只需要找到连接线到起点不与任何边缘相交且 d(vertex, target) + d(vertex, start) 之和最小的顶点即可。

当顶点在图形外部时的过程有些不太明确，但我想完全相同的想法也可以奏效。只需记住，如果目标在边界上，则有可能绕着整个图形走到目标位置，就像您的示例一样。

每次查询可能需要 O((n+m) log m) 的时间来实现。如果您将 all-pairs shortest path algorithm 作为预处理步骤运行，并使用在线点定位算法，则可以以对数时间查询，代价是存储信息以加快最短路径查询所需的空间（如果仅存储所有距离对，则为二次）。

我认为简单的平面点定位与扫描线方法非常相似，只是使用 persistent BST 存储所有扫描线状态。

- Niklas B.

---

关键在于将所有顶点的 d(start,vertex) + d(vertex,end) 最小化。你可以强调这一点。 - bgschiller

@bgschiller 我不会说那是关键。那只是微不足道的部分。关键是找到顶点的有效候选项。 - Niklas B.

Answer 2

我不确定为什么您要费心寻找起始顶点，因为您已经有一个。您（用户）所站立的点本身就是另一个顶点。因此，现在真正的问题是找到从您的起点到封闭多边形图中任何其他点的距离。一旦您做到了这一点，就可以简单地运行Dijkstra或另一个最短路径算法方法，如A*、BFS等，以找到到达目标点的最短路径。

关于这一点，我认为您最好为这个问题实现A*，因为公园涉及到像树、游乐场、池塘（有时候）等事物。因此，您需要使用一个考虑了这些因素的最短路径算法，并且A*是一种使用这些因素确定最短路径的算法之一。

找到从起点到图的距离：

寻找新顶点到其他顶点的距离问题可以通过仅查找具有最接近起始点的x或y坐标的点来解决。因此，该算法必须找到形成围绕起始点的一种封闭形式的点，即包含该点的最小面积多边形。因此，正如@Niklas B所建议的那样，平面点算法（经过一些修改）可能能够完成这项任务。我正在研究扫描线算法，但它仅适用于线段，因此无法使用（仍然值得一试，通过修改可能能够给出正确答案）。

您还可以决定分阶段实现此算法，因此首先找到与当前点最接近的y坐标的点（负和正y都要使用绝对值），然后在这些点中，找到与当前点最接近的x坐标的点，这应该为您提供形成多边形的点集。然后，这些是您用来找到从起点到图形的距离的点。

- smac89

---

但是，您如何确保在将起点连接到其他顶点之一时不会越过路径？换句话说，您隐含引入的新顶点的边缘是什么？ - Niklas B.

这就是我所提到的，问题不在于找到一个起点，而是如何确定从新顶点到所有其他点的距离。一旦你有了这个，你就可以运行你选择的最短路径算法来找到最短路径。你也不需要担心路径交叉，因为一个好的最短路径算法会选择最近的点。所以如果有两条路径交叉，最近路径上的点将被选择。 - smac89

我不同意。看一下这张图：http://imgur.com/P1hz6Oy。十字是起点，圆圈是目标。根据我理解的你提出的算法，它会沿着直线连接两者，但那不是一个有效的路径。 - Niklas B.

@NiklasB。你展示的图中只有一个顶点，因此任何试图从x到圆圈找到最短路径的算法都会失败或不得不穿过路径才能找到。我已经进行了编辑。 - smac89

想象所有的角落都是顶点（有3个）。 - Niklas B.