Prírodou inšpirované algoritmy

Princíp

Princíp tvorby rekurzívnych Voronoiovych diagramov.

Na nasledujúcich obrázkoch si vysvetlíme tvorbu Voronoiovych diagramov s použitím rekurzie. Na nasledujúcom obrázku je znázornené rozdelenie plochy okolo dvoch bodov.

Na plochu pridáme ďalší bod. Na nasledujúcom obrázku vidíme, že po pridaní ďalšieho bodu sa nám zmení aj rozdelenie plochy.

V prípade, že vložíme na plochu väčší počet bodov bude plocha rozdelená na väčší počet častí. Na ďalšom obrázku vidíme jednu z možností náhodne vytvoreného Voronoiovho diagramu. V ďalších krokoch si na donom Voronoiovom diagrame vysvetlíme rekurzívnu tvorbu Voronoiovych diagramov.

V prvom kroku si pre názornosť vyberieme iba jednu ohraničenú plochu do ktorej si vložíme nové body. Tieto body sú na nasledujúcom obrázku znázornené modrou farbou a sú väčšie ako body v pôvodnom Voronoiovom diagrame. Okolo týchto bodov si na nami zvolenej ploche vytvoríme Voronoiov diagram. Deliace čiary sú znázornené fialovou farbou a sú tenšie ako deliace čiary v pôvodnom diagrame. Pri tvorbe tohto Voronoiovho diagramu neberieme do úvahy hlavný bod z predchádzajúceho kroku rekurzie, ktorý je na obrázku znázornený červenou farbou a je menší.

Podobne ako na predchádzajúcom si aj na nasledujúcom obrázku vytvoríme Voronoiove diagramy. V tomto kroku rekurzie by sme mali takéto diagramy vytvoriť na každej ploche ohraničenej zelenými čiarami, ale pre názornosť a jednoduchosť obrázku si vytvoríme takéto Voronoiove diagramy len na troch nami zvolených plochách.

Predstavme si, že máme vytvorené Voronoiove diagramy na všetkých plochách ohraničených zelenými deliacimi čiarami. Prišiel čas spraviť ďalší krok rekurzie. Pre názornosť to opäť predvedieme len na jednej ploche, ktorá vznikla v predchádzajúcom kroku rekurzie. Tato plocha je ohraničená zelenými čiarami, alebo ako v našom prípade na ďalšom obrázku, kde sme si vybrali plochu ktorá má hranicu tejto plochy ešte z prvého rozdelenia celej plochy a teda aj inú farbu. Do nami zvolenej plochy vložíme body okolo ktorých vytvoríme Voronoiov diagram.

V tejto kapitole sme sa snažili vysvetliť princíp tvorby rekurzívnych Voronoiovych diagramov. Pre názornosť sme použili rôzne farby deliacich čiar a aj hlavných bodov v jednotlivých krokoch rekurzie. Ak by sme napríklad chceli dosiahnuť prirodzený vzhľad povrchu listov, použili by sme v každom kroku rovnakú farbu, pričom v každom nasledujúcom kroku rekurzie by sa nám deliace čiary stenčovali a na konci by sme z obrázku odstránili všetky body. Výsledný obrazec by sa skladal len z deliacich čiar, čím by sme dosiahli efekt žilovitého povrchu listu ako nám zobrazuje posledný obrázok.