1

我试图弄清楚如何制作一个超级覆盖 DDA 算法。或者换句话说，一种 DDA 算法将覆盖一条线穿过的所有网格点。见下图。

该图像是我绘制的，可能不是 100% 准确，但它显示了总体思路。我还想注意图像下半部分的示例没有整数开始和结束坐标，这是必要的。

如果您需要知道，我打算将其用于视线光线投射。

我能够实现典型的 DDA 算法，但我的问题是，如何修改它以涵盖所有点？

谢谢！

我当前在 Lua 中的 DDA 算法实现

function dline(x0,y0, x1,y1) -- floating point input
  local dx = x1-x0
  local dy = y1-y0

  local s = math.max(math.abs(dx),math.abs(dy))

  dx = dx/s
  dy = dy/s

  local x = x0
  local y = y0
  local i = 0
  return function() -- iterator intended for a for loop
    if i <= s then
      local rx,ry = x,y
      x = x+dx
      y = y+dy
      i = i+1
      return rx,ry
    end
  end
end
4

2 回答 2

3

对不起，我不经常问问题，主要是因为我不是那么好。但我会告诉你我擅长什么！解决我自己的问题！:D

作为一个注释，我的问题中的图像显示了如果线精确地通过一个点，则线交叉对角线，这个算法没有，但经过一番思考，交叉对角线对我来说是不可取的。

感谢这篇文章，我找到了。

这是新的实现

function line(x0,y0, x1,y1)
  local vx,vy = x1-x0, y1-y0           -- get the differences
  local dx = math.sqrt(1 + (vy/vx)^2)  -- length of vector <1, slope>
  local dy = math.sqrt(1 + (vx/vy)^2)  -- length of vector <1/slope, 1>

  local ix,iy = math.floor(x0), math.floor(y0) -- initialize starting positions
  local sx,ex -- sx is the increment direction
              -- ex is the distance from x0 to ix
  if vx < 0 then
    sx = -1
    ex = (x0-ix) * dx
  else
    sx = 1
    ex = (ix + 1-x0) * dx -- subtract from 1 instead of 0
                          -- to make up for flooring ix
  end

  local sy,ey
  if vy < 0 then
    sy = -1
    ey = (y0-iy) * dy
  else
    sy = 1
    ey = (iy + 1-y0) * dy
  end

  local done = false
  local len  = math.sqrt(vx^2 + vy^2)
  return function()
    if math.min(ex,ey) <= len then
      local rx,ry = ix,iy
      if ex < ey then
        ex = ex + dx
        ix = ix + sx
      else
        ey = ey + dy
        iy = iy + sy
      end
      return rx,ry
    elseif not done then -- return the final two coordinates
      done = true
      return ix,iy
    end
  end
end

于 2013-09-19T04:59:11.910 回答
1

您可以通过简单地在相邻方格上添加一些检查，以与普通 dda 算法相同的时间复杂度来完成此操作。

于 2013-09-18T20:13:49.550 回答