超覆盖DDA算法

Question

我想弄清楚如何做一个超覆盖DDA算法。或者换句话说，一种DDA算法，它将覆盖由一条线交叉的所有网格点。请看下面的图片。

​

​

这张照片是我画的，可能不是100%的准确，但它显示了一般的想法。我还想指出的例子，在图像的下半部没有整数开始和结束坐标，这是必要的。

如果你需要知道，我打算使用这个视线光线投射。

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

谢谢!

DDA算法在Lua中的实现

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

Answer 1

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

值得注意的是，我问题中的图像显示了如果这条线精确地穿过一个点，则该算法会显示横穿对角线的直线，但是经过一些思考后，对我来说交叉对角线是不可取的。

多亏了我找到的这文章。

这是新的实现

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

​

​

Answer 2

您可以通过简单地在相邻的平方上添加几个检查来实现与普通dda算法相同的复杂度。