0

目前我正在研究最小走廊长度算法，部分设置涉及列出问题中所有相邻点的列表。目前我有两个数组：一个用 x 坐标上的相邻点排序，另一个用 y 坐标上的点排序。此外，我通过简单地查看给定两个列表的附近点来找到邻接，如果这些点具有相同的 y（在按 x 相邻排序的列表上），那么它们位于同一条线上。同样，如果它们具有相同的 x（在 y 列表上），则位于同一行。

例如，假设我们有以下房间：

图片

然后带有 x 相邻点的列表将具有以下顺序的点：{v1, v2, v3, v4, v5, ... v21, v22}（它们保持与标记相同的顺序）此外，列表与 y 相邻的点将是：{v22, v16, v14, v9, v4, v13, v8, v3, v21, ... v5, v1}（基本上是 y=x 上图形的反映）

如前所述，我通过查看列表中的附近点来找到相邻点。这在大多数情况下都可以正常工作，但是对于以下边缘情况却失败了：

在此处输入图像描述

由于 x-adjacent 列表将具有 {v1, v2, ... v6, v7 ... v11, v12} 并且我的算法会将 v6 和 v7 检测为相邻点。如何检测到这两点之间有一个房间？请注意，我也可以使用一组矩形和顶点上的点。提前致谢。

4

1 回答 1

2

我建议放弃基于位置的方法，因为无法仅根据位置来判断上一个示例中的 v6 和 v7 是否相邻（即连接）。相反，制作一个图形来指示哪些点连接到哪些其他点：这些点将是图形的顶点，并且您在相邻/连接的每对顶点之间添加一条边。

要构建图表，您可以尝试这个算法（就在我的脑海中）：

  1. 创建具有给定顶点且没有边的图
  2. 按 x 坐标对顶点（点）进行分组。创建顶点到组的映射，或以其他方式查找给定顶点所在的组。
  3. 对于每个组，使用该组中的顶点创建一个不相交的集合数据结构。
  4. 遍历矩形的所有垂直边，并且对于每条边，对对应于该边末端的两个顶点的子集执行并集。
  5. 遍历组，并为每个组遍历其子集。对于每个子集，首先按 y 坐标对该子集中的顶点进行排序，然后在图的连续顶点对之间添加边。

然后重复步骤 2-5，切换 x 和 y 坐标的角色（并使用水平边缘而不是垂直边缘）。

自然，这依赖于所有边（线）都是水平或垂直的假设。

于 2013-05-28T00:10:37.847 回答