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 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:

This talk was given at the NYC Clojure Users Group meetup at Two Sigma Investments.