javascript - 使用 RaphaelJS 在任意位置的一组形状周围绘制边框

Question

我正在使用 RaphaelJS 在纸上的随机位置绘制一组形状，使用以下代码：

http://jsbin.com/ixiqiy/2/edit

我现在要做的是找到最外面的一组位置，这样我就可以在整个组周围画一个边框。例如：

任何人都可以帮忙吗？谢谢。

Answer 1

好的，所以使用Jarvis March算法和这个python 实现，我设法将我自己的 JS/RaphaelJS 解决方案放在一起，可以在这里找到：http: //jsbin.com/ixiqiy/12/edit。

以防万一消失，这里是代码：

(function() {

    function cmp(x, y) {  
        if (x > y) {
            return 1;
        } else if (x < y) {
            return -1;
        } else {
            return 0;
        }
    } 
    function turn(p, q, r) {
        return cmp((q[0] - p[0]) * (r[1] - p[1]) - (r[0] - p[0]) * (q[1] - p[1]), 0);
    }
    function dist(p, q) {
        var dx = q[0] - p[0];
        var dy = q[1] - p[1];
        return dx * dx + dy * dy;
    }
    function next_hull_pt(points, p) {
        var q = p,
            r,
            t;
        for (var i = 0; i < points.length; i++) {
            r = points[i];
            t = turn(p, q, r);
            if (t == -1 || t == 0 && dist(p, r) > dist(p, q)) {
                q = r;
            }
        }
        return q;
    }
    function convex_hull(points) {
        var left,
            point;
        for (var i = 0; i < points.length; i++) {
            point = points[i];
            if (!left || point[0] < left[0]) {
                left = point;
            }
        }
        var hull = [left],
            p,
            q;
        for (var i = 0; i < hull.length; i++) {
            p = hull[i];
            q = next_hull_pt(points, p);
            if (q[0] != hull[0][0] || q[1] != hull[0][1]) {
                hull.push(q);
            }
        }
        hull.push(left);
        return hull;
    }

    var paper   = Raphael(0, 0, 800, 800),
        set     = paper.set(),
        points  = [],
        point;

    for (var i = 0; i < 20; i++) {
        points[i] = [
            Math.round(Math.random() * 500) + 100,
            Math.round(Math.random() * 500) + 100
        ];
    }

    for (var i = 0; i < points.length; i++) {
        point = points[i];
        set.push(paper.circle(point[0], point[1], 5));
    }

    set.attr('fill', '#ff0000');
    set.attr('stroke', '#ffffff'); 

    var outline     = convex_hull(points),
        previous    = [0, 0],
        path        = 'M';
    for (var i = 0; i < outline.length; i++) {
        point = outline[i];
        path = path + (i == 0 ? 'M' : 'L') + point[0] + ',' + point[1] + ' ';
    }

    var path = paper.path(path);
    path.attr('stroke', '#0000ff'); 

})();