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

#cpp #алгоритм #геометрия #2d

                    
Я имею неравномерную сетку в виде координат узлов в двумерном пространстве
Узлы сетки хранятся в одномерном векторе, где нумерация снизу-вверх слева-направо



Также мне дана ломаная монотонная линия (обозначена синим цветом на рисунке), из
которой необходимо получить ломаную линию, проходящую через узлы сетки (обозначено
красной линией на рисунке).

Количество точек ломаной линии не совпадает с количеством точек результирующей ломаной.

Есть ли у кого-нибудь идеи по решению данной задачи?
    

Ответы

Ответ 1

Алгоритм:


Выбираем клетки, через которые проходит ломаная.





Циклично проверяем выбранные клетки:


2.1 Берем на границах клетки две точки, в которых ломаная пересекает эту клетку (или
одну из крайних точек ломаной) и соединяем отрезком.



2.2 Сдвигаем отрезок так, чтоб обе точки находились на границах клетки (в случае
с крайними точками ломаной).

2.3 Считаем углы между отрезком и границами к летки, к которым прилегает отрезок
(достаточно неточного расчета в три варианта >45|=45|<45).



2.4 "основная" граница будет та, у которой угол <45 (обведено красным). Если угол
=45, то обе границы равнозначны.

Повторяем для всех клеток




На основе полученных выборок по две границы строим ломаную




Может получиться, что ломаная пройдет "вдоль" нескольких клеток, в этом случаем сравниваем
результаты проверки текущей клетки и предыдущей. Если сторона клетки с минимальным
углом одинаковая в обоих клетках, то вторую сторону не учитываем.


Ответ 2

Проведите дополнительные воображаемые вертикальные и горизонтальные линии посередине
каждого столбца и строки. У вас получится вдвое более плотная сетка. Каждый узел исходной
сетки окажется заключен в ячейку новой сетки.

Если синяя линия проходит через этот прямоугольник, значит, она задействует соответствующий
узел основной сетки.

Каждый сегмент синей линии пересекается с одним или более полученных прямоугольников.
Зная это, можно написать функцию, возвращающую по каждому сегменту массив узлов основной
сетки, связанных с этими прямоугольниками.

Обходя все сегменты синей линии мы получаем несколько таких массивов. Нужно их слить
в один. Если последний узел в предыдущем массиве равен первому узлу в последующем массиве,
записывать этот узел в результирующий массив всего один раз.


Ответ 3

#include 
#include 
#include 
using namespace std;


int main()
{  
    // вообше то с такими задачами хранить лучше в std::valarray
    // допустим количество узловых точек = 4 * 4 и для примера приведу 
    //конкретные цифры
    // в задаче же уже заданы эти цифры, я лишь для демонстрации идеи
    const int n = 4;
    valarray< int > matrix(n * n);
    // инициализируем первую строку снизу от нулевого индекса `n` штук
    valarray row{ 2, 4, 7, 8 };
    // теперь учитываем что разница между соответствующим элементами
    // следующей строки должны быть одинаковыми.
    //  и допустим эти цифры заданы в векторе
    vector 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 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 альгоритмы дадут нам возможность рассмотреть любое количество точек
    с соответствующими предикатами. Вообшем идея такая, дальше подумайте сами


Ответ 4

0) Учащаем точки ломаной: в цикле определяем расстояние между соседними точками (D)
у ломаной, если это расстояние больше, чем расстояние диагонали ячейки сетки (d), то
вставляем дополнительною точку.




Это шаг предобработки ломаной. В конце объясню зачем это нужно

1) Определяем ближайший узел (curr_node) к начальной точке (p) исходной ломаной


Далее в цикле:

2) Определяем соседние узлы для curr_node (соседями не считать предыдущий посещенный
узел)



3) Определяем расстояние от curr_node и от его соседних узлов до следующей точки
ломаной (p_next). 



4) Если расстояние от curr_node до p_next меньше, чем минимальное расстояние от его
соседей до p_next, то p_next станет следующей точкой ломаной, иначе "посещаю" следующий
узел сетки (тот соседний узел, который ближе всего к точке p_next)

Далее возвращаемся к шагу 2

В итоге получаем такую картину посещения узлов



т.е. собирая посещенные узлы (черные), получаем такую ломаную, проходящую по узлам сетки:



А теперь покажу зачем нужно было делать нулевой шаг:



Как видно из этих двух рисунков, первый вариант неверный. Вставкой дополнительных
точек, добьемся правильного результата