Math-Polygon-Tree
view release on metacpan or search on metacpan
0.04 2010-11-07
* added .poly files support
0.035 2010-04-27
* added contains_points method
0.03 2009-11-17
* boundaries are now reported as included
* removed Perl 5.8 incompatibility
* removed Math::Polygon dependency
* fixed POD to pass tests
0.02 2009-08-27
First public release
Makefile.PL view on Meta::CPAN
my %WriteMakefileArgs = (
"ABSTRACT" => "fast check if point is inside polygon\r",
"AUTHOR" => "liosha <liosha\@cpan.org>",
"CONFIGURE_REQUIRES" => {
"ExtUtils::MakeMaker" => 0
},
"DISTNAME" => "Math-Polygon-Tree",
"EXE_FILES" => [],
"LICENSE" => "perl",
"NAME" => "Math::Polygon::Tree",
"PREREQ_PM" => {
"Carp" => 0,
"Exporter" => 0,
"List::MoreUtils" => 0,
"List::Util" => 0,
"Math::Geometry::Planar::GPC::PolygonXS" => 0,
"POSIX" => 0,
"base" => 0,
"strict" => 0,
"utf8" => 0,
lib/Math/Polygon/Tree.pm view on Meta::CPAN
package Math::Polygon::Tree;
$Math::Polygon::Tree::VERSION = '0.08';
# ABSTRACT: fast check if point is inside polygon
# $Id$
use 5.010;
use strict;
use warnings;
use utf8;
use Carp;
lib/Math/Polygon/Tree.pm view on Meta::CPAN
# filled part
if (
@slice_parts == 1 && @{$slice_parts[0]} == 4
&& all { ($_->[0]==$x0 || $_->[0]==$x1) && ($_->[1]==$y0 || $_->[1]==$y1) } @{$slice_parts[0]}
) {
$subparts->[$i]->[$j] = 1;
next;
}
# complex subpart
$subparts->[$i]->[$j] = Math::Polygon::Tree->new( @slice_parts, (%opt ? \%opt : ()) );
}
}
return $self;
}
sub read_poly_file {
lib/Math/Polygon/Tree.pm view on Meta::CPAN
1;
__END__
=pod
=encoding UTF-8
=head1 NAME
Math::Polygon::Tree - fast check if point is inside polygon
=head1 VERSION
version 0.08
=head1 SYNOPSIS
use Math::Polygon::Tree;
my $poly = [ [0,0], [0,2], [2,2], ... ];
my $bound = Math::Polygon::Tree->new( $poly );
if ( $bound->contains( [1,1] ) ) { ... }
=head1 DESCRIPTION
Math::Polygon::Tree creates a tree of polygon parts for fast check if object is inside this polygon.
This method is effective if polygon has hundreds or more segments.
=head1 METHODS
=head2 new
Takes contours and creates a tree structure.
All polygons are outers, inners are not implemented.
Contour is an arrayref of points:
my $poly1 = [ [0,0], [0,2], [2,2], ... ];
...
my $bound = Math::Polygon::Tree->new( $poly1, $poly2, ..., \%opt );
or a .poly file
my $bound1 = Math::Polygon::Tree->new( \*STDIN );
my $bound2 = Math::Polygon::Tree->new( 'boundary.poly' );
Options:
prepare_rough
=head2 contains
my $is_inside = $bound->contains( [1,1] );
if ( $is_inside ) { ... }
lib/Math/Polygon/Tree.pm view on Meta::CPAN
my $united_bbox = bbox_union($bbox1, $bbox2);
Returns united bbox for two bboxes/points.
=head2 polygon_centroid
my $center_point = polygon_centroid( [ [1,1], [1,2], [2,2], ... ] );
Returns polygon's weightened center.
Math::Polygon 1.02+ has the same function, but it is very inaccurate.
=head2 polygon_contains_point
my $is_inside = polygon_contains_point($point, $polygon);
Function that tests if polygon contains point (modified one from Math::Polygon::Calc).
Returns -1 if point lays on polygon's boundary
=head1 AUTHOR
liosha <liosha@cpan.org>
=head1 COPYRIGHT AND LICENSE
This software is copyright (c) 2015 by liosha.
t/bbox_union.t view on Meta::CPAN
#!/usr/bin/perl
use 5.010;
use strict;
use warnings;
use utf8;
use Test::More;
use Math::Polygon::Tree;
our @TESTS = (
[ [[0,0]], [0,0,0,0], 'single point' ],
[ [[0,1],[1,0]], [0,0,1,1], 'two points' ],
[ [[0,0,1,1]], [0,0,1,1], 'single bbox' ],
[ [[0,0,1,1],[2,3]], [0,0,2,3], 'point with bbox' ],
[ [[0,0,2,2],[1,0,2,3]], [0,0,2,3], 'two bboxes' ],
);
for my $test ( @TESTS ) {
my ($in, $expected, $name) = @$test;
my $got = Math::Polygon::Tree::bbox_union(@$in);
is_deeply( $got, $expected, $name );
}
done_testing();
t/contains.t view on Meta::CPAN
#!/usr/bin/perl
use 5.010;
use strict;
use warnings;
use utf8;
use Test::More;
use Math::Polygon::Tree;
our @TESTS = (
[
triangle => [[0,0],[2,0],[0,2]],
[ [0,0], -1, 'vertex point' ],
[ [0,1], -1, 'edge point 1' ],
[ [1,1], -1, 'edge point 2' ],
[ [0.5,0.5], 1, 'inside' ],
[ [1.5,1.5], 0, 'outside' ],
t/contains.t view on Meta::CPAN
[ [34.4141363,54.5091271], 1, 'inside near border' ],
[ [35.3430604,55.2730587], -1,'local upper vertex' ],
[ [8,8], 0, 'very far outside' ],
# [ [], 1, '' ],
],
);
for my $item ( @TESTS ) {
my ($case, $contour, @tests) = @$item;
my $t = Math::Polygon::Tree->new($contour);
for my $test ( @tests ) {
my ($in, $expected, $name) = @$test;
my $got = $t->contains($in);
is( $got, $expected, "$case: $name" );
}
}
done_testing();
t/contains_points.t view on Meta::CPAN
#!/usr/bin/perl
use 5.010;
use strict;
use warnings;
use utf8;
use Test::More;
use Math::Polygon::Tree;
our @TESTS = (
[
triangle => [[0,0],[4,0],[0,4]],
[ [[1,1],[2,1]], 1, 'all inside' ],
[ [[5,5],[6,6]], 0, 'all outside' ],
[ [[2,2],[3,0]], 1, 'all on border' ],
[ [[[5,5],[6,6]]], 0, 'all outside in arrayref' ],
[ [[1,1],[6,6]], undef, 'inside and outside' ],
[ [[1,0],[1,1]], 1, 'inside and border' ],
],
);
for my $item ( @TESTS ) {
my ($case, $contour, @tests) = @$item;
my $t = Math::Polygon::Tree->new($contour);
for my $test ( @tests ) {
my ($in, $expected, $name) = @$test;
my $got = $t->contains_points($in);
is( $got, $expected, "$case: $name" );
}
}
done_testing();
t/contains_rough.t view on Meta::CPAN
#!/usr/bin/perl
use 5.010;
use strict;
use warnings;
use utf8;
use Test::More;
use Math::Polygon::Tree;
our @TESTS = (
[
box => [[61.3124124,56.7182618],[61.4764193,56.7182618],[61.4764193,56.7834254],[61.3124124,56.7834254]],
[
[[
[61.4257797,56.8012777],
[61.430064,56.793951],
[61.4301352,56.7934636],
t/contains_rough.t view on Meta::CPAN
[ [[[35.2284227,54.7442032],[35.2280966,54.7442021],[35.2280953,54.7443255],[35.2284214,54.7443267]]],
, 1, 'inside' ],
[ [[[35.2209694,54.7197187],[35.2229855,54.7201828],[35.2237598,54.7198791],[35.2216122,54.7190521],[35.2209694,54.7197187]]],
, undef, 'doubt' ],
],
);
for my $item ( @TESTS ) {
my ($case, $contour, @tests) = @$item;
my $t = Math::Polygon::Tree->new($contour, {prepare_rough=>1});
for my $test ( @tests ) {
my ($in, $expected, $name) = @$test;
my $got = $t->contains_polygon_rough(@$in);
is( $got, $expected, "$case: $name" );
}
}
done_testing();
t/polygon_bbox.t view on Meta::CPAN
#!/usr/bin/perl
use 5.010;
use strict;
use warnings;
use utf8;
use Test::More;
use Math::Polygon::Tree qw/ polygon_bbox /;
our @TESTS = (
[ [[0,0]], [0,0,0,0], 'single point' ],
[ [[0,0],[1,1],[2,1],[2,2],[0,0]], [0,0,2,2], 'simple contour' ],
);
for my $test ( @TESTS ) {
my ($in, $expected, $name) = @$test;
my $got = polygon_bbox($in);
t/polygon_centroid.t view on Meta::CPAN
#!/usr/bin/perl
use 5.010;
use strict;
use warnings;
use utf8;
use Test::More;
use Math::Polygon::Tree qw/ polygon_centroid /;
our @TESTS = (
[ [[1,1]], [1,1], 'single point' ],
[ [[0,0],[2,4]], [1,2], 'single segment' ],
[ [[0,0],[3,0],[0,3]], [1,1], 'triangle' ],
[ [[0,0],[4,0],[4,4],[0,4]], [2,2], 'square' ],
[ [[0,0],[3,0],[3,0],[0,3]], [1,1], 'duplicated point' ],
);
( run in 0.994 second using v1.01-cache-2.11-cpan-8780591d54d )