作者mrbigmouth (拒絕崩潰的蒲公英)
看板Prob_Solve
標題[問題] 已知兩點畫直線求所經格線
時間Wed Sep 26 15:39:19 2012
高中數學不知道丟到哪裡去了只好來此請教 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)
1F：→ wtvwtvwtv200:想到gcd 09/26 18:43
2F：→ wtvwtvwtv200:對不起看錯了 （？ 09/26 18:45
3F：→ tyc5116:y=ax+b ? 09/26 19:55
4F：推 ledia:是要精確列出經過哪幾條邊還是只要一個總數就好? 09/26 21:54
5F：→ ledia:總數有公式, 列舉的話就真的是慢慢求直線方程式了 09/26 21:54
6F：→ ledia:查 "矩形對角線 通過 格子" 之類的 有一些資料可以看 09/26 21:55
7F：推 jimmycool:沒有很仔細看題目, 但是感覺可以用類似DDA的演算法走 09/27 12:07
9F：→ mrbigmouth:需要精確知道哪些邊跟哪些格子 然後才能去取其上的障 09/27 13:05
10F：→ mrbigmouth:礙物/阻擾物來計算光線/視線的受干擾情形 09/27 13:05
11F：→ mrbigmouth:DDA演算法的確值得參考 我再思考一下 09/27 13:23
12F：→ mrbigmouth:看起來我之前儲存障礙物的資料結構需要改進... 09/27 13:36
13F：推 bigpigbigpig:不考慮 Bresenham 畫直線演算法嗎？ 09/28 13:41
14F：→ mrbigmouth:謝謝大家的回答 最後是用修改後的Bresenham(?)解決 10/03 13:13
16F：→ mrbigmouth:不過這網址給的程式碼不知為啥...x,y好像是反過來的 10/03 13:14
17F：→ mrbigmouth:老實說這演算法跟原本的Bresenham演算法看起來沒啥關係 10/03 13:17
18F：→ mrbigmouth:除了累進錯誤法這點一樣 10/03 13:17