Магия треугольника Серпинского в функциональном стиле

Сегодня мы поговорим про замечательную геометрическую фигуру: треугольник Серпинского. Это фрактальная самоподобная структура, которая однако очень проста в построении.

Алгоритм построения треугольника таков:

• Задаем координаты трех вершин – аттракторов (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

Вот какой получился результат:

Весь исходный код можно найти тут: https://fssnip.net/ta

В качестве самостоятельного упражнения, попробуйте в качестве эксперимента модифицировать функцию sieprinski, чтобы она могла принимать произвольное число вершин. И посмотрите, будет ли сохраняться фрактальное свойство для квадратов, шестиугольников и т.д. Буду рад видеть результаты ваших экспериментов в комментариях!