Question 1

What is a Voronoi diagram?

Accepted Answer

A Voronoi diagram is a specific type of decomposition of a metric space determined by distances to a specified discrete set of objects in the space. Essentially, it partitions a plane into regions close to each seed point, where every location in a given region is closer to its respective seed than to any other.

These diagrams are used extensively in fields like biology for modeling cell growth, in urban planning for facility location analysis, and in computer graphics for texture generation. This tool provides a visual way to understand how these complex spatial patterns emerge from simple sets of points.

Question 2

How does Fortune's Algorithm work for generating diagrams?

Accepted Answer

Fortune's algorithm is a sweep-line algorithm used to construct the Voronoi diagram for a set of points in a plane. It uses a horizontal line (the sweep line) that moves across the plane, maintaining a 'beach line'—a complex curve consisting of parabolic arcs.

The algorithm processes two types of events: site events, where the sweep line hits a new input point, and circle events, where a parabola on the beach line shrinks to a point and disappears. By efficiently managing these events using a priority queue and a balanced binary search tree, the algorithm constructs the diagram in O(n log n) time.

Question 3

Is this tool suitable for educational purposes?

Accepted Answer

Absolutely. This visualizer is designed as an interactive, hands-on educational resource for students, teachers, and developers interested in computational geometry. By breaking down the complex steps of the sweep-line process, it makes abstract algorithmic concepts accessible and concrete.

Users can observe the state of the beach line, pause the execution to inspect specific circle events, and add their own custom points to see how the geometry reacts. This immediate feedback loop is significantly more effective for learning than static diagrams found in textbooks.

Question 4

How do I save my generated Voronoi diagrams?

Accepted Answer

You can export the current state of your diagram directly from the browser as a high-quality SVG or PNG image. Simply use the 'Export' control button located in the sidebar to trigger a download of your visual creation, allowing you to use it in reports, presentations, or further design work.

Please note that since this is a self-contained, browser-based tool without a backend or persistent storage, any diagrams not exported will be lost if you refresh or close the browser tab. We recommend downloading your favorite configurations as you create them to ensure you keep a record of your work.

Free Interactive Voronoi Diagram & Fortune's Algorithm Visualizer