JavaScript Voronoi diagram
This is a pure JavaScript implementation of an incremental algorithm for a planar ordinary
Voronoi diagram. The algorithm uses a quaternary tree for spatial indexing to enhance
performance and facilitate efficient nearest neighbor searches. The geometry is represented
by a winged-edge data structure. This provides a succinct representation from which
information such as the minimum spanning tree can be derived.
An incremental algorithm was chosen over Fortune's sweepline solution so that new points can be inserted into the diagram without needing to regenerate the whole tessellation. The use of the quaternary tree also reduces the average time complexity to O(n).
Tested in Chrome, Firefox, Opera, Safari and Internet Explorer 6. Works in IE via use of excanvas. (See test.html in the download.)
Since VML renders very slowly in IE it is advised that the fillPolygons option is set to false when the script is run in IE, especially when there are a substantial number of points in the diagram.
An incremental algorithm was chosen over Fortune's sweepline solution so that new points can be inserted into the diagram without needing to regenerate the whole tessellation. The use of the quaternary tree also reduces the average time complexity to O(n).
Tested in Chrome, Firefox, Opera, Safari and Internet Explorer 6. Works in IE via use of excanvas. (See test.html in the download.)
Since VML renders very slowly in IE it is advised that the fillPolygons option is set to false when the script is run in IE, especially when there are a substantial number of points in the diagram.