ダグラス-プックのまばらなアルゴリズムはjavascriptを付け加えて実現します.

5669 ワード

sublime-text-3 アルゴリズム javascript

ダグラス・プラク抽出アルゴリズムは、大量の冗長なグラフィカルデータ点を圧縮して必要なデータ点を抽出するために用いられる.このアルゴリズムが希薄化を実現する過程は、まず曲線の先頭点の虚を一直線に接続し、残りの各点からその直線までの距離を求め、その最大値を取った者と所定の臨界値と比較し、臨界値以下の場合は直線の両端間の各点を全部切り捨て、そうでなければこの直線距離の最大点から保留し、元の線を二つの部分に分けます.各部分の線に対して、最後まで抽気プロセスを実施する.抽出結果点数は選択した限界値の増加に伴って減少します.適用する時は精度によってクリッピング臨界値を選択し、最高の効果を得ます.
垂距法とダグラス-プック法の冗長な頂点を削除する効率の比較
ダグラス-プルーク法は、曲線の最初の最後の頂点を線に接続し、残りの各頂点からその直線までの距離を求め、その最大を選択した者は規定の限界差と比較し、もし差を制限するなら、直線の両端の各点を全部削除します.制限差より大きい場合は、この直線距離の最大の頂点から保持し、これを境に曲線を2つの部分に分け、この2つの部分に対して上記の方法を繰り返し使用して、最終的にはさらに圧縮ができなくなるまで(図3参照).
ダグラス2プランク法は、全体的なアルゴリズムであり、一般的に大きな曲げ形態の特徴点を保持することができるという非常に顕著な利点がある.ダグラス・プック法で圧縮された図形を図4に示します.このアルゴリズムは小さい曲げ上の点を正確に削除できるので,線要素の形態的特徴をバルクから効果的に保持できる.ダグラス・プック法はこのような顕著な利点を持っているからこそ、オンライン要素の自動製図において、より広範な応用がなされている.しかし、ダグラス-プック法は垂距離法より複雑で、通常のプログラミングの実現には再帰者を採用する必要があります.
endを転載する
以下はjavascriptバージョンの実現です.




   
   DouglasPeucker




var points = [{
    x: 10,
    y: 10
}, {
    x: 20,
    y: 30
}, {
    x: 30,
    y: 12
}, {
    x: 35,
    y: 5
}, {
    x: 40,
    y: 22
}, {
    x: 50,
    y: 12
}, {
    x: 80,
    y: 40
}];
var Helper = {
    renderPointsTo: function(points, anchor) {
        var d;
        for (var i = 0, p, a = K(anchor); i < points.length; i++) {
            p = points[i];
            if (a) {
                a.appendChild(K('div', {}, {
                    position: 'absolute',
                    left: p.x + 'px',
                    top: p.y + 'px',
                    width: '5px',
                    height: '5px',
                    backgroundColor: 'green',
                    fontSize: '1px'
                }));
            }

        }
    }
};
Helper.renderPointsTo(points, 'processBefore');
var DouglasPeucker = {
    getProcessPoints: function(points, tolerance) {
        /// <summary>       </summary>
        /// <param name="points" type="Array">      </param>
        /// <param name="tolerance" type="Float">     </param>
        /// <returns type="Array" />
        if (!K.isArr(points) || !points.length) { // points         ，         
            return [];
        }
        if (points.length < 3) return points; //  3      ，  1  2        
        var firstPoint = 0,
            lastPoint = points.length - 1; //           
        var pointIndexsToKeep = []; //          
        pointIndexsToKeep.push(firstPoint);
        pointIndexsToKeep.push(lastPoint); //          ，    
        while (points[firstPoint] == points[lastPoint]) { //      ，   ，    
            lastPoint--;
        }
        this.reduce(points, firstPoint, lastPoint, tolerance, pointIndexsToKeep); //  
        var resultPoints = []; //      
        pointIndexsToKeep.sort(function(a, b) { //  ，       
            return a - b;
        });
        for (var i = 0; i < pointIndexsToKeep.length; i++) {
            resultPoints.push(points[pointIndexsToKeep[i]]);
        }
        return resultPoints;
    },
    reduce: function(points, firstPoint, lastPoint, tolerance, pointIndexsToKeep) {
        /// <summary>    </summary>
        /// <param name="points" type="Array">      </param>
        /// <param name="firstPoint" type="Integer">  </param>
        /// <param name="lastPoint" type="Integer">  </param>
        /// <param name="tolerance" type="Float">     </param>
        /// <param name="pointIndexsToKeep" type="Array">        </param>
        var maxDis = 0,
            idxFarthest = 0; //             
        for (var i = firstPoint, dis; i < lastPoint; i++) {
            dis = this.perpendicularDistance(points[firstPoint], points[lastPoint], points[i]); //         
            if (dis > maxDis) { //      
                maxDis = dis;
                idxFarthest = i;
            }
        }
        if (maxDis > tolerance && idxFarthest != 0) { //           
            pointIndexsToKeep.push(idxFarthest);
            this.reduce(points, firstPoint, idxFarthest, tolerance, pointIndexsToKeep);
            this.reduce(points, idxFarthest, lastPoint, tolerance, pointIndexsToKeep);
        }
    },
    perpendicularDistance: function(beginPoint, endPoint, comparePoint) {
        /// <summary>     comparePoint beginPoint endPoint          </summary>
        /// <param name="beginPoint" type="Object">   </param>
        /// <param name="endPoint" type="Object">   </param>
        /// <param name="comparePoint" type="Object">   </param>
        /// <returns type="Float" />
        //Area = |(1/2)(x1y2 + x2y3 + x3y1 - x2y1 - x3y2 - x1y3)|   *Area of triangle
        //Base = v((x1-x2)2+(y1-y2)2)                               *Base of Triangle*
        //Area = .5*Base*H                                          *Solve for height
        //Height = Area/.5/Base
        var area = Math.abs(0.5 * (beginPoint.x * endPoint.y + endPoint.x * comparePoint.y + comparePoint.x * beginPoint.y -
            endPoint.x * beginPoint.y - comparePoint.x * endPoint.y - beginPoint.x * comparePoint.y));
        var bottom = Math.sqrt(Math.pow(beginPoint.x - endPoint.x, 2) + Math.pow(beginPoint.y - endPoint.y, 2));
        var height = area / bottom * 2;
        return height;
    }
};
Helper.renderPointsTo(DouglasPeucker.getProcessPoints(points, 14), 'processAfter');

宣伝の下で私のブロック管理フレームMagix:https://github.com/thx/magix
Magix、starとforkを試してみてください.

WeChat JSSDK invalid signature署名エラーの解決方法