开发者社区> 行列> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

道格拉斯-普克 抽稀算法 附javascript实现

简介: 道格拉斯-普克抽稀算法,是用来对大量冗余的图形数据点进行压缩以提取必要的数据点。
+关注继续查看

道格拉斯-普克抽稀算法,是用来对大量冗余的图形数据点进行压缩以提取必要的数据点。该算法实现抽稀的过程是:先将一条曲线首尾点虚连一条直线,求其余各点到该直线的距离,取其最大者与规定的临界值相比较,若小于临界值,则将直线两端间各点全部舍去,否则将离该直线距离最大的点保留,并将原线条分成两部分,对每部分线条再实施该抽稀过程,直到结束。抽稀结果点数随选取限差临界值的增大而减少,应用时应根据精度来选取限差临界值,以获得最好的效果。


以下转载自:垂距法与道格拉斯-普克法删除冗余顶点效率的比较

道格拉斯- 普克法可描述为:将一条曲线首末顶点虚连一条直线 ,求出其余各顶点到该直线的距离 ,选其最大者与规定的限差相比较 ,若小于等于限差 ,则将直线两端间各点全部删去;若大于限差 ,则离该直线距离最大的顶点保留 ,并以此为界 ,把曲线分为两部分 ,对这两部分重复使用上述方法 ,直至最终无法作进一步的压缩为止 (见图 3)。
img

道格拉斯 2 普克法有一个十分突出的优点 ,即它是一个整体算法 ,在一般情况下可保留较大弯曲形态上的特征点。经道格拉斯-普克法压缩后得到的图形如图 4所示。由于该算法可准确删除小弯曲上的定点 ,故能从体上有效地保持线要素的形态特征。正是因为道格拉斯-普克法具有这样突出的优点 ,所以已经在线要素地自动制图中得到了较广泛的应用。但道格拉斯- 普克法较垂距法复杂 ,且通常编程实现时需要采用递归方 ,有一定的难度。
img

转载end

以下是javascript版本的实现

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">

<head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    <title>DouglasPeucker</title>
</head>

<body>
    <div id="processBefore" style="background-color:#ccc;height:100px;position:relative;"></div>
    <div id="processAfter" style="background-color:#ccc;height:100px;margin-top:10px;position:relative;"></div>
</body>
<script type="text/javascript">
    var K = function (a, b, c, d) {
        var a1 = document.getElementById(a);
        if (a1 != null)
            return a1;
        else {
            a = document.createElement(a);
            for (var i in c) {
                a.style[i] = c[i];
            }

            return a;
        }
    };
    K.isArr = function (object) {
        return object && typeof object === 'object' &&
            typeof object.length === 'number' &&
            typeof object.splice === 'function' &&
            //判断length属性是否是可枚举的 对于数组 将得到false
            !(object.propertyIsEnumerable('length'));
    }
    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');
</script>

</html>

宣传下我的区块管理框架Magix:https://github.com/thx/magix

欢迎试用Magix、star与fork

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
+关注
行列
作品Magix 区块管理框架:https://github.com/thx/magix 欢迎试用、star与fork
15
文章
1
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载