判断线段覆盖的格子解决方案

判断线段覆盖的格子
一个正方形平面被划分成n*n的等大小的正方形部分。
输入一个起点一个终点。
按顺序输出从起点沿直线移动到终点所经过的小正方形部分。
即按顺序输出有向线段所覆盖的正方形部分。（其中覆盖的定义为只要线段上有一个点在正方形内部就称做线段覆盖该正方形部分）。

这个问题有没有什么比较高效率的算法？
直觉上总是觉得应该有比较优的算法的。
[解决办法]
起终点是在小格子的中心吗？这是计算机图形学的题吧？类似于屏幕像素拉直线。

如果
[解决办法]
diff x
[解决办法]
 == 
[解决办法]
 diff y 
[解决办法]
或者 
[解决办法]
diff x
[解决办法]
 * 
[解决办法]
diff y
[解决办法]
 == 0，则沿45°的倍数方向，直接挨个输出。

否则，可以先算出直线方程，例如ax + by = c

然后沿一个方向，每次移动1，例如x起点是5，终点是9

那么就x从5到9代入方程，分别求y的坐标（求整数就行），如果y的坐标和上一个不同了，则检测漏检的一个方格，因为从一行方格到另一行方格，必然有一列经过了两个（排除45°角的前提下）。
[解决办法]

引用:

引用:

说错了，应该是y变化了多少，就漏检了多少个格子。

其实判断一下
[解决办法]
diff x
[解决办法]
 和
[解决办法]
 diff y 
[解决办法]
谁大，沿着大的方向检测，另一个方向就最多漏检一个格子了。


感觉不太对吧。只要能漏一个格子，就能漏更多个吧。

起点终点不是在格子中央。

已经挑了
[解决办法]
dx
[解决办法]
,
[解决办法]
dy
[解决办法]
里较大的一个了，如果旋转坐标系使得检测方向一直朝右的话，射线斜率固定<=45度了，所以他说的是没问题的。

不过其实沿较小的一个走更好。沿着检测的时候走一步一下就确定一串格子了。对于差不多平行于坐标轴的线段来说可能浮点运算少一些。
[解决办法]
1.假定每个正方形由m*m个像素构成（由坐标精度确定）。记像素坐标为（x,y）;正方形索引为(p,q).
2.使用快速画直线的算法，可以得到从起点（x0,y0)到终点(xt,yt) 中间每点坐标。
3. 我们记当前检查点位currentcheckpoint = (x_c,y_c);上一次检查点位lastcheckpoint = (x_l,y_l);
初始化：  (x_l,y_l) = (x_0,y_0);
          (x_0,y_0)对应的小正方形索引为(p_0,q_0);
          上一次检查点所在小正方形索引 (p_l, q_l) = (p_0 - 1 ,q_0);

   for ( i = 0; i <t ; i++) {
         (x_c,y_c) = (x_i, y_i);
         if (x_c mod m == 0) {       // 当前点x坐标为m的倍数
                //计算y_c 与上一次检查点 y_l 之间的距离跨越了几个小正方形。 
                if ( (y_c - y_l) mod m > (m - y_l mod m))

                      numofSqure = y/m + 1;
                else
                      numofSqure = y/m;
                // 输出小正方形索引
                for (j = 0; j<= numofSqure; j++) {
                      printf("直线跨越了(%d,%d) \n", p_l + 1, q_l + j);
                }

                // 修改上一次检查点相关坐标
                (x_l, y_l) = (x_c, y_c);
                (p_l, q_l) = (p_l+1 ,q_l + numofSqure);

         }
   }

查看更多 下一篇