[問題] 已知兩點畫直線求所經格線

[mrbigmouth (拒絕崩潰的蒲公英)]

高中數學不知道丟到哪裡去了只好來此請教 m(_ _)m

現有一方格地圖座標系，
每個座標都代表一個方格，
現在我要計算某個格子有光源、單位時其光線/視線能夠到達何處

依照簡化後的規則，一律起源格的中心點為起點，目標格的中心點為終點
兩點畫線之後，所經的格子邊、格子皆視為其光線/視線會經過的路段
這些格子邊之上、格子範圍內的一切影響源(霧氣、遮蔽物等等)都會影響到光線與視線
(舉例而言，座標1,1到座標2,3之間會經過
  座標1,1
  座標1,1上面的邊
  座標1,2
  座標1,2右邊的邊
  座標2,2
  座標2,2上面的邊
  座標2,3)

數學上，
可以把座標以x2-1的方式求出double後的座標系，
再求出兩點的線性方程式，
最後再一一代入各座標得出會經過哪些格子的邊、格子的範圍。

......但程式要怎麼做到這一過程?@@
已知兩點求出線性方程式?  這種東西沒辦法存到記憶體裡...

有辦法將這過程簡化為程式直接可用的公式嗎?
或是有大能可以提供更方便直接的作法嗎?

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.190.145
※ 編輯: mrbigmouth      來自: 122.116.190.145      (09/26 15:41)
※ 編輯: mrbigmouth      來自: 122.116.190.145      (09/26 15:43)
→ wtvwtvwtv200:想到gcd
→ wtvwtvwtv200:對不起看錯了 （？
→ tyc5116:y=ax+b ?
推 ledia:是要精確列出經過哪幾條邊還是只要一個總數就好?
→ ledia:總數有公式, 列舉的話就真的是慢慢求直線方程式了
→ ledia:查 "矩形對角線 通過 格子" 之類的 有一些資料可以看
推 jimmycool:沒有很仔細看題目, 但是感覺可以用類似DDA的演算法走
→ jimmycool:http://goo.gl/FtAyt
→ mrbigmouth:需要精確知道哪些邊跟哪些格子  然後才能去取其上的障
→ mrbigmouth:礙物/阻擾物來計算光線/視線的受干擾情形
→ mrbigmouth:DDA演算法的確值得參考  我再思考一下
→ mrbigmouth:看起來我之前儲存障礙物的資料結構需要改進...
推 bigpigbigpig:不考慮 Bresenham 畫直線演算法嗎？
→ mrbigmouth:謝謝大家的回答 最後是用修改後的Bresenham(?)解決
→ mrbigmouth:http://ppt.cc/rVDh
→ mrbigmouth:不過這網址給的程式碼不知為啥...x,y好像是反過來的
→ mrbigmouth:老實說這演算法跟原本的Bresenham演算法看起來沒啥關係
→ mrbigmouth:除了累進錯誤法這點一樣