1Math::Geometry::VoronoiU(s3e)r Contributed Perl DocumentaMtaitohn::Geometry::Voronoi(3)
2
3
4

NAME

6       Math::Geometry::Voronoi - compute Voronoi diagrams from sets of points
7

SYNOPSIS

9           use Math::Geometry::Voronoi;
10
11           # load a set of points
12           my @points = ([1,   2],
13                         [1,   3],
14                         [2,   2],
15                         [0,   1],
16                         [0,   10],
17                         [0.5, 11]);
18           my $geo = Math::Geometry::Voronoi->new(points => \@points);
19
20           # compute your diagram
21           $geo->compute;
22
23           # extract features
24           my $lines    = $geo->lines;
25           my $edges    = $geo->edges;
26           my $vertices = $geo->vertices;
27
28           # build polygons
29           my @polygons = $geo->polygons;
30

DESCRIPTION

32       This module computes Voronoi diagrams from a set of input points.  Info
33       on Voronoi diagrams can be found here:
34
35         http://en.wikipedia.org/wiki/Voronoi_diagram
36
37       This module is a wrapper around a C implementation found here:
38
39         http://www.derekbradley.ca/voronoi.html
40
41       Which is itself a modification of code by Steve Fortune, the inventor
42       of the algorithm used (Fortune's algorithm):
43
44         http://cm.bell-labs.com/who/sjf/
45
46       I made changes to the C code to allow reading input and writing output
47       to/from Perl data-structures.  I also modified the memory allocation
48       code to use Perl's memory allocator.  Finally, I changed all floats to
49       doubles to provide better precision and to match Perl's NVs.
50

INTERFACE

52   new
53           my @points = ([1,   2],
54                         [1,   3],
55                         [2,   2],
56                         [0,   1],
57                         [0,   10],
58                         [0.5, 11]);
59           my $geo = Math::Geometry::Voronoi->new(points => \@points);
60
61       Create a new object, passing in a single required parameter called
62       'points'.  This must be an array or arrays containing at least two
63       values each, the X,Y values for your points.  Any extra data will be
64       ignored.
65
66   points
67       Returns the sorted set of points used by the voronoi algorithm.  This
68       is the ordering refered to by the lines() output below.
69
70   compute
71       Call this to build the diagram.  Returns nothing.
72
73   lines
74       Returns an array ref containing arrays of lines in the output diagram.
75       The data by index:
76
77         0: the a value in the ax + by = c equation for the line
78         1: the b value
79         2: the c value
80         3: the index of one point for which this line is the bisector.
81         4: the index of the other point for which this line is the bisector.
82
83       Note that 3 and 4 are not the end-points of the line - they are points
84       perpendicular to the line.  Either 3 or 4 may be -1 meaning no point.
85
86   vertices
87       Returns an array ref containing arrays of vertices in the output
88       diagram.  These are the points which connect edges running along the
89       lines.  The data by index:
90
91         0: the x value
92         1: the y value
93
94   edges
95       Returns an array ref containing arrays of edges in the output diagram.
96       An edge is defined as a segment of a line running between two vertices.
97       The data by index:
98
99         0: the index of the line
100         1: the index of vertex 1
101         2: the index of vertex 2
102
103       Either 1 or 2 can be -1 meaning "infinite".
104
105   polygons
106         @polys = $geo->polygons();
107
108       This method attempts to assemble polygons from non-infinite edges in
109       the diagram.  This part of the code is written in Perl and is of my own
110       invention.  I needed this facility in order to color the diagrams
111       created by this module.  It seems to work reasonably well for my uses
112       but I'm sure it's nowhere near the quality of Steve Fortune's code!
113       Feedback welcome.
114
115       This method returns a reference to an array containing first a point
116       index and then a list of vertex coordinates.  The point is the point
117       inside the polygon and the vertices are in drawing order for the closed
118       polygon surrounding the point.  For example:
119
120         @polys = ( $point_index, [$lat1, $lon1], [$lat2, $lon2], ... );
121
122       One optional parameter is available - normalize_vertices.  This option
123       is necessary because the algorithm used needs to match up points from
124       one edge to another and doing that with floating point numbers requires
125       some kind of normalization (otherwise 1.1 != 1.10001).  For example, if
126       your coordinates are on an integer grid you might do:
127
128         @polys = $geo->polygons(normalize_vertices => sub { int($_[0]) });
129
130       Or if you're using floating point and your coordinates are useful down
131       to 2 decimal places:
132
133         @polys = $geo->polygons(normalize_vertices => sub { sprintf("%.2f", $_[0]) });
134
135       The point is to produce coordinates in a format where they will compare
136       as equal textually, side-stepping the problem of comparing floats
137       numerically.
138

TODO

140       Possible projects, if you're in the mood to help out:
141
142         - Add the ability to combine polygons based on a mapping of
143           same-type points.  Map overlays get cluttered by internal lines
144           with you're coloring multiple polygons the same.  All edges
145           connect exactly two polygons, so this should be relatively easy.
146           Sadly, my limited math skills have thwarted me on this one - I
147           spent several days but ultimately couldn't get it working reliably
148           on all possible shapes.
149
150         - Remove the need for the normalize_vertices option to polygons(),
151           somehow (fuzzy matching?).
152
153         - Setup a site where people can play with the module visually and
154           see purty colors.  Could be an excuse to play with the new canvas
155           stuff in modern browsers.
156
157         - Add tests that actually examine the output for sanity. So far the
158           tests just look at the format and range of the output data - to
159           see if it's actually doing a decent diagram I look at graphical
160           output.
161

AUTHOR

163       Sam Tregar <sam@tregar.com>
164
166       As far as I can tell the underlying C code used here never had a
167       license attached to it, or if it did I couldn't find any trace of it.
168       If this worries you please contact Steve and Derek through the links
169       above.
170
171       The Perl and XS code in this library is free software; you can
172       redistribute it and/or modify it under the same terms as Perl itself,
173       either Perl version 5.8.5 or, at your option, any later version of Perl
174       5 you may have available.
175
176
177
178perl v5.34.0                      2021-07-22        Math::Geometry::Voronoi(3)
Impressum