Блог Дмитрия Сошникова

про технологии и человеческое счастье

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

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

image

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

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

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

image

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

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

Add a comment