0

我有一个网格，其每个单元格都由其 x 和 y 坐标（整数）确定。此网格为 100x100 宽。

我得到一个单元格 (x0, y0) 和一个角度 A。

我的目标是能够在网格内获得线 ((x0, y0), A) 穿过的所有单元格的坐标。

我怎样才能做到这一点 ？？问题是我没有线的长度...

我正在考虑找到第二个点，然后使用 Bresenham 的算法，但是计算它太长了，因为我找到的第二个点通常在我的网格之外。因此，我正在考虑修改 Bresenham 的算法（http://www.roguebasin.com/index.php?title=Bresenham%27s_Line_Algorithm#Python），但鉴于该算法是基于事实上，我们在输入上有两点！：/

预先感谢您的帮助。

4

2 回答 2

0

鉴于 theta = atan2(dy,dx)。这是一个 Bresenham 线条，具有 dx、dy 和单点 (x0,y0) 形式的给定斜率。您还需要指定将使用的图像空间。即最小和最大 x 和 y 值：

     void line(int x0, int y0, int dx, int dy, int minx, int miny, int maxx, int maxy)
     {
         int  sx = dx > 0 ? 1 : -1;
         int  sy = dy > 0 ? 1 : -1;

         dx = abs(dx);
         dy = abs(dy);

         int err = (dx > dy ? dx : -dy) / 2, e2;

         while (x0 >= minx&& y0 >= miny&& x0 <= maxx && y0 <= maxy)
         {
             std::cout << x0 << "," << y0 << endl; // setPixel(x0, y0);
             e2 = err;
             if (e2 > -dx) { err -= dy; x0 += sx; }
             if (e2 < dy) { err += dx; y0 += sy; }
         }
     }

示例驱动程序：

  void driver()
  {
       vector < pair<int, int>> dxdy = { { -1,0},
        { -1,-1},{0,1},{1,1},{-3,1} };

       for (auto& j : dxdy) {
          std::cout << "dxdy = " << j.first << "," << j.second << endl;
          line(5, 5, j.first, j.second, 0, 0, 10, 10);

      }
  }

输出：
dxdy = -1,0
5,5
4,5
3,5
2,5
1,5
0,5
dxdy = -1,-1
5,5
4,4
3,3
2,2
1,1
0, 0
dxdy = 0,1
5,5
5,6
5,7
5,8
5,9
5,10
dxdy = 1,1
5,5
6,6
7,7
8,8
9,9
10,10
dxdy = - 3,1
5,5
4,5
3,6
2,6
1,6
0,7

于 2019-11-07T11:36:37.137 回答
0

假设该角度使得线在沿 y 轴退出之前将沿 x 轴退出网格。这意味着您知道该行末尾的 x 坐标，并且可以使用 @AxelKemper 给出的公式计算其 y 坐标。（如果需要，交换上面 x 和 y 的角色。）如果您事先无法判断是哪种情况，只需选择一个，进行计算，如果它超出网格，则使用另一种情况。

于 2016-12-20T13:54:27.777 回答