4

我正在尝试从绘制点并且部分或全部具有标签的图形 xy 图中提取语义。标签被绘制在“点附近”，以便人们通常可以理解哪个标签与哪个点对应。例如，在此图中，可以清楚地看到哪个标签（数字）属于哪个点（*），并且基于欧几里得距离的算法将起作用。（标签和点没有语义排序 - 例如散点图）

 *1
    *2

        *3

      *4

在拥挤的图中，创作软件/人可以将标签放置在不同的方向以避免重叠。例如在

1**2
 **4
 3

人类读者通常可以计算出哪个标签与哪个标签相关联。

我接受的一种解决方案是创建一个欧几里得距离矩阵并打乱行以获得函数的最小值（例如，对角线或其他启发式距离的平方和）。在第二个示例中（从 NW 角顺时针标记为 a、b、c、d 的点）我们有一个距离矩阵（到 1 dp）

             a   b   c   d
 1ab2    1  1.0 2.0 2.2 1.4    
  dc4    2  2.0 1.0 1.4 2.2
  3      3  2.0 2.2 1.4 1.0
         4  2.2 1.4 1.0 2.0

我们需要给a1 b2 c4 d3. 交换第 3 行和第 4 行给出对角线的最小和。这是一个更复杂的示例，其中简单地选择最近的可能会失败

 *1*2*5
  **4
  3 *6

如果解决了这个问题，那么我将需要处理标签数量可能小于或大于点数的情况。

如果算法是标准的，我将不胜感激开源 Java 的指针（例如 JAMA 或 Apache 数学）

注意：这个 SO 答案将附近的点与路径关联起来并不能很好地作为答案，因为给出了通过这些点的路径。

4

3 回答 3

6

你有一个完整的二部图，一部分是数字，另一部分是点。该图中边的权重是数字和点之间的欧几里得距离。你的任务是找到最小重量的匹配。

这是一个已知问题，并且有一个众所周知的算法，名为Hungarian Algorithm：

来自维基：

给定一个非负 n×n 矩阵，其中第 i 行第 j 列中的元素表示将第 j 个点分配给第 i 个数的成本。我们必须找到将点分配给成本最低的数字。如果目标是找到产生最大成本的分配，则可以通过将每个成本替换为减去成本的最大成本来更改问题以适应设置。

如果我们使用二分图来表述问题，则该算法更容易描述。我们有一个完整的二部图 G=(S, T; E)，有 n 个顶点 (S) 和 n 个点顶点 (T)，每条边都有一个非负成本 c(i,j)。我们希望以最低的成本找到完美的匹配。匈牙利方法是一种组合优化算法，它在多项式时间内解决了分配问题，并预见了后来的原始对偶方法。F

有关详细的算法和代码，您可以查看topcoder 文章 和此pdf可能使用

有一个媒体文件来描述它。（该视频解释了匈牙利算法为何有效）

算法：步骤1：-准备一个成本矩阵。如果成本矩阵不是方阵，则添加一个具有零成本元素的虚拟行（列）。

第 2 步：- 从相应行的所有元素中减去每行中的最小元素。

步骤3：-通过从相应列的所有元素中减去每列的最小元素来进一步修改结果矩阵。从而获得修改后的矩阵。

第 4 步：- 然后，绘制最小数量的水平和垂直线以覆盖结果矩阵中的所有零。让最小的线数量为 N。现在有 2 种可能的情况。

案例 1 - 如果 N=n，其中 n 是矩阵的阶，则可以进行最佳分配。因此进行分配以获得所需的解决方案。

情况 2 - 如果 N 小于 n 则继续执行步骤 5

步骤5：确定矩阵中最小的未覆盖元素（N行未覆盖的元素）。从所有未覆盖元素中减去这个最小元素，并在水平和垂直线的交点处添加相同的元素。从而获得第二个修改矩阵。

第 6 步：- 重复第 (3) 步和第 (4) 步，直到我们得到第 4 步的情况 (1)。

第 7 步：- （进行零分配）连续检查行，直到找到逐行精确的单个零。circle(o) 这个零进行分配。然后在所有零上标记一个 cross(x) 如果位于带圆圈的零的列，表明它们不能被考虑用于将来的分配。以这种方式继续，直到检查完所有的零。对列也重复相同的过程。

第 8 步：- 连续重复第 6 步，直到出现以下情况之一 - (i) 如果没有留下未标记的零，则过程结束或 (ii) 如果在任何列或行中存在多个未标记的零然后，任意圈出未标记的零之一，并在其行或列中剩余零的单元格中标记一个十字。重复该过程，直到矩阵中没有未标记的零。

第 9 步：- 因此，在矩阵的每一行和每一列中恰好有一个标记为圆圈的零。与这些标记的圆零对应的分配将给出最佳分配。

有关详细信息，请参阅 wiki 和http://www.ams.jhu.edu/~castello/362/Handouts/hungarian.pdf

于 2012-04-20T01:31:01.820 回答
2

如果我理解了您的问题，那么您展示的每个示例都有一个独特的最佳解决方案，可以最小化点和标签之间距离的平方和。点和标签之间有指数级的映射，但也许您可以尝试以下方法：

  1. 在多项式时间内，计算每个标签到每个点的距离。在一般图中，您必须解决所有对最短路径问题。在这里，正如 Mikola 指出的那样，您可以使用双重嵌套并使用坐标几何：选择欧几里得距离或曼哈顿距离。

  2. 在多项式时间内，找到点和标签之间的最小成本二分匹配。此问题的解决方案将为您提供点和标签之间的匹配，以最小化总距离。

所有算法（最短路径、欧几里得距离、最小成本二分匹配）都是标准的，可以在 Wikipedia 上找到。

稍微不标准的是，如果您以最低成本找到不止一个二分匹配。如果发生这种情况，您可以尝试所有这些，看看是否有一个匹配可以最小化距离平方和。如果还有平手，我建议您将水平距离视为略短于垂直距离，然后再次运行算法。如果您仍然有联系，则可能没有唯一的解决方案，或者您可能希望将“右侧标签”视为比左侧标签稍微“接近”。

但是当有一个唯一的解决方案时，所有对最短路径遵循最小成本二分匹配应该找到它。

于 2012-04-20T00:33:58.123 回答
1

我还没有看到这种情况下的通用算法。因此，我会务实地解决这个问题：

假设属于某个点的标签始终是最近的（可能与其他标签），您可以定位区域增长算法（参见动画 gif）。迭代每个增长步骤的每个点（红色）（围绕数字标签圈）。增长步长由点和标签之间的最小距离决定。

区域增长

对点和标签使用临时列表。每次找到一个确定的对，删除相应的点和标签。如果有多个最近点（此处：标签 2），则只需跳过标签。通过解决其他点标签组合（此处为标签 3），它们应该在另一个迭代中映射。

在由于整体情况不明确而没有任何进展的迭代之后，您可以定义一种选择方法来解决它们（例如，更喜欢顶部而不是底部，左侧优于右侧）。

于 2012-04-19T17:29:31.820 回答