Calculating and Visualizing Voronoi Diagrams using the Quad-Edge Structure
Developer Alan Shaw talks about Guibas and Stolfi's quad-edge structure and demonstrates the symmetries that make it so beautiful: it's capable of simultaneously representing a graph, its dual, and its mirror image; it exports just two topological primitives which suffice to implement arbitrary graph construction; and all operations are reversible.
He also explores the Voronoi diagram, mentions some of its application domains, and looks at some of its related structures.
The implementation uses @toxi's thi.ng/geom Clojure/ClojureScript libraries for computational geometry; a generic Om/canvas animator component; Om's time-machine capability; and some function decorators for pre-, post-, and substitute actions to facilitate recording and playback of algorithm results, incidental computations, and debug/logging information.
Repository available here: https://github.com/nodename/edge-algebra
This talk was given at the NYC Clojure Users Group meetup at Two Sigma Investments.