Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Re: Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks

by BrowserUk (Patriarch)
on Jul 05, 2008 at 06:20 UTC ( [id://695660]=note: print w/replies, xml ) Need Help??


in reply to Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks

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; }

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Replies are listed 'Best First'.
Re^2: Better maps with Math::Geometry::Voronoi, and a Challenge for Math Monks
by samtregar (Abbot) on Jul 07, 2008 at 16:58 UTC
    Thanks, this is very useful. Have you looked at whether the extra poly is present in the lines() and edges()? That's the data that comes straight from the C implementation. If not, no problem, that's the first thing I'll look at.

    -sam

      No. Lines() and Edges() return 36 elements each. These are the 30 edges that make up the 9 polygons, plus six lines off the edge of the coordinate space, which are not part of any complete polygon.

      So the polygons() method must be manufacturing the extra poly.


      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
        Cool, no suprise there. The polygon() method is all my work, so much more likely to be flawed than Steve Fortune's C code! I'll see if I can fix the problem.

        -sam

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://695660]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others browsing the Monastery: (2)
As of 2024-03-19 06:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found