原创

凸包算法的实现与应用

温馨提示:
本文最后更新于 2021年12月07日,已超过 164 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

凸包算法的应用

凸包算法在网络分组区域的可视化绘制,节点扩展后的区域选择等实际场景中有着广泛的应用。
(其实我还想到了包围圈的概念,在军事推演过程中,是否也可以应用凸包算法,选择合理的据点,形成点面区域包围圈,围点打援....)

什么是凸包?

在二维欧几里得空间中,凸包可想象为一条刚好包着所有点的橡皮圈。
用不严谨的话来讲,给定二维平面上的点集,凸包就是将最外层的点连接起来构成的凸多边型,它能包含点集中所有的点。
凸包的效果如下图所示:

Graham's Scan法求凸包

这个算法是由数学大师葛立恒(Graham)发明的,算法思路如下:

  1. 找出所有点中y坐标最小的点,若y坐标最小的点有两个以上,则选择其中x坐标最小的点,将此点记为H;
  2. 设除H之外所有点的坐标集合为N{p1,p2,p3,p4,p5,p6,…},分别计算向量< H,p1>,< H,p2>,< H,p3>极坐标的角度,对集合N按极坐标角度的大小排序,即以H为圆心,顺时针扫描各点,将扫描到的点依次加入集合中;如下图,排好序的坐标集合为N{a1,a2,a3,a4,a5,a6},其中θ为向量< H,a1>极坐标的角度。
  3. 线段< H,a1>一定在凸包上,现在加入a2,假设a2也在凸包上,接下来加入a3,如果a3在向量的左侧则判断a2不在凸包上,需将a2从凸包中移除,在此例中a3在向量的右侧;然后加入a4,如果a4在向量的左侧则判断a3不在凸包上,此例中a4在向量的左侧,所以需将a3从凸包中移除,接下来需回溯判断a4在向量的左侧还是右侧,决定是否要将a2移除…,即每加入一点时,必须考虑到前面的线段是否在凸包上。从基点开始,凸包上每条相临的线段的旋转方向应该一致,并与扫描方向相同。如果发现新加的点使得新线段与上线段的旋转方向发生变化,则可判定上一点必然不在凸包上。

复杂度

这个算法可以直接在原数据上进行运算,因此空间复杂度为O⑴。但如果将凸包的结果存储到另一数组中,则可能在代码级别进行优化。由于在扫描凸包前要进行排序,因此时间复杂度至少为快速排序的O(nlgn)。后面的扫描过程复杂度为O(n),因此整个算法的复杂度为O(nlgn)。

求解凸包的javascript代码

设数组points是存储所选图形的所有顶点的集合

<!--
主要是利用叉积判断方向来决定点是否可选
注意实现的时候去掉了在同一条直线上的点

基本代码借鉴
http://blog.csdn.net/miscclp/article/details/41169837
http://blog.csdn.net/enjoying_science/article/details/47760677
-->
<html>
<head>
 <meta charset = "utf-8" / > 
<title>TSP_demo</title>
</head>
<body>
<div id="outText">
</div>
<canvas id="canvas" height="550px" width="1024px">
</canvas>
<script type="text/javascript">

var canvas = document.getElementById("canvas");
var canvasWidth = canvas.width;
var canvasHeight = canvas.height;
var context = canvas.getContext("2d");
// 未使用
function initMat(M, N, val) {
  var x = new Array();
  for(var i = 0; i < M; i++) {
    x[i] = new Array();
    for(var j = 0; j < N; j++)
        x[i].push(val);
  }
  return x;
}

function drawPath(x1, y1, x2, y2, color, width) {
    context.beginPath();
    context.fillStyle = color;
    context.strokeStyle = color;
    context.lineWidth = width;
    context.moveTo(x1, y1);
    context.lineTo(x2, y2);
    context.stroke();
}
function drawCities(p) {
    for(var i = 0; i < p.length ; i++) {
        context.beginPath();

        context.fillStyle = "blue";
        context.strokeStyle = "blue";
        context.lineWidth = 1;
        context.font = "normal 16px Arial";

        context.arc(p[i].x, p[i].y, 3, (Math.PI / 180) * 0, (Math.PI / 180) * 360, false);
        context.fill();
        context.stroke();
        context.closePath();
        if(p[i].tj==true){
            context.fillStyle = "red";
            context.textAlign = "center";
            context.textBaseline = "middle";
            context.fillText(String(i), p[i].x, p[i].y-8);
        }
    }
}

function output(string){
    var out = document.getElementById("outText");
    out.innerHTML+=string
}
// 可以借助cos a 在0-180之间,单调递减!!!
// 这里用的是叉积,正弦的判断
function multiply(p0,p1,p2){
    return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y)); 
}
function distance_no_sqrt(p1,p2)
{
    //return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y))); 
    return((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); 
}
function Graham_scan(pointSet,ch,n){
// 这里会修改pointSet
    var i,j,k=0,top=2;
    var tmp=new Object();
    // 找到一个基点,基本就是保证最下面最左面的点
    for(i=1;i<n;i++){
        if( (pointSet[i].y<pointSet[k].y) || 
            ( (pointSet[i].y==pointSet[k].y) && (pointSet[i].x<pointSet[k].x) ) 
          ){
            k=i;
        }
    }

    tmp=pointSet[0];
    pointSet[0]=pointSet[k];
    pointSet[k]=tmp; 

    use=n;
    for (i=1;i<use-1;i++){
        k=i;
        for (j=i+1;j<use;j++){
            var direct=multiply(pointSet[0],pointSet[k],pointSet[j]);
            if(direct>0){
                k=j;
            }else if(direct==0){
                // k j 同方向
                var dis=distance_no_sqrt(pointSet[0],pointSet[j])-distance_no_sqrt(pointSet[0],pointSet[k]);
                use--; // 也就是不要了
                if(dis>0){
                    // 保留j
                    // 把 k 就不要了
                    pointSet[k]=pointSet[j];
                    pointSet[j]=pointSet[use];
                    j--;
                }else{
                    tmp=pointSet[use];
                    pointSet[use]=pointSet[j];
                    pointSet[j]=tmp;
                }
            }
        }
        tmp=pointSet[i];
        pointSet[i]=pointSet[k];
        pointSet[k]=tmp;
    }

    ch.push(pointSet[0]);
    ch.push(pointSet[1]);
    ch.push(pointSet[2]);
    for (i=3;i<use;i++){
        while ( !(multiply(pointSet[i],ch[top-1],ch[top]) < 0 ) ){
            top--;
            ch.pop();
        }
        top++;
        ch.push(pointSet[i]);
    }
}
// 求凸集的方法
function Graham_example(){
    var n=100; // 用100个例子
    var p=new Array(n);
    //var res=new Array(n);
    var res=new Array();
    // 随机初始化定点
    for(var i = 0; i < n; i++) {
        p[i]=new Object();
        p[i].x = (Math.random() * 32767) % 680 + 20;
        p[i].y = (Math.random() * 32767) % 320 + 20;
        p[i].tj=false

    }
    drawCities(p)
    var t1 = new Date()
    t1.setTime(t1.getTime());
    Graham_scan(p,res,n)
    t2 = new Date();
    var ms = t2.getTime() - t1.getTime();
    output("<br/>用时(毫秒):<br/>" + ms)

    var m=res.length;
    res[0].tj=true;
    for(var i=1;i<m;i++){
        res[i].tj=true;
        drawPath(res[i-1].x, res[i-1].y, res[i].x, res[i].y, "black", 1);
    }
    drawPath(res[0].x, res[0].y, res[m-1].x, res[m-1].y, "black", 1);
    // canvas 的坐标和我们的不一样
    drawCities(res)
}

Graham_example();

</script>
</body>
</html>

效果图

在线凸包计算可视化示例

Canvas使用实时凸包算法实现可视化效果

凸包算法库推荐

Hull.js 凸包算法库

正文到此结束
该篇文章的评论功能已被站长关闭