Mandelbrot kümesi için çizim algoritmaları - Plotting algorithms for the Mandelbrot set - Wikipedia

Hareketsiz görüntüsü artan büyütme filmi 0.001643721971153 - 0.822467633298876 üzerindeben

Hareketsiz görüntüsü artan büyütme animasyonu

Çizgiyi çizmek için kullanılan birçok program ve algoritma vardır. Mandelbrot seti ve diğeri fraktallar, bazıları şurada açıklanmıştır: fraktal üreten yazılım. Bu programlar, bireyin rengini belirlemek için çeşitli algoritmalar kullanır. piksel verimli.

Kaçış süresi algoritması

Mandelbrot kümesinin bir temsilini oluşturmak için en basit algoritma "kaçış zamanı" algoritması olarak bilinir. Her biri için tekrar eden bir hesaplama yapılır. x, y çizim alanındaki nokta ve bu hesaplamanın davranışına bağlı olarak, o piksel için bir renk seçilir.

Optimize edilmemiş, saf kaçış süresi algoritması

Hem optimize edilmemiş hem de optimize edilmiş kaçış süresi algoritmalarında, x ve y her noktanın konumu, tekrar eden veya yinelenen bir hesaplamada başlangıç ​​değerleri olarak kullanılır (aşağıda ayrıntılı olarak açıklanmıştır). Her yinelemenin sonucu, bir sonraki için başlangıç ​​değerleri olarak kullanılır. Değerler, kritik bir "kaçış" durumuna veya "kurtarma" durumuna ulaşıp ulaşmadıklarını görmek için her yineleme sırasında kontrol edilir. Bu koşula ulaşılırsa, hesaplama durdurulur, piksel çizilir ve sonraki x, y nokta incelenir. Bazı başlangıç ​​değerleri için kaçış, yalnızca az sayıda yinelemeden sonra hızlı bir şekilde gerçekleşir. Kümeye çok yakın olan ancak kümede olmayan başlangıç ​​değerleri için, kaçmak yüzlerce veya binlerce yineleme alabilir. Mandelbrot kümesindeki değerler için kaçış asla gerçekleşmez. Programcı veya kullanıcı, incelemek istedikleri kaç yineleme veya ne kadar "derinlik" i seçmelidir. Maksimum yineleme sayısı ne kadar yüksekse, son görüntüde o kadar fazla ayrıntı ve incelik ortaya çıkar, ancak fraktal görüntünün hesaplanması o kadar uzun sürecektir.

Kaçış koşulları basit veya karmaşık olabilir. Gerçek veya hayali kısmı 2'den büyük olan hiçbir karmaşık sayı kümenin parçası olamayacağından, ortak bir kurtarma, katsayılardan biri 2'yi aştığında kaçmaktır. Kaçışları daha erken tespit eden daha hesaplamalı olarak karmaşık bir yöntem, başlangıç ​​noktasından uzaklığı hesaplamaktır. Pisagor teoremi yani, belirlemek için mutlak değer veya modül, karmaşık sayının. Bu değer 2'yi aşarsa veya eşdeğer olarak, gerçek ve sanal parçaların karelerinin toplamı 4'ü aştığında, nokta kaçışa ulaşmıştır. Hesaplama açısından daha yoğun işleme varyasyonları şunları içerir: Buddhabrot kaçış noktaları bulan ve yinelenen koordinatlarını çizen yöntem.

Her noktanın rengi, değerlerin kaçış noktasına ne kadar hızlı ulaştığını gösterir. Yineleme sınırından önce kaçamayan değerleri göstermek için genellikle siyah kullanılır ve kaçan noktalar için giderek daha parlak renkler kullanılır. Bu, kaçış durumuna ulaşmadan önce kaç döngü gerektiğinin görsel bir temsilini verir.

Böyle bir görüntüyü oluşturmak için, düşündüğümüz karmaşık düzlemin bölgesi belirli bir sayıda alt bölüme ayrılmıştır. piksel. Böyle bir pikseli renklendirmek için ${ displaystyle c}$ o pikselin orta noktası olun. Şimdi kritik noktayı 0'ın altında yineliyoruz ${ displaystyle P_ {c}}$, her adımda yörünge noktasının modülünün 2'den büyük olup olmadığını kontrol edin. Bu durumda, biliyoruz ki ${ displaystyle c}$ Mandelbrot setine ait değildir ve pikselimizi bulmak için kullanılan yineleme sayısına göre renklendiririz. Aksi takdirde, sabit sayıda adıma kadar yinelemeye devam ederiz, ardından parametremizin Mandelbrot kümesinde "muhtemelen" veya en azından ona çok yakın olduğuna karar verir ve pikseli siyah renklendiririz.

İçinde sözde kod, bu algoritma aşağıdaki gibi görünecektir. Algoritma, karmaşık sayılar kullanmaz ve karmaşık sayı işlemlerini iki gerçek sayı kullanarak manuel olarak simüle eder. karmaşık veri türü. Programlama dili karmaşık veri tipi işlemler içeriyorsa program basitleştirilebilir.

her biri için ekrandaki piksel (Px, Py) yapmak    x0: = pikselin ölçeklenmiş x koordinatı (Mandelbrot X ölçeğinde (-2.5, 1) olacak şekilde ölçeklenmiş) y0: = pikselin ölçeklenmiş y koordinatı (Mandelbrot Y ölçeğinde (-1, 1) yatacak şekilde ölçeklenmiş) x: = 0.0 y: = 0.0 yineleme: = 0 maks_iterasyon: = 1000 süre (x × x + y × y ≤ 2 × 2 VE yineleme yapmak        xtemp: = x × x - y × y + x0 y: = 2 × x × y + y0 x: = xtemp yineleme: = yineleme + 1 renk: = palet [yineleme] grafiği (Px, Py, renk)

Burada sözde kodu ile ilişkilendirmek ${ displaystyle c}$, ${ displaystyle z}$ ve ${ displaystyle P_ {c}}$:

• ${ displaystyle z = x + iy }$
• ${ displaystyle z ^ {2} = x ^ {2} + 2ixy}$ - ${ displaystyle y ^ {2} }$
• ${ displaystyle c = x_ {0} + iy_ {0} }$

ve böylece, hesaplamadaki sözde kodda görülebileceği gibi x ve y:

• ${ displaystyle x = mathop { mathrm {Re}} (z ^ {2} + c) = x ^ {2} -y ^ {2} + x_ {0}}$ ve ${ displaystyle y = mathop { mathrm {Im}} (z ^ {2} + c) = 2xy + y_ {0}. }$

Setin renkli görüntülerini elde etmek için, yürütülen yineleme sayısının her bir değerine bir renk ataması, çeşitli işlevlerden biri (doğrusal, üstel, vb.) Kullanılarak yapılabilir. Hesaplamaları yavaşlatmadan pratik bir yol, yürütülen yinelemelerin sayısını bir giriş olarak kullanmaktır. palet başlangıçta başlatıldı. Renk tablosunda örneğin 500 giriş varsa, renk seçimi n mod 500, nerede n yineleme sayısıdır.

Optimize edilmiş kaçış süresi algoritmaları

Önceki bölümdeki kod, netlik için optimize edilmemiş bir iç while döngüsü kullanır. Optimize edilmemiş versiyonda, her yineleme için beş çarpma gerçekleştirilmelidir. Çarpma sayısını azaltmak için, bunun yerine iç while döngüsü için aşağıdaki kod kullanılabilir:

x2: = 0y2: = 0w: = 0süre (x2 + y2 ≤ 4 ve yineleme yapmak    x: = x2 - y2 + x0 y: = w - x2 - y2 + y0 x2: = x × x y2: = y × y w: = (x + y) × (x + y) yineleme: = yineleme + 1

Yukarıdaki kod, karmaşık çarpmanın bazı cebirsel basitleştirmesi yoluyla çalışır:

${ displaystyle { başla {hizalı} (iy + x) ^ {2} & = - y ^ {2} + 2iyx + x ^ {2} & = x ^ {2} -y ^ {2} + 2iyx end {hizalı}}}$

Yukarıdaki kimlik kullanılarak çarpma sayısı beş yerine üçe indirilebilir.

Yukarıdaki iç while döngüsü, genişletilerek daha da optimize edilebilir w -e

${ displaystyle w = x ^ {2} + 2xy + y ^ {2}}$

İkame w içine ${ displaystyle y = w-x ^ {2} -y ^ {2} + y_ {0}}$ verim${ displaystyle y = 2xy + y_ {0}}$ve dolayısıyla hesaplanıyor w artık gerekli değil.

Yukarıdakiler için daha da optimize edilmiş sözde kod şudur:

x2: = 0y2: = 0süre (x2 + y2 ≤ 4 ve yineleme yapmak    y: = 2 × x × y + y0 x: = x2 - y2 + x0 x2: = x × x y2: = y × y yineleme: = yineleme + 1

Yukarıdaki sözde kodda, ${ displaystyle 2xy}$ Çarpma sayısını 1 artırıyor gibi görünüyor, ancak çarpan 2 olduğu için kod şu şekilde optimize edilebilir: ${ displaystyle (x + x) y}$.

Renklendirme algoritmaları

Setin grafiğini çizmeye ek olarak, seti estetik açıdan hoş bir şekilde verimli bir şekilde renklendirmek için çeşitli algoritmalar geliştirilmiştir.

Histogram renklendirme

Bu bölüm için ek alıntılara ihtiyaç var doğrulama. İlgili tartışma şurada bulunabilir: konuşma sayfası. Lütfen yardım et bu makaleyi geliştir tarafından güvenilir kaynaklara alıntılar eklemek. Kaynaksız materyale itiraz edilebilir ve kaldırılabilir. (Haziran 2019) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

Daha karmaşık bir renklendirme yöntemi, bir histogram kaçış / kurtarma işleminden önce her pikseli söz konusu pikselin maksimum yineleme sayısıyla eşleştirir. Bu yöntem, renkleri aynı genel alana eşit olarak dağıtacaktır ve daha da önemlisi, seçilen maksimum yineleme sayısından bağımsızdır.^[1]

Bu algoritmanın dört geçişi vardır. İlk geçiş, her bir pikselle ilişkili yineleme sayımlarının hesaplanmasını içerir (ancak herhangi bir piksel çizilmeden). Bunlar, IterationCounts [x] [y] olarak adlandıracağımız bir dizide saklanır, burada x ve y, sırasıyla ekrandaki pikselin x ve y koordinatlarıdır.

Üst sıra, piksel başına sırasıyla 10000, 1000 ve 100 maksimum yineleme için kaçış süresi algoritmasını kullanan bir dizi grafiktir. Alt satır, aynı maksimum yineleme değerlerini kullanır, ancak histogram renklendirme yöntemini kullanır. Histogram renklendirme yöntemi grafikleri için farklı maksimum yineleme sayısı başına renklendirmenin ne kadar az değiştiğine dikkat edin.

İkinci geçişin ilk adımı, bir boyut dizisi oluşturmaktır. n, maksimum yineleme sayısıdır. Bu diziye NumIterationsPerPixel adını vereceğiz. Daha sonra, piksel yineleme sayım çiftleri dizisi, IterationCounts [] [] üzerinde yineleme yapılmalı ve her pikselin kaydedilen yineleme sayısı alınmalıdır. ben, ör. ben = IterationCounts [x] [y]. Her pikselin yinelemesinden sonra ben alındığında NumIterationsPerPixel'i indekslemek gerekir. ben ve endekslenmiş değeri artırın (başlangıçta sıfırdır) - ör. NumIterationsPerPixel [ben] = NumIterationsPerPixel [ben] + 1 .

için (x = 0; x yapmak    için (y = 0; y yapmak        i: = IterationCounts [x] [y] NumIterationsPerPixel [i] ++

Üçüncü geçiş NumIterationsPerPixel dizisi boyunca yinelenir ve depolanan tüm değerleri toplayarak bunları kaydeder Toplam. Dizi indeksi, kurtarma işleminden önce bu yineleme sayısına ulaşan piksel sayısını temsil eder.

toplam: = 0için (i = 0; i yapmak    toplam + = NumIterationsPerPixel [i]}

Bundan sonra, dördüncü geçiş başlar ve IterationCounts dizisindeki tüm değerler dizine alınır ve her yineleme için ben, her pikselle ilişkili olarak sayı, 1'den 1'e kadar tüm yineleme sayılarının genel toplamına eklenir. ben NumIterationsPerPixel dizisinde. . Bu değer daha sonra toplamı, Toplam daha önce hesaplanan değer.

renk [] []: = 0,0için (x = 0; x yapmak    için (y = 0; y yapmak        yineleme: = IterationCounts [x] [y] için (i = 0; i <= yineleme; i ++) yapmak            ton [x] [y] + = NumIterationsPerPixel [i] / toplam / * Kayan nokta bölümü olmalıdır. * /... renk = palet [ton [m, n]] ...

Son olarak, hesaplanan değer kullanılır, ör. bir renk paletinin indeksi olarak.

Bu yöntem, estetik açıdan daha hoş görüntüler için aşağıdaki pürüzsüz renklendirme yöntemiyle birleştirilebilir.

Sürekli (pürüzsüz) renklendirme

Bu görüntü, kaçış süresi algoritmasıyla oluşturulmuştur. Çok belirgin renk "bantları" var

Bu görüntü, normalleştirilmiş yineleme sayma algoritması ile oluşturulmuştur. Renk bantlarının yerini yumuşak bir gradyan almıştır. Ayrıca renkler, kaçış süresi algoritması kullanıldığında gözlemlenecek olanla aynı kalıbı alır.

Kaçış süresi algoritması basitliği nedeniyle popülerdir. Bununla birlikte, bir tür olarak renk bantları oluşturur. takma ad, bir görüntünün estetik değerini azaltabilir. Bu, "normalleştirilmiş yineleme sayısı" olarak bilinen bir algoritma kullanılarak iyileştirilebilir.^[2][3] Bu, yinelemeler arasında yumuşak bir renk geçişi sağlar. Algoritma gerçek bir sayıyı ilişkilendirir ${ displaystyle nu}$ her değeri ile z iterasyon numarasının bağlantısını kullanarak potansiyel işlev. Bu işlev,

${ displaystyle phi (z) = lim _ {n ila infty} ( log | z_ {n} | / P ^ {n}),}$

nerede z_n sonraki değer n yinelemeler ve P bunun için güç z Mandelbrot set denkleminde yükseltilir (z_n+1 = z_n^P + c, P genellikle 2'dir).

Büyük bir kurtarma yarıçapı seçersek N (ör. 10¹⁰⁰), bizde var

${ displaystyle günlük | z_ {n} | / P ^ {n} = günlük (N) / P ^ { nu (z)}}$

gerçek bir sayı için ${ displaystyle nu (z)}$, Ve bu

${ displaystyle nu (z) = n- log _ {P} ( log | z_ {n} | / log (N)),}$

ve benzeri n ilk yineleme numarasıdır, öyle ki |z_n| > Nçıkardığımız sayı n [0, 1) aralığındadır.

Renklendirme için döngüsel bir renk ölçeğine sahip olmalıyız (örneğin matematiksel olarak oluşturulmuş) ve H 0 ile numaralandırılmış renkler H − 1 (H = 500, örneğin). Gerçek sayıyı çarpıyoruz ${ displaystyle nu (z)}$ resimdeki renklerin yoğunluğunu belirleyen sabit bir gerçek sayı ile bu sayı modülünün ayrılmaz parçasını alınHve renk tablosunda karşılık gelen rengi aramak için kullanın.

Örneğin, yukarıdaki sözde kodu değiştirmek ve ayrıca doğrusal enterpolasyon verim verecek

her biri için ekrandaki piksel (Px, Py) yapmak    x0: = pikselin ölçeklenmiş x koordinatı (Mandelbrot X ölçeğinde (-2.5, 1) olacak şekilde ölçeklenmiş) y0: = pikselin ölçeklenmiş y koordinatı (Mandelbrot Y ölçeğinde (-1, 1) yatacak şekilde ölçeklenmiş) x: = 0.0 y: = 0.0 yineleme: = 0 maks_iterasyon: = 1000 // Burada N = 2 ^ 8, makul bir kurtarma yarıçapı olarak seçilmiştir.    süre x × x + y × y ≤ (1 << 16) ve yineleme yapmak        xtemp: = x × x - y × y + x0 y: = 2 × x × y + y0 x: = xtemp yineleme: = yineleme + 1 // Küme içindeki noktalarla ilgili kayan nokta sorunlarını önlemek için kullanılır.    Eğer yineleme sonra        // günlük basitleştirme kuralları kullanılarak iç terimin sqrt'si kaldırıldı.        log_zn: = log (x * x + y * y) / 2 nu: = log (log_zn / log (2)) / log (2) // Potansiyel işlevi yeniden düzenleme.        // log_zn'yi log (N = 1 << 8) yerine log (2) ile bölmek // çünkü tüm paletin // merkezden yarıçap 2'ye kadar değişmesini istiyoruz, kurtarma yarıçapımız DEĞİL.        yineleme: = yineleme + 1 - nu renk1: = palet [kat (yineleme)] renk2: = palet [kat (yineleme) + 1] // yineleme% 1 = yinelemenin kesirli kısmı.    color: = linear_interpolate (color1, color2, iteration% 1) plot (Px, Py, color)

Gelişmiş çizim algoritmaları

Daha önce tartışılan basit ve yavaş kaçış zamanı algoritmalarına ek olarak, çizim sürecini hızlandırmak için kullanılabilecek daha birçok gelişmiş algoritma vardır.

Mesafe tahminleri

Biri hesaplanabilir mesafe noktadan c (içinde dış veya iç ) en yakın noktaya sınır Mandelbrot kümesinin.^[4]

Dış mesafe tahmini

Kanıtı bağlılık aslında Mandelbrot kümesinin haritayı tek tipleştirme of Tamamlayıcı nın-nin ${ displaystyle M}$ (ve türev Bu haritanın). Tarafından Koebe çeyrek teoremi, daha sonra orta noktamız arasındaki mesafe tahmin edilebilir. piksel ve Mandelbrot 4 katına çıktı.

Başka bir deyişle, maksimum yineleme sayısının yeterince yüksek olması koşuluyla, aşağıdaki özelliklere sahip Mandelbrot kümesinin bir resmini elde edebilirsiniz:

1. Mandelbrot setinin bir noktasını içeren her piksel siyah renklidir.
2. Siyah renkli her piksel Mandelbrot setine yakındır.

Dış mesafe tahmini, Mandelbrot setinin tüm tamamlayıcısını renklendirmek için kullanılabilir

Mesafe tahmini b bir pikselin c Mandelbrot kümesinden (karmaşık bir sayı) verilir

${ displaystyle b = lim _ {n ila infty} 2 cdot { frac {| {P_ {c} ^ {n} (c) | cdot ln | {P_ {c} ^ {n} (c)}} |} {| { frac { kısmi} { kısmi {c}}} P_ {c} ^ {n} (c) |}},}$

nerede

• ${ displaystyle P_ {c} (z) ,}$ duruyor karmaşık ikinci dereceden polinom
• ${ displaystyle P_ {c} ^ {n} (c)}$ duruyor n yinelemeler ${ displaystyle P_ {c} (z) ila z}$ veya ${ displaystyle z ^ {2} + c ila z}$ile başlayarak ${ displaystyle z = c}$: ${ displaystyle P_ {c} ^ {0} (c) = c}$, ${ displaystyle P_ {c} ^ {n + 1} (c) = P_ {c} ^ {n} (c) ^ {2} + c}$;
• ${ displaystyle { frac { kısmi} { kısmi {c}}} P_ {c} ^ {n} (c)}$ türevidir ${ displaystyle P_ {c} ^ {n} (c)}$ c ile ilgili olarak. Bu türev, ile başlayarak bulunabilir. ${ displaystyle { frac { kısmi} { kısmi {c}}} P_ {c} ^ {0} (c) = 1}$ ve daha sonra ${ displaystyle { frac { kısmi} { kısmi {c}}} P_ {c} ^ {n + 1} (c) = 2 cdot {} P_ {c} ^ {n} (c) cdot { frac { kısmi} { kısmi {c}}} P_ {c} ^ {n} (c) +1}$. Bu, türev için zincir kuralı kullanılarak kolayca doğrulanabilir.

Bu formülün arkasındaki fikir basittir: eşpotansiyel potansiyel işlev için çizgiler ${ displaystyle phi (z)}$ yakın yalan, numara ${ displaystyle | phi '(z) |}$ büyüktür ve tersine, işlev için eşpotansiyel çizgiler ${ displaystyle phi (z) / | phi '(z) |}$ yaklaşık olarak düzenli olarak yalan söylemelidir.

Bir matematikçinin bakış açısından, bu formül yalnızca n sonsuzluğa gider, ancak çok makul tahminler, ana döngüden çıktıktan sonra sadece birkaç ek yineleme ile bulunabilir.

bir Zamanlar b Koebe 1/4-teoremi ile bulunursa, Mandelbrot kümesinin uzaklığı olan bir noktasının olmadığını biliyoruz. c daha küçük b / 4.

Mesafe tahmini, Mandelbrot setinin sınırının çizilmesi için kullanılabilir, makaleye bakın Julia seti. Bu yaklaşımda, M'ye yeterince yakın olan pikseller farklı bir renk kullanılarak çizilir. Bu, Mandelbrot setinin ince "filamentlerinin" kolayca görülebildiği çizimler oluşturur. Bu teknik, "Fraktalların Güzelliği" kitaplarındaki Mandelbrot setlerinin siyah-beyaz görüntülerinde iyi bir etki için kullanılır.^[5]"ve" Fraktal Görüntü Bilimi ".^[6]

Mesafe Tahminleri kullanılarak oluşturulmuş örnek bir siyah beyaz görüntü:

Bu, Mesafe Tahminleri (DE) kullanılarak oluşturulan Mandelbrot kümesinin bir bölümünün siyah beyaz bir görüntüsüdür

Mesafe Tahmini, işlemek için de kullanılabilir Mandelbrot ve Julia setlerinin 3 boyutlu görüntüleri

İç mesafe tahmini

Tahmini iç mesafeye göre renkli pikseller

Sınırlı bir periyodik (yani iç) noktanın Mandelbrot kümesinin sınırına olan mesafesini tahmin etmek de mümkündür. Tahmin tarafından verilir

${ displaystyle b = { frac {1- sol | {{ frac { kısmi} { kısmi {z}}} P_ {c} ^ {p} (z_ {0})} sağ | ^ { 2}} { sol | {{ frac { kısmi} { kısmi {c}}} { frac { kısmi} { kısmi {z}}} P_ {c} ^ {p} (z_ {0 }) + { frac { bölüm} { bölümlü {z}}} { frac { bölümlü} { bölümlü {z}}} P_ {c} ^ {p} (z_ {0}) { frac {{ frac { kısmi} { kısmi {c}}} P_ {c} ^ {p} (z_ {0})} {1 - { frac { kısmi} { kısmi {z}}} P_ {c} ^ {p} (z_ {0})}}} sağ |}},}$

nerede

• ${ displaystyle p}$ dönem
• ${ displaystyle c}$ tahmin edilmesi gereken nokta
• ${ displaystyle P_ {c} (z)}$ ... karmaşık ikinci dereceden polinom ${ displaystyle P_ {c} (z) = z ^ {2} + c}$
• ${ displaystyle P_ {c} ^ {p} (z_ {0})}$ ... ${ displaystyle p}$-fold iterasyonu ${ displaystyle P_ {c} (z) ila z}$ile başlayarak ${ displaystyle P_ {c} ^ {0} (z) = z_ {0}}$
• ${ displaystyle z_ {0}}$ herhangi biri ${ displaystyle p}$ yapan noktalar cazibe merkezi yinelemelerinin ${ displaystyle P_ {c} (z) ila z}$ ile başlayarak ${ displaystyle P_ {c} ^ {0} (z) = c}$; ${ displaystyle z_ {0}}$ tatmin eder ${ displaystyle z_ {0} = P_ {c} ^ {p} (z_ {0})}$,
• ${ displaystyle { frac { kısmi} { kısmi {c}}} { frac { kısmi} { kısmi {z}}} P_ {c} ^ {p} (z_ {0})}$, ${ displaystyle { frac { kısmi} { kısmi {z}}} { frac { kısmi} { kısmi {z}}} P_ {c} ^ {p} (z_ {0})}$, ${ displaystyle { frac { kısmi} { kısmi {c}}} P_ {c} ^ {p} (z_ {0})}$ ve ${ displaystyle { frac { kısmi} { kısmi {z}}} P_ {c} ^ {p} (z_ {0})}$ çeşitli türevleridir ${ displaystyle P_ {c} ^ {p} (z)}$, değerlendirildi ${ displaystyle z_ {0}}$.

Dış kasaya benzer, bir kez b bulunduğunda, mesafe içindeki tüm noktaların b/ 4 c Mandelbrot kümesinin içindedir.

İç mesafe tahminiyle ilgili iki pratik sorun vardır: ilk olarak, bulmalıyız ${ displaystyle z_ {0}}$ tam olarak ve ikincisi, bulmamız gerekiyor ${ displaystyle p}$ tam olarak. ile sorun ${ displaystyle z_ {0}}$ yakınsama ${ displaystyle z_ {0}}$ yineleyerek ${ displaystyle P_ {c} (z)}$ teorik olarak sonsuz sayıda işlem gerektirir. ${ displaystyle p}$ bazen, yuvarlama hataları nedeniyle, bir dönemin yanlış bir şekilde gerçek dönemin tam sayı katı olarak tanımlanmasıdır (örneğin, gerçek dönem yalnızca 43 = 86/2 iken, 86 periyotu tespit edilir). Böyle bir durumda, mesafe fazla tahmin edilir, yani rapor edilen yarıçap Mandelbrot kümesinin dışındaki noktaları içerebilir.

3B görünüm: Mandelbrot setinin iç noktalarının yörüngesinin en küçük mutlak değeri

Kardioid / ampul kontrolü

Hesaplamaları geliştirmenin bir yolu, verilen noktanın kardiyoit içinde mi yoksa 2. periyot ampulünde mi olduğunu önceden bulmaktır. Karmaşık değeri kaçış süresi algoritmasından geçirmeden önce, önce şunları kontrol edin:

${ displaystyle p = { sqrt { left (x - { frac {1} {4}} sağ) ^ {2} + y ^ {2}}}}$,

${ displaystyle x leq p-2p ^ {2} + { frac {1} {4}}}$,

${ displaystyle (x + 1) ^ {2} + y ^ {2} leq { frac {1} {16}}}$,

nerede x noktanın gerçek değerini temsil eder ve y hayali değer. İlk iki denklem, noktanın kardioid içinde olduğunu, sonuncusu ise periyot-2 ampulünün içinde olduğunu belirler.

Kardioid testi aynı şekilde karekök olmadan da yapılabilir:

${ displaystyle q = sol (x - { frac {1} {4}} sağ) ^ {2} + y ^ {2},}$

${ displaystyle q sol (q + sol (x - { frac {1} {4}} sağ) sağ) leq { frac {1} {4}} y ^ {2}.}$

3. ve daha yüksek dereceli tomurcukların eşdeğer testleri yoktur çünkü bunlar tamamen dairesel değildir.^[7] Bununla birlikte, noktaların bu yüksek dereceli ampullerin içine yazılmış dairelerin içinde olup olmadığını bulmak mümkündür, bu da ampuldeki noktaların tümü olmasa da çoğunun yinelenmesini engeller.

Periyodik kontrol

Küme içindeki noktalar için çok sayıda yineleme yapmak zorunda kalmamak için, periyodiklik kontrolü yapılabilir. Daha önce bir piksel yinelemede ulaşılan bir noktaya ulaşılıp ulaşılmadığını kontrol edin. Öyleyse piksel birbirinden ayrılamaz ve sette olmalıdır.

Periyodiklik kontrolü elbette bir değiş tokuştur. Noktaları hatırlama ihtiyacı hafızaya mal olur ve veri yönetimi talimatları kaydederken hesaplamalı Talimatlar.

Ancak, yalnızca bir önceki yinelemeyi kontrol etmek, az performans ek yükü olan birçok dönemi algılayabilir. Örneğin, yukarıdaki sözde kodun while döngüsü içinde aşağıdaki değişiklikleri yapın:

xold: = 0yıl: = 0dönem: = 0süre (x × x + y × y ≤ 2 × 2 ve yineleme yapmak    xtemp: = x × x - y × y + x0 y: = 2 × x × y + y0 x: = xtemp yineleme: = yineleme + 1 Eğer x ≈ xold ve y ≈ yold sonra        yineleme: = max_iteration / * Renk çizimi için maksimuma ayarlayın * / break / * Mandelbrot setinin içindeyiz, while döngüsünü bırakın * / period: = period + 1 Eğer dönem> 20 sonra        dönem: = 0 xold: = x yold: = y

Yukarıdaki kod, her 20: th yinelemede yeni bir x ve y değerini saklar, böylece 20 puana kadar olan periyotları algılayabilir.

Sınır izleme / kenar kontrolü

Mandelbrot setinin hiperbolik bileşenlerinin Sobel filtresini kullanarak kenar algılama

Tüm kenar renkleri aynı olacak şekilde Mandelbrot setinde düz bir şekil çizilebiliyorsa, şeklin bu renkle doldurulabileceği gösterilebilir. Bu, Mandelbrot kümesinin basitçe bağlanmasının bir sonucudur. Sınır izleme, Lemniscates setin her tarafında çeşitli yineleme seviyelerinin (renkli bantlar) ve ardından tüm bandın bir kerede doldurulması. Bu iyi bir hız artışı olabilir, çünkü çok sayıda noktanın atlanabileceği anlamına gelir.^[8] Çizim DE (Mesafe Tahmini) veya potansiyel (kesirli yineleme) değerlerini hesaplarsa, setin dışındaki piksel bantlarını tanımlamak için sınır izlemenin kullanılamayacağını unutmayın.

Sınır izleme, bir pikselin M cinsinden olduğunu belirlemek maksimum yineleme sayısını hesaplamayı gerektirdiğinden, Mandelbrot kümesinin (M cinsinden) parçaları olan bir grafiğin geniş alanlarını atlamak için özellikle yararlıdır.

Aşağıda, sınır izleme kullanılarak oluşturulmuş bir Mandelbrot kümesi örneği verilmiştir:

Medya oynatın

Bu, 1000 yineleme maksimum yineleme sayısı ile basit kaçış zamanı oluşturmayı kullanan 400x400 piksellik bir çizimdir. Sınır izleme olmadan gerekli olacak toplam yineleme sayısının yalnızca% 6,84'ünü hesaplaması gerekiyordu. Oluşturma sürecini izlemek için yeterince yavaş hale getirmek için yavaşlatılmış bir oluşturma motoru kullanılarak oluşturuldu ve oluşturulması 6,05 saniye sürdü. Aynı yavaşlatılmış işleme motoru ile sınır izleme kapalıyken aynı grafiğin işlenmesi 117.0 saniye sürdü.

Kesirli yineleme değerlerini hesaplamak için ayarlar değiştirilse bile (bu, sınır izlemenin Mandelbrot olmayan noktaları izlemesini engeller) sınır izleme algoritmasının bu grafiği yine de 7.10 saniyede işler çünkü Mandelbrot noktalarının tanımlanması her zaman maksimum sayıda yineleme gerektirir. Maksimum yineleme sayısı ne kadar yüksekse, Mandelbrot noktalarını belirlemek o kadar maliyetli olur ve bu nedenle sınır izleme daha fazla fayda sağlar.

Diğer bir deyişle, dış alan düzgün / sürekli renklendirme kullansa bile, kenar izleme Mandelbrot setinin maliyetli iç alanını yine de hızlandıracaktır. İç alan da bazı yumuşak renklendirme yöntemlerini kullanmadığı sürece, örneğin iç mesafe tahmini.

Dikdörtgen kontrolü

Sınır izlemeden daha eski ve uygulaması daha basit bir yöntem dikdörtgenler kullanmaktır. Dikdörtgen yönteminin birkaç çeşidi vardır. Hepsi daha fazla piksel hesapladığı için sınır izlemeden daha yavaştır.

Temel yöntem, 8x8 piksellik bir kutunun kenar piksellerini hesaplamaktır. Tüm kutu kenarlığı aynı renge sahipse, hesaplamak yerine kutunun içindeki 36 pikseli (6x6) aynı renkle doldurun. (Mariani'nin algoritması.)^[9]

Daha hızlı ve biraz daha gelişmiş bir varyant, önce daha büyük bir kutuyu, örneğin 25x25 piksel hesaplamaktır. Tüm kutu kenarlığı aynı renge sahipse, kutuyu aynı renkle doldurmanız yeterlidir. Değilse, kutuyu 13x13 piksellik dört kutuya bölün, önceden hesaplanmış pikselleri dış kenarlık olarak yeniden kullanın ve iç kutular arasında iç "çapraz" pikselleri paylaşın. Yine, yalnızca bir kenarlık rengi olan kutuları doldurun. Ve bu kutuları şimdi 7x7 piksellik dört kutuya bölün. Ve sonra 4x4 kutularda "başarısız olanlar". (Mariani-Silver algoritması.)

Daha da hızlı olanı, kutuları dört kutu yerine ikiye bölmektir. O zaman 1.4: 1 kutu kullanmak en uygun seçenek olabilir. en boy oranı, böylece bölünebilirler A3 kağıtlar nasıl katlanır A4 ve A5 kağıtlarına. (DIN yaklaşımı.)

Bir varyant, her kutunun köşe piksellerini hesaplar. Ancak bu, tüm kutu kenar piksellerini hesaplamaktan daha sık hasarlı resimlere neden olur. Bu nedenle, yalnızca 6x6 piksellik küçük kutular kullanılırsa ve daha büyük kutulardan tekrarlama yapılmazsa makul derecede iyi çalışır. (Fractint yöntem.)

Kenarlık izlemede olduğu gibi, dikdörtgen denetimi yalnızca tek bir rengi olan alanlarda çalışır. Ancak, dış alan düzgün / sürekli renklendirme kullansa bile, dikdörtgen kontrolü Mandelbrot setinin maliyetli iç alanını yine de hızlandıracaktır. İç alan da bazı yumuşak renklendirme yöntemlerini kullanmadığı sürece, örneğin iç mesafe tahmini.

Simetri kullanımı

Mandelbrot setinin yatay simetrisi, son görüntüde gerçek eksenin varlığı üzerine oluşturma işleminin bölümlerinin atlanmasına izin verir. Bununla birlikte, yansıtılan kısım ne olursa olsun, aynı sayıda nokta işlenecektir.

Julia setlerinin orijini etrafında simetrisi vardır. Bu, çeyrek 1 ve çeyrek 3'ün simetrik olduğu ve çeyrek 2 ve çeyrek 4'ün simetrik olduğu anlamına gelir. Hem Mandelbrot hem de Julia kümeleri için simetriyi desteklemek, simetriyi iki farklı grafik türü için farklı şekilde ele almayı gerektirir.

Çoklu kullanım

Mandelbrot ve Julia setlerinin kaçış zamanı sunumu paralel işlemeye son derece uygun. Çok çekirdekli makinelerde, çizilecek alan bir dizi dikdörtgen alana bölünebilir ve bunlar daha sonra bir işleme iş parçacığı havuzu tarafından gerçekleştirilecek bir dizi görev olarak sağlanabilir. Bu bir utanç verici derecede paralel^[10] bilgi işlem sorunu. (Birinin en iyi hızlanmayı, önce grafiğin simetrik alanlarını çıkararak ve ardından kalan benzersiz bölgeleri dikdörtgen alanlara bölerek elde edeceğinizi unutmayın.)^[11]

Burada, Mandelbrot setinin çoklu okuma ve simetri kullanılarak işlendiğini, ancak sınırlama olmaksızın gösteren kısa bir video var:

Medya oynatın

Bu, bir Mandelbrot setinin çoklu iş parçacığı ve simetri kullanılarak, ancak sınır takibi kapalıyken oluşturulmasını gösteren kısa bir videodur.

Son olarak, burada aynı Mandelbrot set görüntüsünün multithreading, simetri kullanılarak işlenmesini gösteren bir video var. ve sınır takibi:

Medya oynatın

Bu, sınır izleme, çoklu iş parçacığı ve simetri kullanılarak bir Mandelbrot kümesinin oluşturulmasını gösteren kısa bir videodur.

Pertürbasyon teorisi ve seri yaklaşımı

Oldukça yüksek oranda büyütülmüş görüntüler, çoğu donanımın sahip olduğu standart 64–128 bit hassasiyetten fazlasını gerektirir. kayan nokta birimleri oluşturucuların yavaş "BigNum" veya "keyfi hassasiyet "hesaplanacak matematik kitaplıkları. Ancak, bu, pertürbasyon teorisi. Verilen

${ displaystyle z_ {n + 1} = z_ {n} ^ {2} + c}$

yineleme ve küçük bir epsilon ve delta olarak,

${ displaystyle (z_ {n} + epsilon) ^ {2} + (c + delta) = z_ {n} ^ {2} + 2z_ {n} epsilon + epsilon ^ {2} + c + delta, }$

veya

${ displaystyle = z_ {n + 1} + 2z_ {n} epsilon + epsilon ^ {2} + delta,}$

yani biri tanımlarsa

${ displaystyle epsilon _ {n + 1} = 2z_ {n} epsilon _ {n} + epsilon _ {n} ^ {2} + delta,}$

yüksek hassasiyetli aritmetik kullanarak tek bir nokta (örneğin bir görüntünün merkezi) hesaplanabilir (z), vererek referans yörüngeve ardından, çeşitli başlangıç ​​uzaklıkları delta artı epsilon için yukarıdaki yineleme cinsinden birçok noktayı hesaplayın; burada epsilon-sıfır, 0'a ayarlanmıştır. Çoğu yineleme için, epsilon 16'dan fazla anlamlı rakama ihtiyaç duymaz ve sonuç olarak kayan donanım nokta, çoğunlukla doğru bir görüntü elde etmek için kullanılabilir.^[12] Çoğu zaman, noktaların yörüngelerinin referans yörüngeden yeterince uzaklaştığı ve bu noktalarda ekstra hassasiyetin gerekli olduğu bazı alanlar olacaktır, aksi takdirde ek yerel yüksek hassasiyetle hesaplanmış referans yörüngelerine ihtiyaç duyulacaktır. Referans noktası ile düşük hassasiyetle hesaplanan nokta arasındaki yörünge mesafesi ölçülerek noktanın doğru hesaplanmasının mümkün olmadığı tespit edilebilir ve hesaplama durdurulabilir. Bu yanlış noktalar daha sonra yeniden hesaplanabilir, örn. başka bir yakın referans noktasından.

Ayrıca, düşük hassasiyetli noktalar için başlangıç ​​değerlerini kesik bir şekilde yaklaşık olarak tahmin etmek mümkündür. Taylor serisi, bu genellikle önemli miktarda yinelemenin atlanmasını sağlar.^[13]Bu teknikleri uygulayan oluşturucular halka açık ve son derece büyütülmüş görüntüler için yaklaşık iki büyüklük sırası ile hızlandırmalar sunar.^[14]

Yukarıdakilerin alternatif bir açıklaması:

Diskteki merkezi nokta için ${ displaystyle c}$ ve yinelemeleri ${ displaystyle z_ {n}}$ve diskte keyfi bir nokta ${ displaystyle c + delta}$ ve yinelemeleri ${ displaystyle z '_ {n}}$aşağıdaki yinelemeli ilişkiyi tanımlamak mümkündür:

${ displaystyle z '_ {n} = z_ {n} + epsilon _ {n}}$

İle ${ displaystyle epsilon _ {1} = delta}$. Ardışık yinelemeler ${ displaystyle epsilon _ {n}}$ aşağıdakiler kullanılarak bulunabilir:

${ displaystyle z '_ {n + 1} = {z' _ {n}} ^ {2} + (c + delta)}$

${ displaystyle z '_ {n + 1} = (z_ {n} + epsilon _ {n}) ^ {2} + c + delta}$

${ displaystyle z '_ {n + 1} = {z_ {n}} ^ {2} + c + 2z_ {n} epsilon _ {n} + { epsilon _ {n}} ^ {2} + delta}$

${ displaystyle z '_ {n + 1} = z_ {n + 1} + 2z_ {n} epsilon _ {n} + { epsilon _ {n}} ^ {2} + delta}$

Şimdi orijinal tanımdan:

${ displaystyle z '_ {n + 1} = z_ {n + 1} + epsilon _ {n + 1}}$,

Bunu takip eder:

${ displaystyle epsilon _ {n + 1} = 2z_ {n} epsilon _ {n} + { epsilon _ {n}} ^ {2} + delta}$

Yinelemeli ilişki, çok küçük bir değişiklikle merkezi noktaya keyfi bir noktayı ilişkilendirdiğinden ${ displaystyle delta}$, daha sonra yinelemelerin çoğu ${ displaystyle epsilon _ {n}}$ ayrıca küçüktür ve kayan nokta donanımı kullanılarak hesaplanabilir.

Bununla birlikte, diskteki her gelişigüzel nokta için, verilen bir değer için bir değer hesaplamak mümkündür. ${ displaystyle epsilon _ {n}}$ dizi boyunca yinelemek zorunda kalmadan ${ displaystyle epsilon _ {0}}$, ifade ederek ${ displaystyle epsilon _ {n}}$ bir güç serisi olarak ${ displaystyle delta}$.

${ displaystyle epsilon _ {n} = A_ {n} delta + B_ {n} delta ^ {2} + C_ {n} delta ^ {3} + dotsc}$

İle ${ displaystyle A_ {1} = 1, B_ {1} = 0, C_ {1} = 0, dotsc}$.

Şimdi yineleme denklemi verildiğinde ${ displaystyle epsilon}$her biri için kuvvet serilerinin katsayılarını hesaplamak mümkündür. ${ displaystyle epsilon _ {n}}$:

${ displaystyle epsilon _ {n + 1} = 2z_ {n} epsilon _ {n} + { epsilon _ {n}} ^ {2} + delta}$

${ displaystyle epsilon _ {n + 1} = 2z_ {n} (A_ {n} delta + B_ {n} delta ^ {2} + C_ {n} delta ^ {3} + dotsc) + (A_ {n} delta + B_ {n} delta ^ {2} + C_ {n} delta ^ {3} + dotsc) ^ {2} + delta}$

${ displaystyle epsilon _ {n + 1} = (2z_ {n} A_ {n} +1) delta + (2z_ {n} B_ {n} + {A_ {n}} ^ {2}) delta ^ {2} + (2z_ {n} C_ {n} + 2A_ {n} B_ {n}) delta ^ {3} + dotsc}$

Bu nedenle, şunu takip eder:

${ displaystyle A_ {n + 1} = 2z_ {n} A_ {n} +1}$

${ displaystyle B_ {n + 1} = 2z_ {n} B_ {n} + {A_ {n}} ^ {2}}$

${ displaystyle C_ {n + 1} = 2z_ {n} C_ {n} + 2A_ {n} B_ {n}}$

${ displaystyle vdots}$

Kuvvet serisindeki katsayılar, yalnızca merkezi noktanın yinelemelerinden değerler kullanılarak yinelemeli seriler olarak hesaplanabilir. ${ displaystyle z}$ve diskin herhangi bir noktasında değişiklik yapmayın. Eğer ${ displaystyle delta}$ çok küçük, ${ displaystyle epsilon _ {n}}$ Kuvvet serisinin yalnızca birkaç terimi kullanılarak yeterli doğrulukta hesaplanabilir olmalıdır. Mandelbrot Kaçış Konturları karmaşık düzlem üzerinde 'sürekli' olduğundan, eğer bir nokta kaçış süresi hesaplanmışsa, o noktalardaki komşuların kaçış süreleri benzer olmalıdır. Komşu noktaların enterpolasyonu, nerede başlayacağına dair iyi bir tahmin sağlamalıdır. ${ displaystyle epsilon _ {n}}$ dizi.

Ayrıca, hem gerçek eksen noktalarının hem de sanal eksen noktalarının ayrı enterpolasyonu, hesaplanan nokta için hem üst hem de alt sınır sağlamalıdır. Her iki sonuç da aynıysa (yani her ikisi de kaçar veya kaçmazsa) o zaman fark ${ displaystyle Delta n}$ hem üst hem de alt sınır oluşturulana kadar tekrar kullanmak için kullanılabilir. Kayan nokta donanımı, ${ displaystyle epsilon}$ series, then there exists a relation between how many iterations can be achieved in the time it takes to use BigNum software to compute a given ${displaystyle epsilon _{n}}$. If the difference between the bounds is greater than the number of iterations, it is possible to perform binary search using BigNum software, successively halving the gap until it becomes more time efficient to find the escape value using floating point hardware.

Referanslar