python - 快速体素遍历 2D

Question

我正在尝试遍历一条线经过的所有单元格。我找到了 Fast Voxel Traversal Algorithm这似乎符合我的需要，但我目前发现它不准确。下面是一个带有红线的图表，点作为算法给出的体素坐标。如您所见，它几乎是正确的，除了 (4, 7) 点，因为它应该是 (5,6)。我也不确定我是否正确地实现了算法，所以我将它包含在 Python 中。所以我想我的问题是我的实现是正确的还是有更好的算法？

谢谢

def getVoxelTraversalPts(strPt, endPt, geom):
  Max_Delta = 1000000.0
  #origin
  x0 = geom[0]
  y0 = geom[3]

  (sX, sY) = (strPt[0], strPt[1])
  (eX, eY) = (endPt[0], endPt[1])
  dx = geom[1]
  dy = geom[5]

  sXIndex = ((sX - x0) / dx)
  sYIndex = ((sY - y0) / dy)
  eXIndex = ((eX - sXIndex) / dx) + sXIndex
  eYIndex = ((eY - sYIndex) / dy) + sYIndex

  deltaX = float(eXIndex - sXIndex)
  deltaXSign = 1 if deltaX > 0 else -1 if deltaX < 0 else 0
  stepX = deltaXSign

  tDeltaX = min((deltaXSign / deltaX), Max_Delta) if deltaXSign != 0 else Max_Delta
  maxX = tDeltaX * (1 - sXIndex + int(sXIndex)) if deltaXSign > 0 else tDeltaX * (sXIndex - int(sXIndex))

  deltaY = float(eYIndex - sYIndex)
  deltaYSign = 1 if deltaY > 0 else -1 if deltaY < 0 else 0
  stepY = deltaYSign

  tDeltaY = min(deltaYSign / deltaY, Max_Delta) if deltaYSign != 0 else Max_Delta
  maxY = tDeltaY * (1 - sYIndex + int(sYIndex)) if deltaYSign > 0 else tDeltaY * (sYIndex - int(sYIndex))

  x = sXIndex
  y = sYIndex

  ptsIndexes = []
  pt = [round(x), round(y)]
  ptsIndexes.append(pt)
  prevPt = pt
  while True:
    if maxX < maxY:
        maxX += tDeltaX
        x += deltaXSign
    else:
        maxY += tDeltaY
        y += deltaYSign

    pt = [round(x), round(y)]
    if pt != prevPt:
        #print pt
        ptsIndexes.append(pt)
        prevPt = pt

    if maxX > 1 and maxY > 1:
        break

  return (ptsIndexes)

Answer 1

您正在行走的体素从 0.0 开始，即第一个体素跨越空间从 0.0 到 1.0，而不是您似乎假设的从 -0.5 到 0.5。换句话说，它们是虚线标记的，而不是实线标记的。

如果您希望体素随心所欲，则必须修正初始的 maxX 和 maxY 计算。