Douglas-Peucker壓縮算法

Douglas-Peucker算法(道格拉斯-普克算法）是将曲線近似表示為一系列點，并減少點的數量的一種算法。它的優點是具有平移和旋轉不變性，給定曲線與門檻值後，抽樣結果一定。Douglas—Peucker算法通常用于線狀矢量資料壓縮、軌迹資料壓縮等。

算法步驟

連接配接曲線首尾兩點A、B形成一條直線AB；

計算曲線上離該直線段距離最大的點C，計算其與AB的距離d；

比較該距離與預先給定的門檻值threshold的大小，如果小于threshold，則以該直線作為曲線的近似，該段曲線處理完畢。

如果距離大于門檻值，則用點C将曲線分為兩段AC和BC，并分别對兩段曲線進行步驟[1~3]的處理。

當所有曲線都處理完畢後，依次連接配接各個分割點形成折線，作為原曲線的近似。

實作代碼

Java實作代碼如下，代碼引用自JTS庫。

class DouglasPeuckerLineSimplifier {

    private Coordinate[] pts;

    private boolean[] usePt;

    private double distanceTolerance;

    private LineSegment seg = new LineSegment();

    public static Coordinate[] simplify(Coordinate[] pts, double distanceTolerance) {

        DouglasPeuckerLineSimplifier simp = new DouglasPeuckerLineSimplifier(pts);

        simp.setDistanceTolerance(distanceTolerance);

        return simp.simplify();

    }

    public DouglasPeuckerLineSimplifier(Coordinate[] pts) {

        this.pts = pts;

    }

    public void setDistanceTolerance(double distanceTolerance) {

        this.distanceTolerance = distanceTolerance;

    }

    public Coordinate[] simplify() {

        this.usePt = new boolean[this.pts.length];

        for(int i = 0; i < this.pts.length; ++i) {

            this.usePt[i] = true;

        }

        this.simplifySection(0, this.pts.length - 1);

        CoordinateList coordList = new CoordinateList();

        for(int i = 0; i < this.pts.length; ++i) {

            if(this.usePt[i]) {

                coordList.add(new Coordinate(this.pts[i]));

            }

        }

        return coordList.toCoordinateArray();

    }

    private void simplifySection(int i, int j) {

        if(i + 1 != j) {

            this.seg.p0 = this.pts[i];

            this.seg.p1 = this.pts[j];

            double maxDistance = -1.0D;

            int maxIndex = i;

            int k;

            for(k = i + 1; k < j; ++k) {

                double distance = this.seg.distance(this.pts[k]);

                if(distance > maxDistance) {

                    maxDistance = distance;

                    maxIndex = k;

                }

            }

            if(maxDistance <= this.distanceTolerance) {

                for(k = i + 1; k < j; ++k) {

                    this.usePt[k] = false;

                }

            } else {

                this.simplifySection(i, maxIndex);

                this.simplifySection(maxIndex, j);

            }

        }

    }

}