0

我正在设计一种算法来测试网格上的单元格是否相邻。问题是单元格不在平面网格上。它们位于多级网格上，如下图所示。

Level 1 (Top Level)
| - - - - - |
| A | B | C |
| - - - - - |
| D | E | F |
| - - - - - |
| G | H | I |
| - - - - - |


Level 2
| -Block A- | -Block B- |
| 1 | 2 | 3 | 1 | 2 | 3 |
| - - - - - | - - - - - |
| 4 | 5 | 6 | 4 | 5 | 6 |   ...
| - - - - - | - - - - - |
| 7 | 8 | 9 | 7 | 8 | 9 |
| - - - - - | - - - - - |
| -Block D- | -Block E- |
| 1 | 2 | 3 | 1 | 2 | 3 |
| - - - - - | - - - - - |
| 4 | 5 | 6 | 4 | 5 | 6 |   ...
| - - - - - | - - - - - |
| 7 | 8 | 9 | 7 | 8 | 9 |
| - - - - - | - - - - - |
      .           .
      .           .
      .           .

该图是根据我的实际需要简化的，但概念是相同的。有一个顶层块，其中包含许多单元格（第 1 层）。每个块进一步细分为更多单元（第 2 级）。对于我的项目，这些单元格进一步细分为 3、4 和 5 级，但对于这个问题，我们只坚持两个级别。

我正在以“A8、A9、B7、D3”的形式接收我的函数的输入。这是一个单元格 ID 列表，其中每个单元格 ID 的格式为 (level 1 id)(level 2 id)。

让我们首先比较 2 个单元格，A8 和 A9。这很容易，因为它们在同一个街区。

private static RelativePosition getRelativePositionInTheSameBlock(String v1, String v2) {
    RelativePosition relativePosition;

    if( v1-v2 == -1 ) {
        relativePosition = RelativePosition.LEFT_OF;
    }
    else if (v1-v2 == 1) {
        relativePosition = RelativePosition.RIGHT_OF;
    }
    else if (v1-v2 == -BLOCK_WIDTH) {
        relativePosition = RelativePosition.TOP_OF;
    }
    else if (v1-v2 == BLOCK_WIDTH) {
        relativePosition = RelativePosition.BOTTOM_OF;
    }
    else {
        relativePosition = RelativePosition.NOT_ADJACENT;
    }
    return relativePosition;
}

可以通过检查 A 是否为 BLOCK_WIDTH 的倍数以及 B 是否为 (A-BLOCK_WIDTH+1) 来进行 A9 - B7 比较。或者只是简单地检查 A/B 对是 3-1、6-4 还是 9-7 以获得更好的可读性。

对于 B7 - D3，它们不相邻，但 D3 与 A9 相邻，因此我可以进行与上述类似的邻接测试。

因此，远离小细节，着眼于大局。这真的是最好的方法吗？请记住以下几点：

  • 我实际上有 5 个级别而不是 2 个级别，所以我可能会得到一个像“A8A1A、A8A1B、B1A2A、B1A2B”这样的列表。
  • 添加一个新单元格进行比较仍然需要我比较它之前的所有其他单元格（似乎我可以为这一步做的最好的事情是 O(n)）
  • 这些单元格并非都是 3x3 块，对于我的示例来说就是这样。它们可以是 MxN 块，对于不同的级别具有不同的 M 和 N。
  • 在上面我当前的实现中，如果单元格在相同的块中，如果它们在单独的水平相邻块中，或者它们是否在单独的垂直相邻块中，我有单独的函数来检查相邻性。这意味着在为下面的图层调用其中一个函数之前，我必须知道当前级别的两个块的位置。

从必须在不同级别处理不同边缘情况的多个函数以及具有 5 级嵌套 if 语句的复杂性来判断。我想知道另一种设计是否更合适。也许是一个更递归的解决方案，使用其他数据结构，或者可能将整个多级网格映射到一个单级网格（我的快速计算给了我大约 700,000 多个原子单元 ID）。即使我走这条路，从多级映射到单级本身也是一项不平凡的任务。

4

3 回答 3

0

计算并比较最低级别的绝对 x 和 y 坐标。

例如（假设int index0A 为 = 0，B 为 1，...且index1= 0...8）：

int x = (index0 % 3) * 3 + index1 % 3;
int y = (index0 / 3) * 3 + index1 / 3;

一般来说，给定

int[] WIDTHS;   // cell width at level i  
int[] HEIGHTS;  // cell height at level i

// indices: cell index at each level, normalized to 0..WIDTH[i]*HEIGHT[i]-1
int getX (int[] indices) {
  int x = 0;
  for (int i = 0; i < indices.length; i++) {
     x = x * WIDTHS[i] + indices[i] % WIDTHS[i];
  }
  return x;
}

int getY (int[] indices) {
  int y = 0;
  for (int i = 0; i < indices.length; i++) {
     y = y * HEIGHTS[i] + indices[i] / WIDTHS[i];
  }
  return x;
}
于 2012-06-22T21:09:34.053 回答
0
  • 我实际上有 5 个级别而不是 2 个级别，所以我可能会得到一个像“A8A1A、A8A1B、B1A2A、B1A2B”这样的列表。
  • 添加一个新单元格进行比较仍然需要我比较它之前的所有其他单元格（似乎我可以为这一步做的最好的事情是 O(n)）
  • 这些单元格并非都是 3x3 块，对于我的示例来说就是这样。它们可以是 MxN 块，对于不同的级别具有不同的 M 和 N。

我认为这些点没有问题：如果一个单元格在最高级别不相邻，那么我们可以在此处停止计算，并且我们不必计算较低级别的邻接。如果只有五个级别，那么您最多可以进行五个邻接计算，这应该没问题。

  • 在上面我当前的实现中，如果单元格在相同的块中，如果它们在单独的水平相邻块中，或者它们是否在单独的垂直相邻块中，我有单独的函数来检查相邻性。这意味着在为下面的图层调用其中一个函数之前，我必须知道当前级别的两个块的位置。

你应该尝试重写这个。应该只有两种方法：一种计算两个单元格是否相邻，另一种计算两个单元格在给定级别是否相邻：

  • RelativePosition isAdjacent(String cell1, String cell2);
  • RelativePosition isAdjacentAtLevel(String cell1, String cell2, int level);

该方法为每个级别isAdjacent调用该方法。isAdjacentAtLevel我不确定是否cell1或cell2总是包含所有级别的信息，但isAdjacent可以分析给定的单元格字符串并相应地调用适当的级别邻接检查。当两个单元格在特定级别不相邻时，不需要检查所有更深的级别。

该方法isAdjacentAtLevel应该做：查找给定级别的M和N，从给定级别中提取信息cell1并cell2执行邻接计算。每个级别的计算应该相同，因为每个级别本身具有相同的块结构。

于 2012-06-22T21:10:02.900 回答
0

您可以使用空间填充曲线，例如 peano 曲线或 z morton 曲线。

于 2012-06-22T22:30:51.577 回答