Globus8.jan 2011
    Pri pive a inych spolocenskych akciach obcas vzniknu nove a zaujimave myslienky. Jednou z nich bol aj podnet pre tuto jednoduchu aplikaciu. Predstavme si ze mame nejaku gulu, a mame taktiez N figurok. Otazka znie, ako rozmiestnit figurky tak aby boli vzajomne co najdalej od seba? Otazka sa da jednoducho odhadnut pre N=2 - vtedy budu body lezat na priemere. Pre N=3 vznikne rovnostranny trojuholnik v rovine so stredom. Pre N=4 vznika priestorovy utvar znamy ako stvorsten. Pre N=20 - nikto nevie.
    Pre cloveka s dobrou priestorovou predstavivostou a dobrym matematickym pozadim by to mozno bola jednoducha otazka. Zrejme nepatrim ani do jednej z tychto skupin a kedze ma nenapadol ziadny rozumny system ako postupne ukladat figurky na gulu, rozhodol som sa ze tento problem za mna vyriesi pocitac. Necakajte zazraky, pocitac vie vselico, ale urcite sam od seba nebude vediet vyriesit tuto ulohu.
    Ze vraj sa to vola evolucny algoritmus. Figurky sa najprv nahodne rozmiestnia po guli. A teraz vyskusame experiment. Kazdu figurku posunieme o nejaku malu nahodnu hodnotu. A porovname ktora sada figuriek - ci ta prva, alebo ci tato poposuvana - lepsie charakterizuje nase poziadavky. Pri spravnej formulacii poziadavky staci nechat algoritmus produkovat nove a nove generacie a za par minut sa dopracuje ku finalnemu vysledku.
    Zo slovnej ulohy musime vytvorit akysi matematicky predpis, ktory pocitac bude chapat. Hladame teda taku sadu figuriek pre ktoru su vsetky figurky vzajomne od seba co najviac vzdialene.
    1. Znie to jednoducho, ved skusme si vypocitat vzajomne vsetky vzdialenosti kazdej figurky od kazdej a tieto hodnoty nakoniec scitame. Z nejakeho dovodu tento pristup neposkytoval pouzitelne vysledky - vysledkom bolo ze sa na globuse vytvorili akesi zhluky bodov.
    2. Zamerajme sa na zhluky bodov ktore su tesne pri sebe. Nova podmienka bola formulovana takto: Ta generacia je lepsia v ktorej je vacsia najmensia vzajomna vzdialenost dvoch bodov. Takze najdeme dva body ktore lezia co najblizsie a porovnavame uz iba tuto vzdialenost. Tento pristup funguje, ale je velmi pomaly, kedze pracujeme len s dvomi bodmi a to co sa deje s ostatnymi nas nijako nezaujima
    3. Finalna podmienka ktoru som navrhol: Vypocitajme vsetky vzajomne vzdialenosti figurok a scitajme prevratene hodnoty vsetkych vzdialenosti. Takto krasne eliminujeme efekt zgrupenych figurok a podmienka charakterizuje jednym realnym cislom kompletne rozlozenie figurok na guli.

    Prichadza na rad dalsia otazka - aky programovaci jazyk pouzit? Ako nadsenec novych technologii som si opat vyskusal Canvas element ktory je sucastou HTML5 standardu. Postup generovania generacii som chcel vidiet, takze javascript renderuje pekny globus a na nom aj jednotlive figurky cervenym stvorcekom. Aby bolo lepsie vidiet kde sa ktory bod nachadza, gula pomaly rotuje. Modrou ciarou je zvyraznena minimalna vzdialenost figurok a tato hodnota je zaroven vypisana v lavom hornom rohu canvasu. Program som navrhoval vo Firefoxe, takze netusim ci to bude spustitelne pod inym browserom.
    Pri vysokom pocte figurok (napr N=100) sa vytvoril akysi pravidelny vzor na globuse a bol som zvedavy ako by to vyzeralo v rovine. Vdaka vyhodam jazyku bolo velmi jednoduche pridat dalsie dve projekcie - popri globusu, este cylinder a rovinne zobrazenie.

    A co dalej? Je velmi zaujimave sledovat aka bola dosiahnuta minimalna hodnota vzdialenosti v zavislosti od poctu figurok. Mozno by sa podarilo navrhnut analyticku funkciu parametra N ktora by matematickym predpisom tuto vzdialenost definovala. Mam vsak zly pocit ze ku tomuto vysledku sa da dopracovat iba casovo zdlhavym testovanim a jednoduchy matematicky predpis ku tomuto neexistuje. Zrejme to bude rovnaky problem ako keby sme chceli sfleku urcit X-te cislo Fibonacciho postupnosti. Ked sa mi to ale podari, bude sa tento predpis volat "Gabova funkcia" :)


  
  
Tags: html5, canvas, javascript, 3d, projection, render, globe, sphere, cylinder, plane, rotation, normal distribution, genetic algorithm, random number generator