Javascript implementation of Steven J. Fortune's algorithm to compute Voronoi diagrams

Main page

Intro

See my blog post regarding this page. This page uses an out of date version (and customized to serve as a tutorial of Fortune's algorithm) of the Javascript Voronoi object. However the demo pages listed above use the latest version.

Sites generator ▵

or sites randomly (Warning: performance might suffer the more sites you add.)

Canvas ▵

canvas W × H to pixels × pixels, with a margin of pixels.

Event queue

(down arrow works too)

pixel(s)
every ms

Scrutinize...

Red beach sections are collapsing (meaning there is a Fortune circle event associated with them), while green beach sections are expanding. When all the Fortune events have been processed, a beachline most likely still exists, which means the start and/or end points of the edges implied by each pair of beach sections are not connected, in which case we must ‘manually’ connect these dangling lines to the bounding box, or discard them if they are outside the viewport.

Portions of this software are based on, or depend on, or are inspired from the work of...

“Fortune's algorithm” by Steven Fortune: For his clever algorithm to compute Voronoi diagrams. (Powerpoint detailing the algorithm)
Alec McEachran's code to translate a parabola's focal & directrix into parameters for html5 <canvas>' quadraticCurveTo() method. It occurred to me I could use a Bézier curve to draw a parabolic front, and when I plugged "bézier from focus directrix" in a search engine to find out if someone already went through this, Alec's site was on the first page of results, and his tutorial and accompanying code worked like a charm. His code allows for parabolas with any orientation, so it could be simplified for the current case where parabolas are always oriented vertical and upward.
“The Liang-Barsky line clipping algorithm in a nutshell!”, to efficiently clip a line within a rectangle.