Преобразование ломанной линии

Алгоритм:

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 альгоритмы дадут нам возможность рассмотреть любое количество точек с соответствующими предикатами. Вообшем идея такая, дальше подумайте сами