An interactive, educational visualization of Fortune's algorithm for computing Voronoi diagrams. Built for computational geometry courses.
Try it in your browser — no install required.
- Click to place Voronoi sites — right-click to remove
- Continuous sweep line moves smoothly left-to-right, processing algorithm events in real time
- Beachline visualization with colored parabolic arcs per site
- Circle events fade in as the sweep approaches, with triggered circles highlighted
- Growing edges trace from their origin to the current breakpoint
- Speed control from 10 px/s (lecture pace) to 800 px/s
- Layer toggles for sweep line, beachline, circle events, and edges
- Step-through mode — pause and skip to the next event
- Live preview of the final Voronoi diagram while placing sites
- Robust handling of degenerate cases (collinear sites, near-duplicates, fast clicking)
bun install
bun run devOpen http://localhost:5173.
Fortune's algorithm computes Voronoi diagrams in O(n log n) by sweeping a vertical line left-to-right across the plane:
- Site events — when the sweep line hits a new site, a parabolic arc is inserted into the beachline
- Circle events — when three consecutive arcs converge, their circumcenter becomes a Voronoi vertex
- Beachline — the frontier of parabolic arcs, each defined by a site (focus) and the sweep line (directrix)
- Edges grow along the breakpoints between adjacent arcs
The visualization renders all of this in real time using HTML Canvas, with the beachline computed at the current (interpolated) sweep position for smooth animation between discrete algorithm events.
├── index.html
├── package.json
├── vite.config.js
└── src/
├── main.jsx # Entry point
└── VoronoiVisualizer.jsx # Algorithm + visualization (single file)
bun run build # Output in dist/
bun run preview # Preview production buildMIT