四向导航算法

Question

考虑一个矩形帆布,包含随机大小和位置的矩形.要在这些矩形之间导航,用户可以使用四个箭头:向上,向下,向左,向右.

您是否熟悉任何可以产生相当简单的用户体验的导航算法？

我遇到了一些解决方案,但它们似乎都不合适.我知道没有解决方案是"理想的".但是,我正在寻找的算法类型是用于仅使用箭头键在桌面上的图标之间导航的类型.

Answer 1

[EDIT 21/5/2013：正如Gene在评论中所指出的，我的加权方案实际上并不保证每个矩形都可以与其他矩形相通-只是每个矩形都将在每个方向上都连接到其他某个矩形。]

一个很好的方法是使用最大加权二分匹配。

我们想要做的是建立一个定义函数f（r，d）的表，该函数返回用户当前在矩形r处以及命中方向d（上，下，左或右）将移动到的矩形。我们希望此函数具有一些不错的属性，例如：

1. 必须有可能从每个其他矩形到达每个矩形
2. 依次向左或向右按​​，反之亦然，或者向上然后向下拉，反之亦然，应该将用户留在同一位置
3. 按下例如向左按钮会将用户带到左侧的矩形（这很难准确说明，但是我们可以使用评分系统来衡量质量）

对于每个矩形，在图形中创建4个顶点：对于在该矩形处可以按下的每个可能的关键点。对于一个特定的矩形r，叫他们ř _ü，R _d，R _大号和r _{- [R} 。为每对矩形r和s创建4条边：

• （r _U，s _D）
• （r _D，s _U）
• （r _L，s _R）
• （r _R，s _L）

此图具有2个相连的组件：一个包含所有U和D顶点，另一个包含所有L和R顶点。每个分量都是二分的，因为例如没有U顶点连接到另一个U顶点。实际上，我们可以分别在每个组件上运行最大加权二分匹配，尽管在分组后，例如在U顶点和L顶点以及D顶点和R顶点进行分组后，只需在整个图形上运行一次就更容易了。

根据使一对矩形通过一对键相连的意义，为每个边缘分配一个非负的权重。您可以自由选择此计分函数的形式，但可能应该是：

• 与矩形之间的距离成反比（您可以使用矩形中心之间的距离），并且
• 与矩形的中心之间的角度与所需的水平线或垂直线有多远成反比，并且
• 只要矩形的方向错误（例如，如果边缘（r _U，s _D）如果r的中心实际上在s的中心之上），则为0。另外，您也可以删除这些零权重边缘。

此功能试图满足顶部的要求3。

[EDIT＃2 24/5/2013：下面添加了一个示例功能。]

这是满足这些属性的示例函数的C-ish伪代码。它采用2个矩形的中心点和从矩形1开始的方向（从矩形2开始的方向始终与此方向相反）：

const double MAXDISTSQUARED = /* The maximum possible squared distance */;
const double Z = /* A +ve number. Z > 1 => distance more important than angle */

// Return a weight in the range [0, 1], with higher indicating a better fit.
double getWeight(enum direction d, int x1, int y1, int x2, int y2) {
    if (d == LEFT  && x1 < x2 ||
        d == RIGHT && x1 > x2 ||
        d == UP    && y1 < y2 ||
        d == DOWN  && y1 > y2) return 0;

    // Don't need to take sqrt(); in fact it's probably better not to
    double distSquared = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    double angle = abs(atan2(x1 - x2, y1 - y2));   // 0 => horiz; PI/2 => vert
    if (d == UP || d == DOWN) angle = PI / 2 - angle;
    return 1 - pow(distSquared / MAXDISTSQUARED, Z) * (2 * angle / PI);
}

现在运行最大加权二分匹配。这将试图找到具有最高总权重的一组边缘，以使每个顶点（或至少尽可能多的顶点）与选定的边缘相邻，但是没有一个顶点与一个以上的边缘相邻。（如果我们允许一个顶点与多个边相邻，则意味着在该矩形处按下该键将带您到多个目标矩形，这没有意义。）此匹配中的每个边都对应以双向对按键的，所以在按下例如升后降将采取回到原来的地方，在上面自动满足需求2。

到目前为止，唯一不能通过这种方法自动满足的要求是重要的要求，即数字1：它不一定保证每个矩形都可以到达。如果我们仅将“原始”质量得分用作边缘权重，则对于某些配置实际上可能会发生这种情况，例如，当屏幕的四个角中的每个角中都有一个矩形，而在中心处有一个矩形时，中心可能是无法到达。

[2013年5月21日的编辑：正如吉恩所说，我对财产1以下的主张由我提出的新加权方案得到满足是错误的。在许多情况下，每个矩形都是可以到达的，但是通常，您需要解决NP-hard Hamiltonian Cycle问题才能保证这一点。我将保留说明，因为它可以为我们提供一些帮助。在任何情况下，只要检测到子周期，都可以通过向上调整连接的组件之间的权重来解决它。]

为了确保匹配算法始终返回每个矩形都可以到达的匹配，我们需要调整边缘权重，以使匹配永远不可能比具有更多边缘的匹配得分更高。这可以通过将评分函数缩放到0到1之间并将矩形的数量 n 添加到每个边缘的权重上来实现。之所以可行，是因为完全匹配的得分至少为4n ^ 2（即，即使质量得分为0，边缘本身的权重为n，其中权重为4n），而边缘更少的任何匹配的得分最高为4（n-1）（n + 1）= 4n ^ 2-4-严格来说要小一些。

Answer 2

构建一个运动图如下：

• 对于任何方向，尝试去给定方向上最近的矩形，其中心点是当前矩形边的中间。
• 尝试消除循环，例如，从 A 向右移动应该尝试生成与从 A 向右移动不同的矩形。例如，在该图中，绿色的“右”应该是橙色，即使粉红色是最近的中点
• （感谢 biziclop）：如果图中有任何矩形无法到达，则重新映射相邻的矩形之一以到达它，可能是误差最小的矩形。重复直到所有矩形均可到达（我认为该算法将终止......）

然后存储图表并仅使用它来导航。您不想在会议中途更改方向。