int
и возвращает координату double
.
static auto scaler(int min_from, int max_from,
double min_to, double max_to)
{
const int w_from {max_from - min_from};
const double w_to {max_to - min_to};
const int mid_from {(max_from - min_from) / 2 + min_from};
const double mid_to {(max_to - min_to) / 2.0 + min_to};
return [=] (int from) {
return double(from - mid_from) / w_from * w_to + mid_to;
};
}
4. Теперь можно преобразовать точки в одном измерении, но множество Мандельброта существует в двумерной системе координат. Чтобы выполнить преобразование из одной системы координат
(x, y)
в другую, объединим scaler_x
и scaler_y
, а также создадим экземпляр типа cmplx
на основе их выходных данных.
template
static auto scaled_cmplx(A scaler_x, B scaler_y)
{
return [=](int x, int y) {
return cmplx{scaler_x(x), scaler_y(y)};
};
}
5. После получения возможности преобразовывать координаты в правильные измерения можно реализовать множество Мандельброта. Функция, которую мы реализуем, сейчас ничего не знает о концепции консольных окон или линейного тангенциального преобразования, поэтому можно сконцентрироваться на математике, описывающей множество Мандельброта. Возводим в квадрат значение
z
и добавляем к нему значение c в цикле до тех пор, пока его значение по модулю меньше 2
. Для некоторых координат это не происходит никогда, так что прерываем цикл, если будет превышено максимальное количество итераций max_iterations
. В конечном счете мы вернем количество итераций, которое успели выполнить до того, как сойдется значение по модулю.
static auto mandelbrot_iterations(cmplx c)
{
cmplx z {};
size_t iterations {0};
const size_t max_iterations {1000};
while (abs(z) < 2 && iterations < max_iterations) {
++iterations;
z = pow(z, 2) + c;
}
return iterations;
}
6. Теперь можно начать с функции
main
, где определим измерения консоли и создадим объект функции scale
, который будет масштабировать значения наших координат для обеих осей:
int main()
{
const size_t w {100};
const size_t h {40};
auto scale (scaled_cmplx(
scaler(0, w, -2.0, 1.0),
scaler(0, h, -1.0, 1.0)
));
7. Чтобы выполнить линейный перебор всего изображения, напишем еще одну функцию преобразования, которая принимает одномерную координату
i
. На ее основе она определяет координаты (x, y)
, используя предполагаемую длину строки. После разбиения переменной i
на количество строк и колонок она преобразует их с помощью нашей функции scale
и возвращает комплексную координату:
auto i_to_xy ([=](int i) { return scale(i % w, i / w); });
8. Сейчас можно преобразовать одномерные координаты (с типом
int
) с помощью двумерных координат (с типом (int, int)
) во множество координат Мандельброта (с типом cmplx
), а затем рассчитать количество итераций (снова тип int
). Объединим все это в одну функцию, которая создаст подобную цепочку вызовов:
auto to_iteration_count ([=](int i) {
return mandelbrot_iterations(i_to_xy(i));
});
9. Теперь подготовим все данные. Предположим, что итоговое изображение ASCII имеет w символов в длину и h символов в ширину. Его можно сохранить в одномерном векторе, который имеет
w*h
элементов. Мы заполним данный вектор с помощью std::iota
значениями из диапазона 0...(w*h–1)
. Эти числа можно использовать в качестве входного источника для нашего диапазона данных функции преобразования, который мы инкапсулировали, применяя to_iteration_count
.
vector v (w * h);
iota(begin(v), end(v), 0);
transform(begin(v), end(v), begin(v), to_iteration_count);
10. На этом, по сути, все. Теперь у нас есть вектор v, который мы инициализировали одномерными координатами и переписали счетчиком итераций для множества Мандельброта. На его основе можно вывести красивое изображение. Можно сделать окно консоли длиной w символов, чтобы не выводить на экран символ перевода строки. Но мы можем также нестандартно использовать алгоритм
std::accumulate
, чтобы он добавил разрывы строк за нас. Он применяет бинарную функцию для сокращения диапазона. Предоставим ему бинарную функцию, принимающую итератор вывода (который мы свяжем с терминалом на следующем шаге) и отдельное значение из диапазона. Выведем это значение как символ *
, если количество итераций превышает 50
. В противном случае выведем пробел. При нахождении в конце строки (поскольку переменная-счетчик n
без остатка делится на w
) выведем символ разрыва строки:
auto binfunc ([w, n{0}] (auto output_it, int x) mutable {
*++output_it = (x > 50 ? '*' : ' ');
if (++n % w == 0) { ++output_it = '\n'; }
return output_it;
});
11. Вызывая функцию
std::accumulate
для входного диапазона данных вместе с нашей бинарной функцией print
и итератором ostream_iterator
, можно отправить рассчитанное множество Мандельброта в окно консоли:
accumulate(begin(v), end(v), ostream_iterator{cout},
binfunc);
}
12. Компиляция и запуск программы приводят к следующему результату, который выглядит как изначальное детализированное множество Мандельброта в упрощенной форме (рис. 6.9).
Как это работает
Все расчеты происходят во время вызова
std::transform
для одномерного массива:
vector v (w * h);
iota(begin(v), end(v), 0);
transform(begin(v), end(v), begin(v), to_iteration_count);
Что же произошло и почему это работает именно так? Функция
to_iteration_count
, по сути, представляет собой цепочку вызовов от i_to_xy
до scale
и mandelbrot_iterations
. На рис. 6.10 показаны этапы преобразования.Подобным способом в качестве входного параметра можно использовать индекс одномерного массива и получать количество итераций множества Мандельброта для точки двумерной плоскости, которую представляет точка массива. К счастью, эти три преобразования совершенно не взаимозависимы. Модули подобного кода можно легко протестировать отдельно друг от друга. Таким образом, находить и исправлять ошибки очень легко, как и просто утверждать о корректности кода.
Создаем собственный алгоритм split
В некоторых ситуациях существующих алгоритмов STL недостаточно. Но ничто не запрещает нам реализовать собственный алгоритм. Прежде чем решать конкретную задачу, следует тщательно ее обдумать, чтобы понять: многие задачи можно решить путем обобщения. Если мы будем регулярно добавлять в наши библиотеки новый код по мере решения собственных задач, то можем помочь коллегам-программистам, у которых появятся аналогичные задачи. Идея заключается в том, чтобы знать, когда ваш код является достаточно обобщенным и когда не нужно обобщать его еще больше, в против