折线变换

算法：

1. 选择折线通过的单元格。

2. 循环检查选定的单元格：

2.1 我们取单元格边界上折线与该单元格相交的两个点（或折线的一个极值点）并将其与线段连接起来。

2.2 我们移动线段，使两个点都在单元格的边界上（在折线的极值点的情况下）。

2.3 计算线段与该线段相邻的入口边界之间的角度（三个选项的不准确计算>45|=45|<45 就足够了）。

2.4 “主要”边界将是角度 <45 的边界（以红色圈出）。如果角度 =45，则两个边界是等价的。

对所有单元格重复

3. 基于得到的两个边界的样本，我们构造了一条折线

事实证明，虚线将“沿着”几个单元格，在这种情况下，我们将检查当前单元格和前一个单元格的结果进行比较。如果两个单元格中具有最小角度的单元格一侧相同，则不考虑第二侧。

在每列和每行的中间绘制额外的假想垂直和水平线。您将获得两倍的密集网格。原始网格的每个节点都将包含在新网格的一个单元格中。

如果蓝线穿过这个矩形，则表示它激活了主网格的对应节点。

每个蓝色线段与一个或多个生成的矩形相交。知道了这一点，您可以编写一个函数，为每个段返回与这些矩形关联的主网格节点数组。

绕过蓝线的所有部分，我们得到几个这样的数组。您需要将它们合并为一个。如果前一个数组中的最后一个节点等于后续数组中的第一个节点，则将该节点写入结果数组一次。

#include <iostream>
#include <math.h>
#include <valarray>
using namespace std;


int main()
{  
    // вообше то с такими задачами хранить лучше в std::valarray
    // допустим количество узловых точек = 4 * 4 и для примера приведу 
    //конкретные цифры
    // в задаче же уже заданы эти цифры, я лишь для демонстрации идеи
    const int n = 4;
    valarray< int > matrix(n * n);
    // инициализируем первую строку снизу от нулевого индекса `n` штук
    valarray<int> row{ 2, 4, 7, 8 };
    // теперь учитываем что разница между соответствующим элементами
    // следующей строки должны быть одинаковыми.
    //  и допустим эти цифры заданы в векторе
    vector<int> dif{ 3, 2, 4 };
    // инициализируем последовательность по срезам
    for (int i = 0; i < n; ++i) {
        matrix[slice(i * n, n, 1)] = row;
        if (i == n - 1) break;
        row += dif[i];
    }
   // точки на кривой лучше хранить в map, так как кривая монотонно растет
    map<double, double> curve{{ 3.4, 2.7 }, {4.1, 6}, {5, 9.3}};
    // для первой точки на кривой
    auto para = curve.begin();
    // теперь берем  ближайшие целые этих точек
    int x = lround(para->first), y = lround(para->second);
    //...
    return 0;}

现在，要知道我们序列中的哪些元素更接近具有坐标的点(x, y)只是一个技术问题......为了比较，y它肯定是需要dif的， STL算法将使我们有机会考虑任意数量的点与相应的谓词。总的来说，思路是这样的，那就自己想想吧

0）我们增加折线的点的频率：在循环中我们确定折线的相邻点之间的距离（D），如果这个距离大于网格单元对角线的距离（d），那么插入一个附加点。

这是折线预处理步骤。最后我会解释为什么它是必要的

1）确定离原折线起点（p）最近的节点（curr_node）

在循环中进一步：

2）为curr_node确定邻居节点（不把之前访问过的节点视为邻居）

3) 确定从 curr_node 及其相邻节点到折线的下一个点 (p_next) 的距离。

4) 如果 curr_node 到 p_next 的距离小于它的邻居到 p_next 的最小距离，那么 p_next 将成为折线的下一个点，否则我“访问”下一个网格节点（离p_下一点）

然后回到步骤 2

结果，我们得到如下访问节点的图片

那些。收集访问过的节点（黑色），我们得到以下通过网格节点的折线：

现在我将说明为什么有必要采取零步：

从这两张图可以看出，第一个选项是错误的。通过插入额外的点，我们将获得正确的结果