Магия треугольника Серпинского в функциональном стиле
Сегодня мы поговорим про замечательную геометрическую фигуру: треугольник Серпинского. Это фрактальная самоподобная структура, которая однако очень проста в построении.
Алгоритм построения треугольника таков:
- Задаем координаты трех вершин-аттракторов (x1,y1), (x2,y2) и (x3,y3)
- Выбираем некоторую точку (x,y) внутри треугольника
- Повторяем много раз:
- Ставим точку с координатами (x,y)
- Выбираем случайным образом одну из вершин (xi,yi)
- Вычисляем координаты новой точки по формуле ((x+xi)/2,(y+yi)/2)
Такой алгоритм легко реализовать на любом языке программирования, однако его реализация на функциональных языках имеет ряд интересных моментов. В частности, для вычисления координат всех точек треугольника мы используем концепцию корекурсии.
В соответствии с этим, мы реализуем функцию sierpinski, которая будет возвращать бесконечную последовательность координат точек треугольника:
let sierpinski (p1,p2,p3) =
let rec sierpinski' pt =
seq {
let p = pick [p1;p2;p3]
let pt' = mid pt p
yield pt'
yield! sierpinski' pt'
}
sierpinski' (mid3 p1 p2 p3)
В этом определении мы используем вспомогательную вложенную рекурсивную функцию sierpinski’, которая в качестве аргумента передает координаты текущей точки pt. Координаты вершин p1,p2,p3 в данном случае являются внешними по отношению к этой функции. Далее мы выбираем одну из вершин случайным образом, вычисляем координаты очередной точки, “возвращаем” (с помощью yield) эти координаты, и затем рекурсивно возвращаем бесконечный остаток списка, который получается из рекурсивного вызова. Затем чтобы сформировать результат мы вызываем sierpinsky’, передавая ему в качестве начальной точки среднюю точку, вычисленную из координат вершин.
Для вычисления средних точек мы определим следуюшие вспомогательные функции:
let mid (x1,y1) (x2,y2) = (x1+x2)/2,(y1+y2)/2 let mid3 (x1,y1) (x2,y2) (x3,y3) = (x1+x2+x3)/3,(y1+y2+y3)/2
Для выбора вершины случайным образом мы используем немного нефукнциональный подход, который зато позволяет быстро получить требуемую функциональность:
let Rnd = new Random() let pick (L:'t list) = L.[Rnd.Next(0,Seq.length L)]
В завершение остаётся лишь построить полученный треугольник. Для этого можем использовать стандартную библиотеку FSharp.Charting:
sierpinski ((0,0),(300,600),(600,0)) |> Seq.take 5000 |> Chart.FastPoint
Вот какой получился результат:
Весь исходный код можно найти здесь: http://fssnip.net/ta.
В качестве самостоятельного упражнения, попробуйте в качестве эксперимента модифицировать функцию sieprinski, чтобы она могла принимать произвольное число вершин. И посмотрите, будет ли сохраняться фрактальное свойство для квадратов, шестиугольников и т.д. Буду рад видеть результаты ваших экспериментов в комментариях!
