| 1 | package Polygon::Simplify; | ||||||||||||||||||||||||||||
| 2 | |||||||||||||||||||||||||||||
| 3 | 2 | ▶ | use 5.006; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 4 | 2 | ▶ | use strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 5 | 2 | ▶ | use warnings; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 6 | |||||||||||||||||||||||||||||
| 7 | 2 | ▶ | use Math::BigFloat ':constant'; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 8 | |||||||||||||||||||||||||||||
| 9 | =head1 NAME | ||||||||||||||||||||||||||||
| 10 | |||||||||||||||||||||||||||||
| 11 | Polygon::Simplify | ||||||||||||||||||||||||||||
| 12 | |||||||||||||||||||||||||||||
| 13 | =head1 VERSION | ||||||||||||||||||||||||||||
| 14 | |||||||||||||||||||||||||||||
| 15 | Version 0.01 | ||||||||||||||||||||||||||||
| 16 | |||||||||||||||||||||||||||||
| 17 | =cut | ||||||||||||||||||||||||||||
| 18 | |||||||||||||||||||||||||||||
| 19 | 2 | our $VERSION = '0.01'; | |||||||||||||||||||||||||||
| 20 | |||||||||||||||||||||||||||||
| 21 | =head1 SYNOPSIS | ||||||||||||||||||||||||||||
| 22 | |||||||||||||||||||||||||||||
| 23 | WARNING =>>>>>> EXPERIMENTAL RELEASE <<<<<<<= | ||||||||||||||||||||||||||||
| 24 | |||||||||||||||||||||||||||||
| 25 | use Poygon::Simplify; | ||||||||||||||||||||||||||||
| 26 | |||||||||||||||||||||||||||||
| 27 | # Raw points requiring simplification | ||||||||||||||||||||||||||||
| 28 | my $points = [ | ||||||||||||||||||||||||||||
| 29 | { | ||||||||||||||||||||||||||||
| 30 | x => 12.1, y => 3.41 | ||||||||||||||||||||||||||||
| 31 | }, | ||||||||||||||||||||||||||||
| 32 | ... | ||||||||||||||||||||||||||||
| 33 | ]; | ||||||||||||||||||||||||||||
| 34 | |||||||||||||||||||||||||||||
| 35 | # POINT MUST BE AN Array of x and y points and not lat lng | ||||||||||||||||||||||||||||
| 36 | |||||||||||||||||||||||||||||
| 37 | my $cleaned_points = Polygon::Simplify::simplify($points); | ||||||||||||||||||||||||||||
| 38 | |||||||||||||||||||||||||||||
| 39 | # $cleaned_points is an array of hash refs | ||||||||||||||||||||||||||||
| 40 | |||||||||||||||||||||||||||||
| 41 | =head1 DESCRIPTION | ||||||||||||||||||||||||||||
| 42 | |||||||||||||||||||||||||||||
| 43 | perl port of simplify.js | ||||||||||||||||||||||||||||
| 44 | |||||||||||||||||||||||||||||
| 45 | =head2 getSqDist(\%p1, \%p2) | ||||||||||||||||||||||||||||
| 46 | |||||||||||||||||||||||||||||
| 47 | square distance between 2 points | ||||||||||||||||||||||||||||
| 48 | |||||||||||||||||||||||||||||
| 49 | =cut | ||||||||||||||||||||||||||||
| 50 | |||||||||||||||||||||||||||||
| 51 | 99 | ▶ | sub getSqDist { | ||||||||||||||||||||||||||
|
Subroutine
getSqDist: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 52 | 99 | my ($p1, $p2) = @_; | |||||||||||||||||||||||||||
| 53 | |||||||||||||||||||||||||||||
| 54 | 99 | my $dx = $p1->{x} - $p2->{x}; | |||||||||||||||||||||||||||
| 55 | 99 | my $dy = $p1->{y} - $p2->{y}; | |||||||||||||||||||||||||||
| 56 | |||||||||||||||||||||||||||||
| 57 | 99 | return ($dx * $dx) + ($dy * $dy); | |||||||||||||||||||||||||||
| 58 | } | ||||||||||||||||||||||||||||
| 59 | |||||||||||||||||||||||||||||
| 60 | =head2 getSqSegDist(\%p \%p1, \%p2) | ||||||||||||||||||||||||||||
| 61 | |||||||||||||||||||||||||||||
| 62 | square distance from a point to a segment | ||||||||||||||||||||||||||||
| 63 | |||||||||||||||||||||||||||||
| 64 | =cut | ||||||||||||||||||||||||||||
| 65 | 202 | ▶ | sub getSqSegDist { | ||||||||||||||||||||||||||
|
Subroutine
getSqSegDist: called CC=5 SCAR=16.6
Pod
documented
| |||||||||||||||||||||||||||||
| 66 | 202 | my ($p, $p1, $p2) = @_; | |||||||||||||||||||||||||||
| 67 | |||||||||||||||||||||||||||||
| 68 | 202 | my $x = $p1->{x}; | |||||||||||||||||||||||||||
| 69 | 202 | my $y = $p1->{y}; | |||||||||||||||||||||||||||
| 70 | 202 | my $dx = $p2->{x} - $x; | |||||||||||||||||||||||||||
| 71 | 202 | my $dy = $p2->{y} - $y; | |||||||||||||||||||||||||||
| 72 | |||||||||||||||||||||||||||||
| 73 | 202 | ▶ | if($dx != 0 || $dy != 0 ) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
$dx != bless( {"_e" => bless( [0], 'Math::BigInt::Calc' ),"_es" => "+","_m" => bless( [0], 'Math::BigInt::Calc' ),"sign" => "+"}, 'Math::BigFloat' ) or $dy != bless( {"_e" => bless( [0], 'Math::BigInt::Calc' ),"_es" => "+","_m" => bless( [0], 'Math::BigInt::Calc' ),"sign" => "+"}, 'Math::BigFloat' )
MC/DC0%0/2
$dx != bless( {"_e" => bless( [0], 'Math::BigInt::Calc' ),"_es" => "+","_m" => bless( [0], 'Math::BigInt::Calc' ),"sign" => "+"}, 'Math::BigFloat' ) or $dy != bless( {"_e" => bless( [0], 'Math::BigInt::Calc' ),"_es" => "+","_m" => bless( [0], 'Math::BigInt::Calc' ),"sign" => "+"}, 'Math::BigFloat' )
$dx != bless( {"_e" => bless( [0], 'Math::BigInt::Calc' ),"_es" => "+","_m" => bless( [0], 'Math::BigInt::Calc' ),"sign" => "+"}, 'Math::BigFloat' )
$dy != bless( {"_e" => bless( [0], 'Math::BigInt::Calc' ),"_es" => "+","_m" => bless( [0], 'Math::BigInt::Calc' ),"sign" => "+"}, 'Math::BigFloat' )
Truth table33%1/3
A or B
A= $dx != bless( {"_e" => bless( [0], 'Math::BigInt::Calc' ),"_es" => "+","_m" => bless( [0], 'Math::BigInt::Calc' ),"sign" => "+"}, 'Math::BigFloat' )B= $dy != bless( {"_e" => bless( [0], 'Math::BigInt::Calc' ),"_es" => "+","_m" => bless( [0], 'Math::BigInt::Calc' ),"sign" => "+"}, 'Math::BigFloat' )
| |||||||||||||||||||||||||||||
| 74 | |||||||||||||||||||||||||||||
| 75 | 202 | my $first_block = Math::BigFloat->new($p->{x} - $x); | |||||||||||||||||||||||||||
| 76 | 202 | my $second_block = Math::BigFloat->new($p->{y} - $y); | |||||||||||||||||||||||||||
| 77 | |||||||||||||||||||||||||||||
| 78 | 202 | my $first_multiply = $first_block->bmul($dx); | |||||||||||||||||||||||||||
| 79 | 202 | my $second_multiply = $second_block->bmul($dy); | |||||||||||||||||||||||||||
| 80 | |||||||||||||||||||||||||||||
| 81 | 202 | my $top = $first_multiply->badd($second_multiply); | |||||||||||||||||||||||||||
| 82 | 202 | my $dx_square = Math::BigFloat->new($dx)->bmul($dx); | |||||||||||||||||||||||||||
| 83 | 202 | my $dy_square = Math::BigFloat->new($dy)->bmul($dy); | |||||||||||||||||||||||||||
| 84 | 202 | my $bottom = $dx_square->badd($dy_square); | |||||||||||||||||||||||||||
| 85 | # my $t = (($p->{x} - $x) * $dx + ($p->{y} - $y) * $dy) / ($dx * $dx + $dy * $dy); | ||||||||||||||||||||||||||||
| 86 | |||||||||||||||||||||||||||||
| 87 | 202 | my $t = $top->bdiv($bottom)->bstr(); | |||||||||||||||||||||||||||
| 88 | |||||||||||||||||||||||||||||
| 89 | 202 | ▶ | if($t > 1) { | ||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||
| 90 | 0 | $x = $p2->{x}; | |||||||||||||||||||||||||||
| 91 | 0 | $y = $p2->{y}; | |||||||||||||||||||||||||||
| 92 | } elsif( $t > 0) { | ||||||||||||||||||||||||||||
| 93 | 202 | $x += $dx * $t; | |||||||||||||||||||||||||||
| 94 | 202 | $y += $dy * $t; | |||||||||||||||||||||||||||
| 95 | } | ||||||||||||||||||||||||||||
| 96 | } | ||||||||||||||||||||||||||||
| 97 | |||||||||||||||||||||||||||||
| 98 | 202 | $dx = $p->{x} - $x; | |||||||||||||||||||||||||||
| 99 | 202 | $dy = $p->{y} - $y; | |||||||||||||||||||||||||||
| 100 | |||||||||||||||||||||||||||||
| 101 | 202 | return ($dx * $dx) + ($dy * $dy); | |||||||||||||||||||||||||||
| 102 | } | ||||||||||||||||||||||||||||
| 103 | |||||||||||||||||||||||||||||
| 104 | =head2 simplifyRadialDist($\@points, $sqTolerance) | ||||||||||||||||||||||||||||
| 105 | |||||||||||||||||||||||||||||
| 106 | Basic distanec-based simplifaction | ||||||||||||||||||||||||||||
| 107 | |||||||||||||||||||||||||||||
| 108 | =cut | ||||||||||||||||||||||||||||
| 109 | |||||||||||||||||||||||||||||
| 110 | 1 | ▶ | sub simplifyRadialDist { | ||||||||||||||||||||||||||
|
Subroutine
simplifyRadialDist: called CC=4 SCAR=14.0
Pod
documented
| |||||||||||||||||||||||||||||
| 111 | 1 | my ( $points, $sqTolerance) = @_; | |||||||||||||||||||||||||||
| 112 | |||||||||||||||||||||||||||||
| 113 | 1 | my $prev_point = $points->[0]; | |||||||||||||||||||||||||||
| 114 | 1 | my $new_points = [$prev_point]; | |||||||||||||||||||||||||||
| 115 | 1 | my $point; | |||||||||||||||||||||||||||
| 116 | |||||||||||||||||||||||||||||
| 117 | 1 | my $len = @{$points}; | |||||||||||||||||||||||||||
| 118 | 1 | ▶ | for (my $i = 1; $i < $len; $i++) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 119 | 99 | $point = $points->[$i]; | |||||||||||||||||||||||||||
| 120 | |||||||||||||||||||||||||||||
| 121 | 99 | ▶ | if (getSqDist($point, $prev_point) > $sqTolerance) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 122 | 99 | push( @{$new_points}, $point); | |||||||||||||||||||||||||||
| 123 | 99 | $prev_point = $point; | |||||||||||||||||||||||||||
| 124 | } | ||||||||||||||||||||||||||||
| 125 | |||||||||||||||||||||||||||||
| 126 | } | ||||||||||||||||||||||||||||
| 127 | |||||||||||||||||||||||||||||
| 128 | # If the polygon is not complete then complete it | ||||||||||||||||||||||||||||
| 129 | 0 | ▶ | push (@{$new_points}, $point) if ($prev_point != $point); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 130 | |||||||||||||||||||||||||||||
| 131 | 1 | return $new_points; | |||||||||||||||||||||||||||
| 132 | } | ||||||||||||||||||||||||||||
| 133 | |||||||||||||||||||||||||||||
| 134 | 14 | ▶ | sub simplifyDPStep { | ||||||||||||||||||||||||||
|
Subroutine
simplifyDPStep: called CC=5 SCAR=16.1
Pod
undocumented
| |||||||||||||||||||||||||||||
| 135 | 14 | my ($points, $first, $last, $sqTolerance, $simplified) = @_; | |||||||||||||||||||||||||||
| 136 | |||||||||||||||||||||||||||||
| 137 | 14 | my $maxSqDist = $sqTolerance; | |||||||||||||||||||||||||||
| 138 | 14 | my $index; | |||||||||||||||||||||||||||
| 139 | |||||||||||||||||||||||||||||
| 140 | 14 | ▶ | for(my $i = $first + 1; $i < $last; $i++) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 141 | 202 | my $sqDist = getSqSegDist($points->[$i], $points->[$first], $points->[$last]); | |||||||||||||||||||||||||||
| 142 | |||||||||||||||||||||||||||||
| 143 | 202 | ▶ | if ($sqDist > $maxSqDist) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 144 | 67 | $index = $i; | |||||||||||||||||||||||||||
| 145 | 67 | $maxSqDist = $sqDist; | |||||||||||||||||||||||||||
| 146 | } | ||||||||||||||||||||||||||||
| 147 | |||||||||||||||||||||||||||||
| 148 | } | ||||||||||||||||||||||||||||
| 149 | |||||||||||||||||||||||||||||
| 150 | 14 | ▶ | if ($maxSqDist > $sqTolerance) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 151 | 7 | simplifyDPStep($points, $first, $index, $sqTolerance, $simplified); | |||||||||||||||||||||||||||
| 152 | 7 | push @{$simplified}, $points->[$index]; | |||||||||||||||||||||||||||
| 153 | 7 | ▶ | simplifyDPStep($points, $index, $sqTolerance, $simplified) | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 154 | if($index - $first > 1); | ||||||||||||||||||||||||||||
| 155 | } | ||||||||||||||||||||||||||||
| 156 | } | ||||||||||||||||||||||||||||
| 157 | |||||||||||||||||||||||||||||
| 158 | =head2 simplifyDouglasPeucker(\@points, $sqTolerance) | ||||||||||||||||||||||||||||
| 159 | |||||||||||||||||||||||||||||
| 160 | Simplification using Ramer-Douglas-Peucker algorithm | ||||||||||||||||||||||||||||
| 161 | |||||||||||||||||||||||||||||
| 162 | =cut | ||||||||||||||||||||||||||||
| 163 | 1 | ▶ | sub simplifyDouglasPeucker { | ||||||||||||||||||||||||||
|
Subroutine
simplifyDouglasPeucker: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 164 | 1 | my ($points, $sqTolerance) = @_; | |||||||||||||||||||||||||||
| 165 | |||||||||||||||||||||||||||||
| 166 | 1 | my $last = @{$points} - 1; | |||||||||||||||||||||||||||
| 167 | |||||||||||||||||||||||||||||
| 168 | 1 | my $simplified = [$points->[0]]; | |||||||||||||||||||||||||||
| 169 | 1 | simplifyDPStep($points, 0, $last, $sqTolerance, $simplified); | |||||||||||||||||||||||||||
| 170 | 1 | push @{$simplified}, $points->[$last]; | |||||||||||||||||||||||||||
| 171 | |||||||||||||||||||||||||||||
| 172 | 1 | return $simplified; | |||||||||||||||||||||||||||
| 173 | |||||||||||||||||||||||||||||
| 174 | } | ||||||||||||||||||||||||||||
| 175 | |||||||||||||||||||||||||||||
| 176 | =head2 simplify(\@points, $tolerance, $highest_quality) | ||||||||||||||||||||||||||||
| 177 | |||||||||||||||||||||||||||||
| 178 | both algorithms combined for awsome performance | ||||||||||||||||||||||||||||
| 179 | |||||||||||||||||||||||||||||
| 180 | my $points = [ | ||||||||||||||||||||||||||||
| 181 | { | ||||||||||||||||||||||||||||
| 182 | x => 51.34, | ||||||||||||||||||||||||||||
| 183 | y => 1.34, | ||||||||||||||||||||||||||||
| 184 | }, | ||||||||||||||||||||||||||||
| 185 | ... | ||||||||||||||||||||||||||||
| 186 | ]; | ||||||||||||||||||||||||||||
| 187 | |||||||||||||||||||||||||||||
| 188 | simplify($points, $tolerance, $highest_quality); | ||||||||||||||||||||||||||||
| 189 | |||||||||||||||||||||||||||||
| 190 | =cut | ||||||||||||||||||||||||||||
| 191 | |||||||||||||||||||||||||||||
| 192 | 1 | ▶ | sub simplify { | ||||||||||||||||||||||||||
|
Subroutine
simplify: called CC=4 SCAR=14.6
Pod
documented
| |||||||||||||||||||||||||||||
| 193 | 1 | my ($points, $tolerance, $highestQuality) = @_; | |||||||||||||||||||||||||||
| 194 | |||||||||||||||||||||||||||||
| 195 | 1 | ▶ | return $points if (@{$points} <= 2); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 196 | |||||||||||||||||||||||||||||
| 197 | 1 | my $sqTolerance = 1; | |||||||||||||||||||||||||||
| 198 | |||||||||||||||||||||||||||||
| 199 | 1 | ▶ | if ( $tolerance ) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 200 | 0 | $sqTolerance = $tolerance * $tolerance; | |||||||||||||||||||||||||||
| 201 | } | ||||||||||||||||||||||||||||
| 202 | |||||||||||||||||||||||||||||
| 203 | 1 | ▶ | $points = $highestQuality ? $points : simplifyRadialDist($points, $sqTolerance); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 204 | 1 | $points = simplifyDouglasPeucker($points, $sqTolerance); | |||||||||||||||||||||||||||
| 205 | |||||||||||||||||||||||||||||
| 206 | 1 | return $points; | |||||||||||||||||||||||||||
| 207 | |||||||||||||||||||||||||||||
| 208 | |||||||||||||||||||||||||||||
| 209 | } | ||||||||||||||||||||||||||||
| 210 | |||||||||||||||||||||||||||||
| 211 | =head1 AUTHOR | ||||||||||||||||||||||||||||
| 212 | |||||||||||||||||||||||||||||
| 213 | Sunny Patel C<< <sunnypatel4141@gmail.com> >> | ||||||||||||||||||||||||||||
| 214 | |||||||||||||||||||||||||||||
| 215 | =head1 BUGS | ||||||||||||||||||||||||||||
| 216 | |||||||||||||||||||||||||||||
| 217 | please report any bugs or feature requests to C<bug-polygon-simpligy at rt.cpan.org>, or through | ||||||||||||||||||||||||||||
| 218 | the we interace at L<http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Polygon-Simplify>. I will be notified, and then you'll | ||||||||||||||||||||||||||||
| 219 | automatically be notified of progress on your bug as I make changes.o | ||||||||||||||||||||||||||||
| 220 | |||||||||||||||||||||||||||||
| 221 | =cut | ||||||||||||||||||||||||||||
| 222 | |||||||||||||||||||||||||||||
| 223 | 2 | 1; | |||||||||||||||||||||||||||