инициализировали его значением 0.0. Затем алгоритм принимает две бинарные функции, которые называются bin_op1 и bin_op2.
К этому моменту мы понимаем, что данный алгоритм очень похож на std::accumulate. Единственное отличие состоит в том, что последний работает только для одного диапазона данных. Если мы заменим выражение bin_op2(*it1,*it2) на *it, то перейдем к алгоритму accumulate. Поэтому можно считать std::inner_product версией алгоритма std::accumulate, которая упаковывает пары входных значений.
В нашем случае функция-упаковщик выглядит как pow(a-b,2). Для другой функции, bin_op1, мы выбрали std::plus<double>, поскольку хотим сложить сразу все значения, возведенные в квадрат.
Реализуем отрисовщик множества Мандельброта в ASCII
В 1975 году математик Бенуа Мандельброт (Benoˆt Mandelbrot) придумал термин «фрактал». Это математическое множество с интересными математическими свойствами, которое в конечном счете выглядит как произведение искусства. Фракталы в приближении выглядят так, будто повторяются бесконечно. Одним из самых популярных фракталов является множество Мандельброта, его вы можете увидеть на рис. 6.7.
Рисунок множества Мандельброта можно сгенерировать путем повторения специальной формулы (рис. 6.8).
Переменные z и c являются комплексными числами. Множество Мандельброта содержит все значения c, для которых формула сходится, если они применяются достаточно часто (рис. 6.7). Одни значения сходятся раньше, другие — позже, так что их можно раскрасить разными цветами. Некоторые из них не сходятся вообще — они отмечены черным.
В STL предусмотрен полезный класс std::complex. Попробуем реализовать эту формулу, не используя явные циклы, только ради того, чтобы получше узнать STL.
Как это делается
В этом примере мы выведем на консоль такое же изображение, которое было показано на рис. 6.7, в формате ASCII.
1. Сначала включим все заголовочные файлы и объявим об использовании пространства имен std:
#include <iostream>
#include <algorithm>
#include <iterator>
#include <complex>
#include <numeric>
#include <vector>
using namespace std;
2. Множество Мандельброта и формула работают с комплексными числами. Поэтому определим псевдоним типа cmplx так, что он имеет типаж std::complex, специализированный для значений типа double:
using cmplx = complex<double>;
3. Вы можете скомпоновать весь код для отрисовки изображения для множества Мандельброта с помощью ASCII примерно за 20 строк кода, но мы реализуем каждый логический шаг отдельно, а затем соберем все воедино. Первый шаг — реализация функции, которая переводит координаты из целых чисел в числа с плавающей точкой. Изначально мы имеем столбцы и строки для всех позиций символов на консоли. Нужно получить координаты с типом complex для системы координат множества Мандельброта. Для этого реализуем функцию, которая принимает параметры, описывающие геометрию системы координат пользовательского окна, а также систему, к которой нужно их привести. Эти значения служат для построения лямбда-выражения, которое будет возвращено позднее. Лямбда-выражение принимает координату 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 <typename A, typename B>
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 значениями
