1Math::Geometry::VoronoiU(s3e)r Contributed Perl DocumentaMtaitohn::Geometry::Voronoi(3)
2
6 Math::Geometry::Voronoi - compute Voronoi diagrams from sets of points
7
9 use Math::Geometry::Voronoi;
10 # 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 # compute your diagram
21 $geo->compute;
22 # extract features
24 my $lines = $geo->lines;
25 my $edges = $geo->edges;
26 my $vertices = $geo->vertices;
27 # build polygons
29 my @polygons = $geo->polygons;
30
32 This module computes Voronoi diagrams from a set of input points. Info
33 on Voronoi diagrams can be found here:
34 http://en.wikipedia.org/wiki/Voronoi_diagram
36 This module is a wrapper around a C implementation found here:
38 http://www.derekbradley.ca/voronoi.html
40 Which is itself a modification of code by Steve Fortune, the inventor
42 of the algorithm used (Fortune's algorithm):
43 http://cm.bell-labs.com/who/sjf/
45 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
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 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 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 compute
71 Call this to build the diagram. Returns nothing.
72 lines
74 Returns an array ref containing arrays of lines in the output diagram.
75 The data by index:
76 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 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 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 0: the x value
92 1: the y value
93 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 0: the index of the line
100 1: the index of vertex 1
101 2: the index of vertex 2
102 Either 1 or 2 can be -1 meaning "infinite".
104 polygons
106 @polys = $geo->polygons();
107 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 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 @polys = ( $point_index, [$lat1, $lon1], [$lat2, $lon2], ... );
121 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 @polys = $geo->polygons(normalize_vertices => sub { int($_[0]) });
129 Or if you're using floating point and your coordinates are useful down
131 to 2 decimal places:
132 @polys = $geo->polygons(normalize_vertices => sub { sprintf("%.2f", $_[0]) });
134 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
140 Possible projects, if you're in the mood to help out:
141 - 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 - Remove the need for the normalize_vertices option to polygons(),
151 somehow (fuzzy matching?).
152 - 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 - 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
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 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.
175perl v5.36.0 2023-01-20 Math::Geometry::Voronoi(3)