algorithm - 寻找距离房间最小连接距离的点

Question

我正在实现一种算法来查找一组房间中的最小跨度走廊。目前我已经弄清楚了算法，我只是想实现它。其中一部分涉及找到给定房间的所谓“特殊点”。矩形的“特殊点”是到另一个矩形的最远点的距离最短的点。例如:

房间 R1 的特殊点是 v6 或 v7，因为它们到 R1 以外的矩形中最远点的最小距离相同。同样，矩形 R8 的特殊点是 v13 或 v14，因为它们到 R8 以外的矩形中最远点的最小距离相同。目前我有邻接列表中表示的点，列表中的每个相邻点。此外，我在邻接列表中有每个房间，每个房间的边界点都是值。我也有它所属的每个房间的每一点。

目前我正在通过查看到该点周围每个矩形中最远点的距离来计算特殊点。虽然这很快，但在以下示例中显然失败了:

由于我当前的实现会将 V1 和 V2 识别为 R9 特殊点的连接，当显然 V2 是特殊点时(因为从 V2 到 R3 中最远点的距离明显小于从 V1 到 R3 中最远点的距离R2 中的最远点)。我可以通过计算到图中所有矩形的最远点的距离并选择最小值来实现它，但是我觉得这样做有更有效的方法。我的想法是围绕某种方式对房间进行排序，并且只检查一些房间，但是我仍然没有完整的算法。有什么想法吗？

提前致谢。

Answer 1

总而言之，我建议从源矩形上的所有点同时运行 Dijkstra 算法，并修改停止条件。该算法在搜索过程中跟踪到目前为止找到的当前最低特殊距离，并且不会进一步搜索已经比当前最低特殊距离更远的点。下面的一些伪代码，它使用字典来存储目标点=>(最佳距离，源点)映射。

enqueue all points on source rectangle
special distance = infinity
while (queue not empty) {
    point = dequeue
    if (distance to point < best distance found to point AND 
        distance to point < special distance) {
        best distance found to point = distance to point
        rect = rectangle of point
        if (all points found in rect) {
            special distance to this rect = max(distances found to this rect)
            if (special distance to this rect < special distance) {
                special distance = special distance to this rect
            }
        } 
    }
}

以下激励细节:

你可以运行Dijkstra's algorithm找到从源矩形上的每个源点到一组目标点的所有点。本质上，Dijkstra 的算法是广度优先搜索，如果它满足从源点到该点的最短路径条件，您只能从队列头部的点进一步搜索。

如果你使用这个条件，你会找到到所有点的最短路径。然后，您可以计算每个目标矩形的最长距离，并取其中的最小值——源点的“特殊距离”(然后对源矩形上的每个点重新运行并找到最低的特殊距离)。然而，这工作量太大，因为您将在搜索中包含很多远离源点且不需要考虑的点。

您可以做的是保持算法运行期间找到的当前最低特殊距离，方法是在找到矩形的所有点时发现并相应地更新当前最低特殊距离(它以一些高数开始，例如 C 中的 INT_MAX)。然后，您通过说它们与源点的距离也必须小于当前最低特殊距离来增加向前移动点的条件(显然，如果当前点比当前最低特殊距离更远，那么您不能做任何事情考虑从中引出的路径会更好。)

如果您要为每个矩形寻找特殊点，您可能需要考虑运行 Floyd–Warshall algorithm ，这将计算每对点之间的最短距离。