2

私が解決しようとしている問題は次のとおりです。

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 つの float によって定義されます。

この操作の結果は常に長方形になります。左上のセル (つまり 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 グリッドでは、width=10 とheight=20 の0,0 上の四角形はgr0 とgt1 になるため、_toGrid0,0,1,2 (0,0 セルの 1 行、2 列) が返されます。

この問題は、長方形が内側から 1 つのセルの下側または右側に「接触」する (交差しない) 場合に発生します。その場合、_toGrid私が望むよりも「1 つ多いセル」を返します。

たとえば、前の四角形を左に 6 ピクセル移動すると (つまり 10,0 になります)、それを含むグリッドの左側の境界線に「接触」し、0 から 16 になります。次に、次のgrようになります。 1、返されるデータは 0、0、2、2 になります。

可能であれば、これを避けたいと思います。「左から」16 の長方形の場合、最初のグリッド セルに残しておきたいと思います。16 を超えるとすぐに「次のセルの占有」を開始したいと思います。たとえば、 16.00000001 の場合です。

また、これは右側と下側にのみ適用されることに注意してください。左側と上部は思い通りに機能します。たとえば、左の座標が 16 の四角形は、最初のセルではなく、「右から 2 番目のセル」に表示されます。

解決策は複雑ではないと確信していますが、これについてしばらく考えていて、見つけられないようです。どんな助けでも大歓迎です。

4

1 に答える 1

4

下部と右側には、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です。どうやら、あなたはその抽象化を使用することに自分自身を閉じ込めたので、正しい答えを思い付くのが難しくなりました。

于 2012-08-13T08:18:31.567 に答える