Math::...Voronoi(3pm)

📦
version 1.3 · 8 versions
, in ubuntu stonking

💖 Math::Geometry::Voronoi — bestie edition 💖

okay so this is the manual page for Math::Geometry::Voronoi (that's the Perl module, filed under section 3pm, User Contributed Perl Documentation, iykyk) and it is genuinely one of the cutest little geometry modules out there. It computes Voronoi diagrams from sets of points. Let's get into it, no cap.

✨ NAME ✨

Math::Geometry::Voronoi — compute Voronoi diagrams from sets of points 🦋

✨ SYNOPSIS ✨

use Math::Geometry::Voronoi;

# load a set of points
my @points = ([1,   2],
              [1,   3],
              [2,   2],
              [0,   1],
              [0,   10],
              [0.5, 11]);
my $geo = Math::Geometry::Voronoi->new(points => \@points);

# compute your diagram
$geo->compute;

# extract features
my $lines    = $geo->lines;
my $edges    = $geo->edges;
my $vertices = $geo->vertices;

# build polygons
my @polygons = $geo->polygons;

like… look at her. ten lines and you have a whole diagram. 💅

✨ DESCRIPTION ✨

This module computes Voronoi diagrams from a set of input points. If you wanna know what a Voronoi diagram even is, the info lives here:

http://en.wikipedia.org/wiki/Voronoi_diagram

This module is a wrapper around a C implementation found here, fr fr:

http://www.derekbradley.ca/voronoi.html

Which is itself a modification of code by Steve Fortune, the actual inventor of the algorithm being used (Fortune's algorithm) — iconic behavior honestly:

http://cm.bell-labs.com/who/sjf/

The author made some changes to that C code to allow reading input and writing output to/from Perl data-structures. Also rewrote the memory allocation code to use Perl's memory allocator. And finally, changed all floats to doubles to get better precision and to match Perl's NVs. slay. 🔥

✨ INTERFACE ✨

🌸 new

my @points = ([1,   2],
              [1,   3],
              [2,   2],
              [0,   1],
              [0,   10],
              [0.5, 11]);
my $geo = Math::Geometry::Voronoi->new(points => \@points);

Create a new object, passing in a single required parameter called 'points'. This has to be an array of arrays, and each inner array needs at least two values — those are your X,Y values for each point. Any extra data in there? straight up ignored, bestie. 🫶

🌸 points

Returns the sorted set of points used by the voronoi algorithm. This is the ordering that the lines() output below refers to. 👑

🌸 compute

Call this to build the diagram. Returns nothing. that's it, that's the whole girl. 💀

🌸 lines

Returns an array ref containing arrays of lines in the output diagram. Here's the data by index:

  • 0: the a value in the ax + by = c equation for the line
  • 1: the b value
  • 2: the c value
  • 3: the index of one point for which this line is the bisector
  • 4: the index of the other point for which this line is the bisector
⚠️ note that 3 and 4 are not the end-points of the line — they are points perpendicular to the line. Either 3 or 4 may be -1, meaning no point. don't get it twisted!! 😭

🌸 vertices

Returns an array ref containing arrays of vertices in the output diagram. These are the points which connect edges running along the lines. The data by index:

  • 0: the x value
  • 1: the y value

🌸 edges

Returns an array ref containing arrays of edges in the output diagram. An edge is defined as a segment of a line running between two vertices. The data by index:

  • 0: the index of the line
  • 1: the index of vertex 1
  • 2: the index of vertex 2

Either 1 or 2 can be -1, meaning "infinite". ✨

🌸 polygons

@polys = $geo->polygons();

This method attempts to assemble polygons from non-infinite edges in the diagram. This part of the code is written in Perl and is the author's own invention — the author needed this facility in order to color the diagrams created by this module. It seems to work reasonably well for the author's uses, but ngl, it's surely nowhere near the quality of Steve Fortune's code! Feedback welcome. 🎀

This method returns a reference to an array containing first a point index and then a list of vertex coordinates. The point is the point inside the polygon, and the vertices are in drawing order for the closed polygon surrounding the point. For example:

@polys = ( $point_index, [$lat1, $lon1], [$lat2, $lon2], ... );

One optional parameter is available — normalize_vertices. This option is necessary because the algorithm used needs to match up points from one edge to another, and doing that with floating point numbers requires some kind of normalization (otherwise 1.1 != 1.10001, and we simply cannot). For example, if your coordinates are on an integer grid you might do:

@polys = $geo->polygons(normalize_vertices => sub { int($_[0]) });

Or if you're using floating point and your coordinates are useful down to 2 decimal places:

@polys = $geo->polygons(normalize_vertices => sub { sprintf("%.2f", $_[0]) });

The point is to produce coordinates in a format where they will compare as equal textually, side-stepping the problem of comparing floats numerically. genius honestly 💅

✨ TODO ✨

Possible projects, if you're in the mood to help out:

  • Add the ability to combine polygons based on a mapping of same-type points. Map overlays get cluttered by internal lines when you're coloring multiple polygons the same. All edges connect exactly two polygons, so this should be relatively easy. Sadly, the author's limited math skills thwarted this one — several days were spent on it but ultimately it couldn't be made to work reliably on all possible shapes. 😭
  • Remove the need for the normalize_vertices option to polygons(), somehow (fuzzy matching?).
  • Setup a site where people can play with the module visually and see purty colors. Could be an excuse to play with the new canvas stuff in modern browsers. 🎨
  • Add tests that actually examine the output for sanity. So far the tests just look at the format and range of the output data — to see if it's actually doing a decent diagram, the author looks at graphical output. 🙈

✨ AUTHOR ✨

Sam Tregar <sam@tregar.com>

As far as the author can tell, the underlying C code used here never had a license attached to it, or if it did, no trace of it could be found. If this worries you, please contact Steve and Derek through the links above. 🫶

The Perl and XS code in this library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.8.5 or, at your option, any later version of Perl 5 you may have available.

and that's the whole page bestie!! 🌈✨ filed by perl v5.42.3, dated 2026-08-21 — so this documentation is giving vintage-that's-actually-future, main character energy. go forth and draw some polygons 💖🦋🎀

📦 where this page comes from