确定存储在MySQL中的不断扩展的2D网格中最接近的一组X/Y坐标

Question

我有一个非常基本的MySQL表,其中为网格中的图块存储X和Y坐标.网格的中心是0,0并且可以在任何方向上创建切片.如果坐标存在于MySQL表中,则认为它们被"采用".

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

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

为了说明 - 需要找到下面的绿色瓷砖.

可悲的是,我甚至不确定从哪一个开始:(

Answer 1

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

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

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

这意味着我们可以对所取的方块构建查询来计算可能的可用图块。

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

  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这将确定相对于所取方块的位置中可用图块的左、上、右和下坐标，以及距 (0,0) 的曼哈顿距离。

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

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

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

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

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