emcconville / point-reduction-algorithms
A collection of algorithms for reducing the number of points in polyline
Installs: 145 461
Dependents: 2
Suggesters: 0
Security: 0
Stars: 59
Watchers: 10
Forks: 8
Open Issues: 0
Requires
- php: >=5.4
Requires (Dev)
- phpunit/phpunit: 4.4.*
- satooshi/php-coveralls: 1.*
- squizlabs/php_codesniffer: 2.1.*
This package is not auto-updated.
Last update: 2024-11-01 22:17:59 UTC
README
#Point Reduction Algorithms
A collection of algorithms for reducing the number of points in polygon / polyline.
Custom shapes, polygon & polyline in web-map applications, can have too many points. Often a shape will be rendered at a distant zoom-level, and wouldn't require such high-resolution. This library's goal is to provided basic methods to simplify & reduce shapes.
Install
With composer.
$ curl -sS https://getcomposer.org/installer | php
$ cat > composer.json <<EOF
{
"require": {
"emcconville/point-reduction-algorithms" : "~1.0"
}
}
EOF
$ php composer.phar install
Algorithms & Usage
Below is an original, uncompressed, polyline with 2151 points, and is delivered as SVG weighing in @ 175K.
All algorithms share a common abstraction, but each class implements a unique reduce method. Most reduction methods require one argument for tolerance / threshold; except, Visvalingam–Whyatt requires the desired final point count, and Opheim requires two independent thresholds.
Example Pseudo code:
use PointReduction\Algorithms\ALGORITHM_NAME; $obj = new ALGORITHM_NAME($myPoints); $myReducedPoints = $obj->reduce($tolerance);
The $myPoints must be an array, or traversable object that supports removing element at index. Each user defined point must implement PointReduction\Common\PointInterface which enforces a getCoordinates method. This common interface allows user objects to have any type of property (ie. x/y, latitude/longitude, left/top).
use PointReduction\Common\PointInterface; class MyPoint implements PointInterface { // ... my stuff here ... public function getCoordinates() { return array($this->myOwnX, $this->myOwnY); } }
Ramer–Douglas–Peucker
use PointReduction\Common\Point, PointReduction\Algorithms\RamerDouglasPeucker; $givenPoints = array( new Point(-84.158640, -39.822480), new Point(-84.159250, -39.820120), // ... and so one ); $epsilon = 0.001 $reducer = new RamerDouglasPeucker($givenPoints); $reducedPoints = $reducer->reduce($epsilon);
The original polygon of 2151 points has been reduced to 343.
Visvalingam–Whyatt
use PointReduction\Common\Point, PointReduction\Algorithms\VisvalingamWhyatt; $givenPoints = array( new Point(-84.158640, -39.822480), new Point(-84.159250, -39.820120), // ... and so one ); $desiredPointCount = 343; $reducer = new VisvalingamWhyatt($givenPoints); $reducedPoints = $reducer->reduce($desiredPointCount);
The original polygon of 2151 points has been reduced to 343.
Reumann–Witkam
use PointReduction\Common\Point, PointReduction\Algorithms\ReumannWitkam; $givenPoints = array( new Point(-84.158640, -39.822480), new Point(-84.159250, -39.820120), // ... and so one ); $threshold = 0.001; $reducer = new ReumannWitkam($givenPoints); $reducedPoints = $reducer->reduce($threshold);
The original polygon of 2151 points has been reduced to 872.
Opheim
use PointReduction\Common\Point, PointReduction\Algorithms\Opheim; $givenPoints = array( new Point(-84.158640, -39.822480), new Point(-84.159250, -39.820120), // ... and so one ); $perpendicularTolerance = 0.005; $radialTolerance = 0.01; $reducer = new Opheim($givenPoints); $reducedPoints = $reducer->reduce($perpendicularTolerance, $radialTolerance);
The original polygon of 2151 points has been reduced to 684.
Lang
use PointReduction\Common\Point, PointReduction\Algorithms\Lang; $givenPoints = array( new Point(-84.158640, -39.822480), new Point(-84.159250, -39.820120), // ... and so one ); $threshold = 0.001; $lookAhead = 7; $reducer = new Lang($givenPoints); $reducedPoints = $reducer->reduce($threshold, $lookAhead);
The original polygon of 2151 points has been reduced to 293.
Zhao-Saalfeld
Added in version 1.2.0
.
use PointReduction\Common\Point, PointReduction\Algorithms\ZhaoSAalfeld; $givenPoints = array( new Point(-84.158640, -39.822480), new Point(-84.159250, -39.820120), // ... and so one ); $degree = 7; $lookAhead = 7; $reducer = new ZhaoSAalfeld($givenPoints); $reducedPoints = $reducer->reduce($degree, $lookAhead);
The original polygon of 2151 points has been reduced to 1493.
Radial Distance
Added in version 1.2.0
.
use PointReduction\Common\Point, PointReduction\Algorithms\RadialDistance; $givenPoints = array( new Point(-84.158640, -39.822480), new Point(-84.159250, -39.820120), // ... and so one ); $tolerance = 0.0025; $reducer = new RadialDistance($givenPoints); $reducedPoints = $reducer->reduce($tolerance);
The original polygon of 2151 points has been reduced to 449.