math - 网格中的矩形 - 我需要有关边缘情况的帮助

Question

我试图解决的问题如下:

In a 2-D space, Given a grid size and a rectangle, calculate the grid cells
occupied (partially or totally) by the rectangle.

“网格大小”的意思是:“16x16 网格”或“32x32 网格”。所有网格都以坐标原点 (0,0) 为中心。

矩形由 4 个浮点数定义:左侧、顶部、宽度和高度。

此操作的结果始终是一个矩形。我想返回左上角单元格的坐标(即 0,0)，然后是 retangle 向右和向下占据的单元格数(有点像宽度和高度，但对于单元格)

到目前为止，我已经能够编写一个最有效的算法。它首先要做的是计算网格中单个点所在的单元格坐标。然后，给定矩形，我计算它的左上角和右下角在网格上的位置，然后它是一个简单的减法:

-- given a world coordinate, return the coordinates of the cell that would contain it
local function _toGrid(wx, wy)
  return math.floor(wx / __cellSize), math.floor(wy / __cellSize)
end

-- given a box in world coordinates, return a box in grid coordinates that contains it
-- returns the x,y coordinates of the top-left cell, the number of cells to the right and the number of cells down.
local function _toGridBox(l, t, w, h)
  local gl,gt = _toGrid(l, t)      -- top left grid corner
  local gr,gb = _toGrid(l+w, t+h)  -- bottom-right grid corner
  return gl, gt, gr-gl+1, gb-gt+1  -- return top,left,cells to the right, cells to bottom
end

笔记:

源代码是 Lua，但我会接受任何编程语言的解决方案，只要它们是可理解的。

y坐标“增加时向下”；这就是许多屏幕系统的工作方式。我认为这对这个问题并不重要，但不要对此感到困惑)。

在 16x16 网格中，0,0 上的矩形， width =10 和 height =20， gr 将是 0 和 gt 1，所以 _toGrid 将返回 0,0,1,2(1 行，2 列，在 0 ,0 单元格)。

当矩形从内部“接触”(而不是交叉)一个单元格的下侧或右侧时，就会出现问题。在这种情况下， _toGrid 返回比我想要的“多一个单元格”。

例如，如果我将前一个矩形向左移动 6 个像素(因此它位于 10,0 上)，它将“触摸”其包含网格的左侧边框，从 0 到 16。然后 gr 将为 1，返回的数据将为 0,0,2,2。

如果可能的话，我想避免这种情况。对于“从左侧”到 16 的矩形，我希望它保留在第一个网格单元上。我希望它一旦超过 16 就开始“占用下一个单元格” - 例如当它位于 16.00000001 时。

另外，请注意，这仅适用于右侧和底部。左侧和上部按我的意愿工作。例如，一个 左 坐标为 16 的矩形，应该出现在“右边的第二个单元格”，而不是第一个。

我确定解决方案并不复杂，但是我已经考虑了一段时间，但似乎没有找到。任何帮助将不胜感激。

Answer 1

对于底部和右侧，您需要使用 ceil而不是 floor .我不知道任何 Lua，所以这在语法上可能不正确，但你会想要一些类似的东西:

local function _toGridBox(l, t, w, h)
  local gl = math.floor(l / _cellSize)
  local gt = math.floor(t / _cellSize)
  local gr = math.ceil((l+w) / _cellSize)
  local gb = math.ceil((t+h) / _cellSize)
  return gl, gt, gr-gl, gb-gt  -- return top,left,cells to the right, cells to bottom
end

本质上，您的问题是函数 _toGrid对您的目的来说是错误的抽象，因为它总是使用 floor .显然，您将自己锁定在使用该抽象概念上，从而难以得出正确的答案。