Calculating and Visualizing Voronoi Diagrams using the Quad-Edge Structure – Alan Shaw

(written by lawrence krubner, however indented passages are often quotes). You can contact lawrence at: lawrence@krubner.com

Allan Shaw talks about a data structure called a “quad edge”. There were a lot of ideas here that were new to me. The data structure keeps rotation as one value, and the orientation of the edge as one value, but anything like coordinates are kept in a field called “data”. This separates the topology from the geometry. There is also a “next” function to find the next edge. This, apparently, gives great advantage when calculating a whole network of points, though I would have to work with this before I could understand where the computational advantage comes from.

Source