Существует ли известный алгоритм для преобразования L-систем в итеративные функциональные системы? - PullRequest
Новая
       55

Существует ли известный алгоритм для преобразования L-систем в итеративные функциональные системы?

1 голос
/ 22 апреля 2019

Суть проблемы заключается в следующем:

"Учитывая L-систему с набором алфавита, аксиомой, набором правил перезаписи и набором геометрических правил в биекции с набором алфавита, как нам найти эквивалентный набор Итерированной функциональной системы (IFS) преобразования (что включает в себя, но не исчерпывает - переводы, вращения и масштабирования)? "

Грубо говоря, L-система - это система переписывания символов, в которой вы начинаете с начальной строки (аксиомы) и продолжаете изменять символы в соответствии с правилами переписывания. Чтобы дать ему геометрическую интерпретацию, вы можете связать элемент рисунка, и это даст вам диаграмму.

Это реализация Python для L-системы, которая генерирует кривую Коха с использованием Turtle. 

import time
from turtle import *
from progress.bar import Bar


def Lrule(s):
    s2 = ''
    for i in range(len(s)):
        if s[i] == '>':
            s2 += '>+>-->+>' #rewriting rule
        else:
            s2 += s[i]
    return s2

def stringConstruct(n):
    axiom = '>' #initial string
    b = Bar('Creating string',fill = '=',max = n)
    for i in range(n):
        axiom = Lrule(axiom)
        b.next()
    return axiom

def drawit(distance,angle,n):
    s = stringConstruct(n)
    d = distance

    wn = Screen()
    t = Turtle()
    t.penup()
    t.back(700)
    t.right(90)
    t.forward(300)
    t.left(90)
    t.pendown()
    t.speed(0)

    for cmd in s:
        if cmd == '>':
            t.forward(d)
        elif cmd == '+':
            t.left(angle)
        elif cmd == '-':
            t.right(angle)
    wn.exitonclick()


if __name__ == '__main__':

    drawit(distance=5, angle=60, n=10)

IFS - это набор сжимающих отображений или преобразований, которые переносят точку в другую точку и пытаются аппроксимировать аттракторный набор преобразований.

Здесь приведена реализация IFS для Python, которая генерирует кривую Коха. Он представлен в виде рисунка с использованием библиотеки подушек. 

import random
from PIL import Image
from progress.bar import *
class snowflake(object):
    def __init__(self, img_width, img_height, paint_color=(19, 150, 100),
                 bg_color=(255, 255, 255)):
        self.img_width, self.img_height = img_width, img_height
        self.paint_color = paint_color
        self.x, self.y = 0, 0
        self.age = 0

        self.koch = Image.new('RGB', (img_width, img_height), bg_color)
        self.pix = self.koch.load()
        self.pix[self.scale(0, 0)] = paint_color


    def scale(self, x, y):
        h = (x)*(self.img_width-1)
        k = (0.7-y)*(self.img_height-1)
        return h, k

    def transform(self, x, y): #set of transformations
        rand = random.uniform(0, 100)#to make it more faster
        if rand < 25:
            return x/3, y/3
        elif 25 <= rand < 50:
            return (x-y*3**0.5+2)/6, (y+x*3**0.5)/6
        elif 50 <= rand < 75:
            return (x+y*3**0.5+3)/6, (y-x*3**0.5+3**0.5)/6
        else:
            return (x+2)/3, y/3

    def iterate(self, iterations):
        self.b = ChargingBar('Creating string',max = iterations, suffix='%(percent)d%%')
        for _ in range(iterations):
            self.b.next()
            self.x, self.y = self.transform(self.x, self.y)
            self.pix[self.scale(self.x, self.y)] = self.paint_color
        self.age += iterations

koch = snowflake(1080, 1080)
koch.iterate(200000)
koch.koch.show()

Пройдя неделю, мы пришли к следующему выводу:

  • Для L-системы с набором правил рисования такой набор преобразований всегда существует.

Но это не поможет нам, кроме как докажет существование.

Мы написали L-системы и IFS отдельно в python, чтобы генерировать те же самые фракталы, но отношение, связывающее одно с другим, все еще неясно.

Можно ли сгенерировать алгоритм, чтобы узнать (или сгенерировать) IFS, заданную L-системой с правилами рисования? Если да, было ли это сделано и что это? Если нет, то почему это невозможно?

...