openlayer的凸包算法实现

最近在要实现一个openlayer的凸多边形，也遇到了不小的坑，就记录一下

1.具体的需求：

　　通过在界面点击，获取点击是的坐标点，来绘制一个凸多边形。

2.思考过程：

　　1）首先，我们得先获取点击事件发生时，触发的点的坐标

map.events.register('click', map, function (e) {

    var pixel = new OpenLayers.Pixel(e.xy.x,e.xy.y);

    var lonlat = map.getLonLatFromPixel(pixel);

    /*  lonlat.transform(new OpenLayers.Projection("EPSG:4326")); //由900913坐标系转为4326 */

    var newPoint = new OpenLayers.Geometry.Point(lonlat.lon,lonlat.lat);

})

　　2）将获得的点做成一个凸多边形（ps:中间遇到点小坑）

　　　　(1)将获得的点坐标设置为map的点对象,点对象一步步转化为一个map的多边形对象

　　　　/**

        * 绘画凸多边形图层

        * @param {Object} pointList

        */

       function drawConvex(pointList){

        var linearRing = new OpenLayers.Geometry.LinearRing(pointList);

        var LinearArr = linearRing.components;

        var polygonFeature = new OpenLayers.Feature.Vector(new OpenLayers.Geometry.Polygon([linearRing]));

         map.addLayer(vectorLayer);

         vectorLayer.addFeatures([polygonFeature]);

       }

　　接下来，重要的来了，如何将获取的无序的坐标集合转化为凸多边形的点呢?(这里也是血泪史的开始)

　　原本的思路：1.首先得到点，前两个点不做判断，

　　·　　　　　　2.将第三个开始的坐标做一个判断，判断是否在凸多边形内

　　　　　　//判断点是否在多边形内

            function PointInPoly(pt, poly) {

                for (var c = false, i = -1, l = poly.length, j = l - 1; ++i < l; j = i)

                    ((poly[i].y <= pt.y && pt.y < poly[j].y) || (poly[j].y <= pt.y && pt.y < poly[i].y))

                    && (pt.x < (poly[j].x - poly[i].x) * (pt.y - poly[i].y) / (poly[j].y - poly[i].y) + poly[i].x)

                    && (c = !c);

                return c;

            }

　　　　　　3将不在凸多边形内的点（也就是新点）与多边形的其他坐标做判断，通过距离排序来找出距离最近的点，然后将新点插入点的数组中，本以为这样就可以得到一个有　　序的点数组，结果代码写出来了，发现这个和预想不一样，未获得预想的效果。具体代码如下，有大牛懂的话可以指点下。

    //确定插入点在多边形的位置

    function idIndex(p, points){

        var arr = [];

        for(var i =0;i<points.length;i++){

            var obj ={"id":"","distance":"","name":""};

            obj.distance = getFlatternDistance(points[i],p);

            obj.id=i;

            obj.name = points[i].id;

            arr.push(obj);

        }

        arr.sort(by("distance"));

        console.log("arr距离:",arr);

        if(arr.length<2)

            return 0;

        return arr[1].id;

    }

    /**

     * by函数接受一个成员名字符串做为参数

     并返回一个可以用来对包含该成员的对象数组进行排序的比较函数

     * @param {Object} name

     */

    function by(name){

        return function(o,p){

            var a, b;

            if(typeof o === "object" && typeof p === "object" && o && p) {

                a= o[name];

                b= p[name];

                if(a === b) {

                    return 0;

                }

                if(typeof a === typeof b) {

                    return a < b ? -1 : 1;

               }

                return typeof a < typeof b ? -1 : 1;

          }else{

            throw("error");

           }

      }

    }

    //俩点之间的距离

    function getFlatternDistance(pointa,pointb){

        var f = getRad((pointa.x + pointb.x)/2);

        var g = getRad((pointa.x - pointb.x)/2);

        var l = getRad((pointa.y - pointb.y)/2);               

        var sg = Math.sin(g);

        var sl = Math.sin(l);

        var sf = Math.sin(f);            

        var s,c,w,r,d,h1,h2;

        var a = EARTH_RADIUS;

        var fl = 1/298.257;

        sg = sg*sg;

        sl = sl*sl;

        sf = sf*sf;

        s = sg*(1-sl) + (1-sf)*sl;

        c = (1-sg)*(1-sl) + sf*sl;

        w = Math.atan(Math.sqrt(s/c));

        r = Math.sqrt(s*c)/w;

        d = 2*w*a;

        h1 = (3*r -1)/2/c;

        h2 = (3*r +1)/2/s;

        return d*(1 + fl*(h1*sf*(1-sg) - h2*(1-sf)*sg));

    }

    var EARTH_RADIUS = 6378137.0;    //单位M

    var PI = Math.PI;

    function getRad(d){

         return d*PI/180.0;

    }

　　最后，是实现凸包算法的代码（下面的代码是git上找到的，可以实现给一个无序数组，将其中的点排序，过滤生成一个凸多边形，可以省略掉我上面判断点是否在多边形内）

　　　　 function convexHull(points) {

            points.sort(function (a, b) {

                return a.x != b.x ? a.x - b.x : a.y - b.y;

            });

            var n = points.length;

            var hull = [];

            for (var i = 0; i < 2 * n; i++) {

                var j = i < n ? i : 2 * n - 1 - i;

                while (hull.length >= 2 && removeMiddle(hull[hull.length - 2], hull[hull.length - 1], points[j]))

                    hull.pop();

                hull.push(points[j]);

            }

            hull.pop();

            return hull;

        }

        function removeMiddle(a, b, c) {

            var cross = (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x);

            var dot = (a.x - b.x) * (c.x - b.x) + (a.y - b.y) * (c.y - b.y);

            return cross < 0 || cross == 0 && dot <= 0;

        }

最后，出一张效果图

巴特西

openlayer的凸包算法实现

1.具体的需求：

2.思考过程：

最新文章

热门文章