Voroného diagram v JavaScriptu

Už dlouhou dobu mě láká vyzkoušet si práci s JavaScriptem. Přece jen je to hlavní otevřený jazyk pro web, navíc v posledních letech vznikla řada opravdu rychlých interpretů pro JS.

Čím je JS zajímavý

Doposud jsem o JS věděl pouze to, že je hodně podobný ActionScriptu a že nemá třídy.

Zní to zvláštně, ale je to tak. JavaScript je objektově orientovaný, stejně jako ActionScript nebo C++, ale datové typy ani třídy v něm neexistují. Namísto tříd se používá Prototypové programování. Je trochu těžké zvyknout si na absenci tříd, avšak po chvíli už vám to nebude vadit, nebo vám se to nedej bože začne líbit :)

Přepis kódu z ActionScriptu do JS

Se způsobem programování v JS jsem se seznámil ve článku na wikipedii. Vypadalo to celkem jasně a jako cvičení jsem si řekl, že přepíši svoji knihovnu pro Voroného diagramy, kterou už mám napsanou v ActionScriptu a C++. Ze začátku jsem se trochu bál, že bude těžké přepsat AS do JS, ale nakonec to bylo až podezřele jednoduché, a co je ještě divnější, ono to i fungovalo! Během necelé hodiny bylo vše hotové.

Výsledek

Výsledek můžete vidět výše. Diagramy vykresluji do HTML elementu "canvas". Bohužel jsem neměl implementaci haldy pro prioritní frontu a místo ní jsem použil pole. Časová složitost je tak $O(n^2)$ místo $O(n * log(n))$, kterou má flešová a C++ verze. Pomalost se může projevit při vysokém počtu bodů.

Přepis běžných imperativních objektových jazyků do JS by se dal shrnout do těchto bodů:

• Odstranit specifikace typů při definici proměnných
  
  • int a = 5; var a:int = 5; => var a = 5;
• Přepsat definice tříd na definice funkcí. Když se tyto funkce zavolají s "new", chovají se jako konstruktory
• Všechny metody tříd napojit na prototyp konstruktorů