Sam. I've finally come up with an example that I believe proves that M::G::V is producing wrong output. Whether the underlying library, or something happens on the way through I cannot identify.

If you run the following code, it produces 10 polygons, including the triangle that appears as an asymmetry at roughly 11 o'clock, in the png produced.

However, when I feed the same points into this voronoi applet, only 9 polygons and no asymmetry result. ( You have to feed the points into that applet by clicking, so I've arranged the input data in roughly the correct (physical) pattern in the code below.)

If you compare the results from the two implementations I think you'll agree that M::G::V is producing an extraneous polygon.

#! perl -slw
use strict;
use GD;
use Data::Dump qw[ pp ]; $Data::Dump::MAX_WIDTH = 200;
use Math::Geometry::Voronoi;

my @points = (
    [150,150],            [500,150],             [850,150],


                          [500,300],

                [429,329],          [429,471],

            [400,400],    [500,400],    [600,400],

                [571,329],          [571,471],

                          [500,500],


    [150,650],            [500,650],              [850,650],
);


my $geo = Math::Geometry::Voronoi->new( points => \@points );
$geo->compute;

my @geoPolys = $geo->polygons;
pp \@geoPolys;

my @gdPolys = map { gdPolyFromPoints( @{ $_ }[ 1 .. $#$_ ] ); } @geoPo
+lys;

my $img = GD::Image->new( 1000, 800, 1 );
$img->filledRectangle( 0, 0, 1000, 800, 0x00ffffff );

my $color = 0xA0;
for ( @gdPolys ) {
    $img->filledPolygon( $_, rgb2n( $color, $color, $color ) );
    $color -= 0x10;
}

open IMG, '>:raw', 'voronoi-t.png' or die $!;
print IMG $img->png;
close IMG;

system 'voronoi-t.png';


sub rgb2n{ unpack 'N', pack 'CCCC', 0x40, @_ }

sub gdPolyFromPoints {
    return unless @_;
    my $p = new GD::Polygon;
    $p->addPt( @$_ ) for @_;
    return $p;
}
[download]