距離點和線最近的曼哈頓距離

Question

我想從給定點的最小Manhattan distance的圖像中繪製的線段上找到點。

明顯的方法是獲取線段上的像素，併爲每個像素計算距離以獲得最小值。 但是我們能做得比這更好嗎？

Answer 1

這是一個搜索問題。你需要從你的觀點開始並應用一個breadth first search，直到你達到一行像素爲止。孩子們表示任何像素都應該是正確的 - 左 - 下的鄰居。曼哈頓的距離只不過是目標的深度。

編輯：請記住爲更快的搜索添加一些啓發式法，例如如果所有行像素都在起點的左側;您無需訪問right。爲了進一步減少狀態，線的角度將是另一個需要考慮的事情。