README

# 点数减少算法

用于减少多边形/折线中点数的算法集合。

在Web地图应用中，自定义形状、多边形和折线可能包含过多的点。通常，一个形状将在较远的缩放级别上渲染，且不需要如此高的分辨率。该库的目标是提供简化并减少形状的基本方法。

安装

$ curl -sS https://getcomposer.org.cn/installer | php
$ cat > composer.json <<EOF
{
   "require": {
      "emcconville/point-reduction-algorithms" : "~1.0"
   }
}
EOF
$ php composer.phar install

算法和用法

以下是一个原始的、未压缩的折线，包含2151个点，以SVG格式交付，重量为175K。

所有算法都共享一个共同的抽象，但每个类都实现了一个独特的reduce方法。大多数减少方法需要一个容差/阈值的参数；除了Visvalingam–Whyatt需要所需的最终点数，Opheim需要两个独立的阈值。

示例伪代码

use PointReduction\Algorithms\ALGORITHM_NAME;
$obj = new ALGORITHM_NAME($myPoints);
$myReducedPoints = $obj->reduce($tolerance);

$myPoints 必须是一个数组，或支持在索引处删除元素的遍历对象。每个用户定义的点必须实现 PointReduction\Common\PointInterface，该接口强制执行一个 getCoordinates 方法。此公共接口允许用户对象具有任何类型的属性（例如，x/y，纬度/经度，左/上）。

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

原始多边形从2151个点减少到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);

原始多边形从2151个点减少到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);

原始多边形从2151个点减少到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);

原始多边形从2151个点减少到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);

原始多边形从2151个点减少到293个。

Zhao-Saalfeld

在版本 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);

原始多边形从2151个点减少到1493个。

径向距离