mysql - 确定存储在 MySQL 中的不断扩展的二维网格中最接近的自由 X/Y 坐标集

Question

我有一个非常基本的 MySQL 表，其中为网格内的图 block 存储了 X 和 Y 坐标。网格的中心是 0,0，可以在任何方向创建图 block 。如果该坐标存在于 MySQL 表中，则认为它们已被“占用”。

+---------+------------+------------+
| tile_id | position_x | position_y |
+---------+------------+------------+
|       1 |          0 |          0 |
|       2 |          1 |          0 |
|       3 |          0 |          1 |
|       4 |          1 |          1 |
|       5 |         -1 |         -1 |
+---------+------------+------------+

我需要将一组 4 个图 block (作为正方形，而不是矩形)放置到网格中最接近 0,0 的位置。

为了说明 - 需要找到下面的绿色方 block 。

遗憾的是，我什至不确定从哪里开始:(

Answer 1

这是一个单查询解决方案。

对于网格上的任何给定正方形 t，我们可以识别其周围 8 个可能为空的 4 正方形方 block :

如果包含 (0,0) 的 4 个可能的方 block 均不可用，则最接近 (0,0) 的可用方 block 必须与现有的已占用方 block 相邻(因为对于不与现有已占用方 block 相邻的任何可用方 block 正方形，我们可以找到更近的可用瓷砖)。

这意味着我们可以构建一个查询来计算可能的可用方 block 。

要检查我们是否有与方 block t 相邻的可用图 block ，我们可以使用如下查询:

  SELECT t.x AS x1, t.y-2 AS y1, t.x+1 AS x2, t.y-1 AS y2, LEAST(ABS(x1),ABS(x2))+LEAST(ABS(y1),ABS(y2)) AS distance
  FROM tiles t
  LEFT JOIN tiles t1 ON (t.x = t1.x OR t.x+1 = t1.x) AND (t.y-2 = t1.y OR t.y-1 = t1.y)
  WHERE t1.tile_id IS NULL

这将确定 t1 位置的可用图 block 相对于所取方 block 的左、上、右和下坐标，以及距 (0,0) 的曼哈顿距离。

接下来我们需要所有 8 个位置的可用图 block 的并集。我们还需要检查包含 (0,0) 的 4 个可能可用的图 block ，因为它们不一定与现有的已占用方 block 相邻。

SELECT *, LEAST(ABS(x1),ABS(x2))+LEAST(ABS(y1),ABS(y2)) AS distance
FROM (
  SELECT t.x   AS x1, t.y-2 AS y1, t.x+1 AS x2, t.y-1 AS y2
  FROM tiles t
  LEFT JOIN tiles t1 ON (t.x   = t1.x OR t.x+1 = t1.x) AND (t.y-2 = t1.y OR t.y-1 = t1.y)
  WHERE t.y <= 0 AND t1.tile_id IS NULL

  UNION ALL

  SELECT t.x+1 AS x1, t.y-1 AS y1, t.x+2 AS x2, t.y   AS y2
  FROM tiles t
  LEFT JOIN tiles t2 ON (t.x+1 = t2.x OR t.x+2 = t2.x) AND (t.y-1 = t2.y OR t.y   = t2.y)
  WHERE t.x >= 0 AND t2.tile_id IS NULL

  UNION ALL

  SELECT t.x+1 AS x1, t.y   AS y1, t.x+2 AS x2, t.y+1 AS y2
  FROM tiles t
  LEFT JOIN tiles t3 ON (t.x+1 = t3.x OR t.x+2 = t3.x) AND (t.y   = t3.y OR t.y+1 = t3.y)
  WHERE t.x >= 0 AND t3.tile_id IS NULL

  UNION ALL

  SELECT t.x   AS x1, t.y+1 AS y1, t.x+1 AS x2, t.y+2 AS y2
  FROM tiles t
  LEFT JOIN tiles t4 ON (t.x   = t4.x OR t.x+1 = t4.x) AND (t.y+1 = t4.y OR t.y+2 = t4.y)
  WHERE t.y >= 0 AND t4.tile_id IS NULL

  UNION ALL

  SELECT t.x-1 AS x1, t.y+1 AS y1, t.x   AS x2, t.y+2 AS y2
  FROM tiles t
  LEFT JOIN tiles t5 ON (t.x-1 = t5.x OR t.x   = t5.x) AND (t.y+1 = t5.y OR t.y+2 = t5.y)
  WHERE t.y >= 0 AND t5.tile_id IS NULL

  UNION ALL

  SELECT t.x-2 AS x1, t.y   AS y1, t.x-1 AS x2, t.y+1 AS y2
  FROM tiles t
  LEFT JOIN tiles t6 ON (t.x-2 = t6.x OR t.x-1 = t6.x) AND (t.y   = t6.y OR t.y+1 = t6.y)
  WHERE t.x <= 0 AND t6.tile_id IS NULL

  UNION ALL

  SELECT t.x-2 AS x1, t.y-1 AS y1, t.x-1 AS x2, t.y   AS y2
  FROM tiles t
  LEFT JOIN tiles t7 ON (t.x-2 = t7.x OR t.x-1 = t7.x) AND (t.y-1 = t7.y OR t.y   = t7.y)
  WHERE t.x <= 0 AND t7.tile_id IS NULL

  UNION ALL

  SELECT t.x-1 AS x1, t.y-2 AS y1, t.x   AS x2, t.y-1 AS y2
  FROM tiles t
  LEFT JOIN tiles t8 ON (t.x-1 = t8.x OR t.x   = t8.x) AND (t.y-2 = t8.y OR t.y-1 = t8.y)
  WHERE t.y <= 0 AND t8.tile_id IS NULL

  UNION ALL

  SELECT 0 AS x1, -1 AS y1, 1 AS x2, 0 AS y2
  FROM dual
  WHERE NOT EXISTS (
    SELECT 1
    FROM tiles
    WHERE (x = 0 OR x = 1) AND (y = -1 OR y = 0)
  )

  UNION ALL

  SELECT 0 AS x1, 0 AS y1, 1 AS x2, 1 AS y2
  FROM dual
  WHERE NOT EXISTS (
    SELECT 1
    FROM tiles
    WHERE (x = 0 OR x = 1) AND (y = 0 OR y = 1)
  )

  UNION ALL

  SELECT -1 AS x1, 0 AS y1, 0 AS x2, 1 AS y2
  FROM dual
  WHERE NOT EXISTS (
    SELECT 1
    FROM tiles
    WHERE (x = -1 OR x = 0) AND (y = 0 OR y = 1)
  )

  UNION ALL

  SELECT -1 AS x1, -1 AS y1, 0 AS x2, 0 AS y2
  FROM dual
  WHERE NOT EXISTS (
    SELECT 1
    FROM tiles
    WHERE (x = -1 OR x = 0) AND (y = -1 OR y = 0)
  )
) z
ORDER BY distance
LIMIT 1

为简洁起见，我使用了 x 和 y 而不是 position_x 和 position_y。我使用 UNION ALL 来提高速度，因为它避免了检查重复行，毕竟我们只需要一个。另一个优化是只检查 t 右侧 x >= 0、t y >= 0 下方的图 block ，依此类推。 x 和 y 列上的索引对于性能应该是至关重要的。

我用你的示例网格测试了它:

+---+---+---+---+---------+
| x1| y1| x2| y2| distance|
+---+---+---+---+---------+
|-2 |  0| -1|  1|        1|
+---+---+---+---+---------+