作者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