计算网格中直线经过的格子

关于在位图上像绘制直线的算法,可以参见:http://free.pages.at/easyfilter/bresenham.html。但是不同于在位图上绘制直线,需要的是:一条直线经过哪些格子。

  1. 假设有p0,p1两个点,位置如下图:
  2. 我们很容易得到连线的方程。首先我们按照在x上取整递增,很容易计算出x=1, 2, 3, 4…时y的值是多少。
  3. 然后对y值取整,所得到(x1,y1),(x2,y2),(x3,y3)…肯定是连线过的格子。
  4. 但是我们遗漏了这种情况,左上格也是连线经过的格子,但由于我们只在x轴上进行取整递增运算,没有被考虑在内。
  5. 在(2)时已经可以知道A点坐标,我们可以斜率来判断连线是否经过上面一格。如果“蓝色线的斜率小于p0-p1的斜率”,说明连线经过了上面一格。
  6. 利用这种方法,可以轻松计算出连线经过的所有格子。

AS3实现的demo:
[kml_flashembed publishmethod="static" fversion="10.0.0" movie="http://www.itamt.com/wp-content/uploads/2011/04/TestLineCrossPoints.swf" width="550" height="400" targetclass="flashmovie"]Get Adobe Flash player

[/kml_flashembed]

源码:

/**
* 返回网格中两个点,连线经过的格子。
* @see  http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
*/
public static function determineTouchedTiles(p0:Point, p1:Point):Vector.
{
var touched:Vector.=new Vector.();
var x0:Number=p0.x;
var y0:Number=p0.y;
var x1:Number=p1.x;
var y1:Number=p1.y;

var steep:Boolean=Math.abs(y1 - y0) > Math.abs(x1 - x0);
if (steep)
{
x0=p0.y;
y0=p0.x;
x1=p1.y;
y1=p1.x;
}

if (x0 > x1)
{
var x0_old:Number=x0;
var y0_old:Number=y0;
x0=x1;
x1=x0_old;
y0=y1;
y1=y0_old;
}

var ratio:Number=Math.abs((y1 - y0) / (x1 - x0));
var mirror:int=y1 > y0 ? 1 : -1;

for (var col:int= Math.floor(x0); col < Math.ceil(x1); col++)
{
var currY:Number=y0 + mirror * ratio * (col - x0);

//第一格不进行延边计算
var skip:Boolean = false;
if(col == Math.floor(x0)){
skip = (int(currY) != int(y0));
}

if(!skip){
if (!steep)
{
touched.push(new Point(col, Math.floor(currY)));
}
else
{
touched.push(new Point(Math.floor(currY), col));
}
}

//根据斜率计算是否有跨格。
if ((mirror > 0 ? (Math.ceil(currY) - currY) : (currY - Math.floor(currY))) < ratio)
{
var crossY:int = Math.floor(currY) + mirror;

//判断是否超出范围
if(crossY>Math.max(int(y0), int(y1)) || crossY

//跨线格子
if (!steep)
{
touched.push(new Point(col, crossY));
}
else
{
touched.push(new Point(crossY, col));
}
}
}
 return touched;
}