.\" Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28)
.\"
.\" Standard preamble:
.\" ========================================================================
.de Sp \" Vertical space (when we can't use .PP)
.if t .sp .5v
.if n .sp
..
.de Vb \" Begin verbatim text
.ft CW
.nf
.ne \\$1
..
.de Ve \" End verbatim text
.ft R
.fi
..
.\" Set up some character translations and predefined strings.  \*(-- will
.\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
.\" double quote, and \*(R" will give a right double quote.  \*(C+ will
.\" give a nicer C++.  Capital omega is used to do unbreakable dashes and
.\" therefore won't be available.  \*(C` and \*(C' expand to `' in nroff,
.\" nothing in troff, for use with C<>.
.tr \(*W-
.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
.ie n \{\
.    ds -- \(*W-
.    ds PI pi
.    if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
.    if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\"  diablo 12 pitch
.    ds L" ""
.    ds R" ""
.    ds C` ""
.    ds C' ""
'br\}
.el\{\
.    ds -- \|\(em\|
.    ds PI \(*p
.    ds L" ``
.    ds R" ''
.    ds C`
.    ds C'
'br\}
.\"
.\" Escape single quotes in literal strings from groff's Unicode transform.
.ie \n(.g .ds Aq \(aq
.el       .ds Aq '
.\"
.\" If the F register is turned on, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index
.\" entries marked with X<> in POD.  Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
.\"
.\" Avoid warning from groff about undefined register 'F'.
.de IX
..
.nr rF 0
.if \n(.g .if rF .nr rF 1
.if (\n(rF:(\n(.g==0)) \{
.    if \nF \{
.        de IX
.        tm Index:\\$1\t\\n%\t"\\$2"
..
.        if !\nF==2 \{
.            nr % 0
.            nr F 2
.        \}
.    \}
.\}
.rr rF
.\"
.\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
.\" Fear.  Run.  Save yourself.  No user-serviceable parts.
.    \" fudge factors for nroff and troff
.if n \{\
.    ds #H 0
.    ds #V .8m
.    ds #F .3m
.    ds #[ \f1
.    ds #] \fP
.\}
.if t \{\
.    ds #H ((1u-(\\\\n(.fu%2u))*.13m)
.    ds #V .6m
.    ds #F 0
.    ds #[ \&
.    ds #] \&
.\}
.    \" simple accents for nroff and troff
.if n \{\
.    ds ' \&
.    ds ` \&
.    ds ^ \&
.    ds , \&
.    ds ~ ~
.    ds /
.\}
.if t \{\
.    ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
.    ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
.    ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
.    ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
.    ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
.    ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
.\}
.    \" troff and (daisy-wheel) nroff accents
.ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
.ds 8 \h'\*(#H'\(*b\h'-\*(#H'
.ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
.ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
.ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
.ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
.ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
.ds ae a\h'-(\w'a'u*4/10)'e
.ds Ae A\h'-(\w'A'u*4/10)'E
.    \" corrections for vroff
.if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
.if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
.    \" for low resolution devices (crt and lpr)
.if \n(.H>23 .if \n(.V>19 \
\{\
.    ds : e
.    ds 8 ss
.    ds o a
.    ds d- d\h'-1'\(ga
.    ds D- D\h'-1'\(hy
.    ds th \o'bp'
.    ds Th \o'LP'
.    ds ae ae
.    ds Ae AE
.\}
.rm #[ #] #H #V #F C
.\" ========================================================================
.\"
.IX Title "Math::Geometry::Voronoi 3pm"
.TH Math::Geometry::Voronoi 3pm "2009-07-11" "perl v5.20.0" "User Contributed Perl Documentation"
.\" For nroff, turn off justification.  Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.if n .ad l
.nh
.SH "NAME"
Math::Geometry::Voronoi \- compute Voronoi diagrams from sets of points
.SH "SYNOPSIS"
.IX Header "SYNOPSIS"
.Vb 1
\&    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 => \e@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;
.Ve
.SH "DESCRIPTION"
.IX Header "DESCRIPTION"
This module computes Voronoi diagrams from a set of input points.
Info on Voronoi diagrams can be found here:
.PP
.Vb 1
\&  http://en.wikipedia.org/wiki/Voronoi_diagram
.Ve
.PP
This module is a wrapper around a C implementation found here:
.PP
.Vb 1
\&  http://www.derekbradley.ca/voronoi.html
.Ve
.PP
Which is itself a modification of code by Steve Fortune, the inventor
of the algorithm used (Fortune's algorithm):
.PP
.Vb 1
\&  http://cm.bell\-labs.com/who/sjf/
.Ve
.PP
I made changes to the C code to allow reading input and writing output
to/from Perl data-structures.  I also modified the memory allocation
code to use Perl's memory allocator.  Finally, I changed all floats to
doubles to provide better precision and to match Perl's NVs.
.SH "INTERFACE"
.IX Header "INTERFACE"
.SS "new"
.IX Subsection "new"
.Vb 7
\&    my @points = ([1,   2],
\&                  [1,   3],
\&                  [2,   2],
\&                  [0,   1],
\&                  [0,   10],
\&                  [0.5, 11]);
\&    my $geo = Math::Geometry::Voronoi\->new(points => \e@points);
.Ve
.PP
Create a new object, passing in a single required parameter called
\&'points'.  This must be an array or arrays containing at least two
values each, the X,Y values for your points.  Any extra data will be
ignored.
.SS "points"
.IX Subsection "points"
Returns the \fIsorted\fR set of points used by the voronoi algorithm.
This is the ordering refered to by the \fIlines()\fR output below.
.SS "compute"
.IX Subsection "compute"
Call this to build the diagram.  Returns nothing.
.SS "lines"
.IX Subsection "lines"
Returns an array ref containing arrays of lines in the output diagram.
The data by index:
.PP
.Vb 5
\&  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.
.Ve
.PP
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.
.SS "vertices"
.IX Subsection "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:
.PP
.Vb 2
\&  0: the x value
\&  1: the y value
.Ve
.SS "edges"
.IX Subsection "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:
.PP
.Vb 3
\&  0: the index of the line
\&  1: the index of vertex 1
\&  2: the index of vertex 2
.Ve
.PP
Either 1 or 2 can be \-1 meaning \*(L"infinite\*(R".
.SS "polygons"
.IX Subsection "polygons"
.Vb 1
\&  @polys = $geo\->polygons();
.Ve
.PP
This method attempts to assemble polygons from non-infinite edges in
the diagram.  This part of the code is written in Perl and is of my
own invention.  I needed this facility in order to color the diagrams
created by this module.  It seems to work reasonably well for my uses
but I'm sure it's nowhere near the quality of Steve Fortune's code!
Feedback welcome.
.PP
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:
.PP
.Vb 1
\&  @polys = ( $point_index, [$lat1, $lon1], [$lat2, $lon2], ... );
.Ve
.PP
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).  For
example, if your coordinates are on an integer grid you might do:
.PP
.Vb 1
\&  @polys = $geo\->polygons(normalize_vertices => sub { int($_[0]) });
.Ve
.PP
Or if you're using floating point and your coordinates are useful down
to 2 decimal places:
.PP
.Vb 1
\&  @polys = $geo\->polygons(normalize_vertices => sub { sprintf("%.2f", $_[0]) });
.Ve
.PP
The point is to produce coordinates in a format where they will
compare as equal textually, side-stepping the problem of comparing
floats numerically.
.SH "TODO"
.IX Header "TODO"
Possible projects, if you're in the mood to help out:
.PP
.Vb 7
\&  \- Add the ability to combine polygons based on a mapping of
\&    same\-type points.  Map overlays get cluttered by internal lines
\&    with you\*(Aqre coloring multiple polygons the same.  All edges
\&    connect exactly two polygons, so this should be relatively easy.
\&    Sadly, my limited math skills have thwarted me on this one \- I
\&    spent several days but ultimately couldn\*(Aqt get it working 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\*(Aqs actually doing a decent diagram I look at graphical
\&    output.
.Ve
.SH "AUTHOR"
.IX Header "AUTHOR"
Sam Tregar <sam@tregar.com>
.SH "COPYRIGHT AND LICENSE"
.IX Header "COPYRIGHT AND LICENSE"
As far as I can tell the underlying C code used here never had a
license attached to it, or if it did I couldn't find any trace of it.
If this worries you please contact Steve and Derek through the links
above.
.PP
The Perl and \s-1XS\s0 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.