Fast Voxel Traversal 2D

Question

私は、行が通過するすべてのセルを走査しようとしています。私はFast Voxel Traversal Algorithmが私のニーズに合うように見えましたが、現在は不正確であると感じています。アルゴリズムが示すボクセル座標としての赤い線と点を持つグラフを下に示します。あなたが見ることができるように、それは（5,6）でなければならないので、（4,7）点を除いてほぼ正しいです。私はアルゴリズムを正しく実装しているかどうかわからないので、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

は、誰もあなたが投稿論文を読んで、あなたはそれを正しく実装した場合を把握するための時間を持っていないではありません。

ここに質問があります。使用したアルゴリズムは、実際には線が通過するすべてのセルを決定することを意味するか、または（b）2点間の直線のまともなボクセル近似を形成することを意味しますか？

私は、（b）を実行するBresenham's line algorithmをよく知っています。ここでの画像は、アクションである：細胞の選択は「美的」ですが、ラインが通過する特定の細胞を省略すること

注意。これらを含めると、行が "醜い"となります。

あなたのボクセルラインアルゴリズムでも同様のことが起こっていると思われます。しかし、あなたのデータとBresenham画像を見ると、簡単な解決法が示唆されます。発見された細胞のラインに沿って歩いてください。しかし、対角のステップを作る必要があるときはいつでも、2つの中間細胞を検討してください。次に、線形矩形交差アルゴリズム（hereを参照）を使用して、候補セルのどれを含むべきかを決定します。

Answer 2

私はちょうど完了すると思う、私は別の孤独を使用することにしました。ここで参照されるものdtb's answer on another question。

はここにあなたが0.0でスタートを歩いている実装

def getIntersectPts(strPt, endPt, geom=[0,1,0,0,0,1]): 
''' 
    Find intersections pts for every half cell size 
    ** cell size has only been tested with 1 

    Returns cell coordinates that the line passes through 
''' 

x0 = geom[0] 
y0 = geom[3] 

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

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


dx = (eXIndex - sXIndex) 
dy = (eYIndex - sYIndex) 
xHeading = 1.0 if dx > 0 else -1.0 if dx < 0 else 0.0 
yHeading = 1.0 if dy > 0 else -1.0 if dy < 0 else 0.0 

xOffset = (1 - (math.modf(sXIndex)[0])) 
yOffset = (1 - (math.modf(sYIndex)[0])) 

ptsIndexes = [] 
x = sXIndex 
y = sYIndex 
pt = (x, y) #1st pt 

if dx != 0: 
    m = (float(dy)/float(dx)) 
    b = float(sY - sX * m) 

dx = abs(int(dx)) 
dy = abs(int(dy)) 

if dx == 0: 
    for h in range(0, dy + 1): 
     pt = (x, y + (yHeading *h)) 
     ptsIndexes.append(pt) 

    return ptsIndexes 

#print("m {}, dx {}, dy {}, b {}, xdir {}, ydir {}".format(m, dx, dy, b, xHeading, yHeading)) 
#print("x {}, y {}, {} {}".format(sXIndex, sYIndex, eXIndex, eYIndex)) 

#snap to half a cell size so we can find intersections on cell boundaries 
sXIdxSp = round(2.0 * sXIndex)/2.0 
sYIdxSp = round(2.0 * sYIndex)/2.0 
eXIdxSp = round(2.0 * eXIndex)/2.0 
eYIdxSp = round(2.0 * eYIndex)/2.0 
# ptsIndexes.append(pt) 
prevPt = False 
#advance half grid size 
for w in range(0, dx * 4): 
    x = xHeading * (w/2.0) + sXIdxSp 
    y = (x * m + b) 
    if xHeading < 0: 
     if x < eXIdxSp: 
      break 
    else: 
     if x > eXIdxSp: 
      break 

    pt = (round(x), round(y)) #snapToGrid 
    # print(w, x, y) 

    if prevPt != pt: 
     ptsIndexes.append(pt) 
     prevPt = pt 
#advance half grid size 
for h in range(0, dy * 4): 
    y = yHeading * (h/2.0) + sYIdxSp 
    x = ((y - b)/m) 
    if yHeading < 0: 
     if y < eYIdxSp: 
      break 
    else: 
     if y > eYIdxSp: 
      break 
    pt = (round(x), round(y)) # snapToGrid 
    # print(h, x, y) 

    if prevPt != pt: 
     ptsIndexes.append(pt) 
     prevPt = pt 

return set(ptsIndexes) #elminate duplicates 

Answer 3

ボクセル、あなたが想定しているように見えるとして、すなわち最初のボクセルがない-0.5から0.5まで、0.0から1.0への領域にまたがるです。つまり、破線で表示されているものであり、実線ではありません。

ボクセルを使いたい場合は、最初のmaxXとmaxYの計算を修正する必要があります。