給定圖像表示和解決迷宮的最佳方法是什麼?
給定一張 JPEG 圖像(如上所示),讀取它、將其解析為某種數據結構並解決迷宮問題的最佳方法是什麼?我的第一個本能是逐像素讀取圖像並將其存儲在布爾值列表(數組)中:True
表示白色像素,False
表示非白色像素(可以丟棄顏色)。這種方法的問題是圖像可能不是“像素完美”。我的意思是,如果牆上某處有一個白色像素,它可能會創建一個意想不到的路徑。
另一種方法(經過一番思考後想到)是將圖像轉換為 SVG 文件 - 這是在畫布上繪製的路徑列表。這樣,可以將路徑讀入相同類型的列表(布爾值),其中 True
表示路徑或牆壁,False
表示可行駛的空間。如果轉換不是 100% 準確,並且沒有完全連接所有牆壁,從而產生間隙,則此方法會出現問題。
轉換為 SVG 的另一個問題是線條不是“完美的” “ 直的。這導致路徑是三次貝塞爾曲線。使用由整數索引的布爾值列表(數組),曲線不會輕易轉移,曲線上的所有點都必須計算,但不會與列表索引完全匹配。
我假設雖然其中一種方法可能有效(儘管可能無效),但考慮到如此大的圖像,它們的效率非常低,並且存在更好的方法。這如何最好(最有效和/或複雜性最低) ) 完成了嗎?有沒有最好的方法?
然後是解迷宮。如果我使用前兩種方法中的任何一種,我基本上都會得到一個矩陣。根據 this answer,表示迷宮的好方法是使用樹,解決它的好方法是使用 A* 算法。如何從圖像中創建一棵樹?有什麼想法嗎?
TL;DR
解析的最佳方式是什麼? ta結構?上述結構如何幫助/解決問題?
更新
我已經嘗試使用 numpy
import png, numpy, Queue, operator, itertools def is_white(coord, image): """ 返回 (x, y) 是否近似於一個白色像素。""" a = True for i in xrange(3): if not a: break a = image[coord[1]][coord[0] * 3 + i] > 240 return a def bfs(s, e, i,visited): """ 執行廣度優先搜索。""" frontier = Queue.Queue() while s != e: for d in [(-1, 0 ), (0, -1), (1, 0), (0, 1)]: np = tuple(map(operator.add, s, d)) 如果 is_white(np, i) 和 np 未訪問: frontier.put(np)visited.append(s) s = frontier.get() returnvisited def main(): r = png.Reader(filename = "thescope-134.png") 行、列、像素、元 = r.asDirect() assert meta["planes"] == 3 # 確保文件是 RGB image2d = numpy.vstack(itertools.imap(numpy.uint8, pixel)) start, end = (402, 985), (398 , 27) 打印 bfs(start, end, image2d, [])