Web 技术研究所

我一直坚信着,Web 将会成为未来应用程序的主流

简单凸包算法

  所谓凸包算法就是给定任意个点,把它们用某种方式连接起来使得最终得到的多边形的面积最大(推广到三维则是体积最大的多面体)。凸包算法是个很常用也很实用的算法,不仅是绘图,在各个领域都有可能用到。这里使用一个简单的递归思路来实现。
  递归的思维就是把复杂的计算分解成简单的计算。如果给定的点只有三个那就很容易画出面积最大的图形,因为三个点只能固定一个三角形。既然这样,我们就把给定的一堆点逐渐细分成只有三个点的情况,然后在组合回来。为了提高效率,我们应该分出尽量大的三角形。一开始可以找到给定一堆点的两个相差很远的边界点(比如左下和右上两点),连接这两个点(连线称为中线)。就可以把所有的点分成两大份。以上这些就是第一步,它比较特殊,我把它提取到了递归之外处理。
  既然已经有了点集和中线,后面的步骤就不需要第一步那么麻烦的寻找新的边界点了,因为中线的两端就是边界点。现在只要找到离中线最远的点,连接它和中线的两端就能画出可能的最大三角形。这个三角形的其中一边已经是中线了,把剩下两条边视为下一层递归的中线,边外部找到的点作为下一层递归的点集,递归处理。这样最终就能把所有点集都变成单个三角形的情况处理掉。
  计算过程大概是这样
  在这个过程中还有一些可能会纠结的操作,比如计算最远的点、计算三角形边外部的点,这样的小算法。这些都是几何基础,稍微想想就能想出来。我就不逐一介绍了,直接看程序就明白
//功能:获取点集所能构成的最大多边形的顶点数组
//作者:次碳酸钴(admin@web-tinker.com)
//参数:点集(无序顶点数组)
//返回:多边形顶点数组(有序)
function getGreatePolygon(s){
  var L,R,i,j,k,o,A=[],B=[],f=function(s,L,R){
    if(s.length==0)return []; //如果集合为空就不能存在外部节点
    var i,j,k1,k2,o,m=0,H,A=[],B=[],V=[R[0]-L[0],R[1]-L[1]];
    //找出面积最大的三角形 dot(V,vec(L,o))
    for(i=0;o=s[i];i++)
      j=V[0]*(o[1]-L[1])-V[1]*(o[0]-L[0]),j<m&&(m=j,H=o);
    if(!H)return []; //找不到说明无外部节点
    //计算vec(L,H)和vec(H,R)角度
    k1=Math.atan2(H[0]-L[0],H[1]-L[1]);
    k2=Math.atan2(R[0]-H[0],R[1]-H[1]);
    //找出外部顶点
    for(i=0;o=s[i];i++)if(o!=H&&o!=L)
      Math.atan2(o[0]-L[0],o[1]-L[1])>k1&&A.push(o),
      Math.atan2(o[0]-H[0],o[1]-H[1])>k2&&B.push(o);
    return [].concat(f(A,L,H),[H],f(B,H,R));
  };
  //计算(左下)(右上)两个极点
  for(i=1,L=R=s[0];o=s[i];i++)
    (o[0]<L[0]||o[0]==L[0]&&o[1]>L[1])&&(L=o),
    (o[0]>R[0]||o[0]==R[0]&&o[1]<R[1])&&(R=o);
  //计算找出中线左右两边的节点集
  k=Math.atan2(R[0]-L[0],R[1]-L[1])
  for(i=0;o=s[i];i++)if(o!=L)
    j=Math.atan2(o[0]-L[0],o[1]-L[1]),
    j>k&&A.push(o),j<k&&B.push(o);
  //分别处理左右节点并返回数据
  return [].concat([L],f(A,L,R),[R],f(B,R,L));
};
  下面是使用的实例 onload=function(){
  var canvas,g,size=400,move,s=[];
  //创建画布
  canvas=document.createElement("canvas");
  canvas.width=canvas.height=size;
  canvas.style.border="1px solid #CCC";
  document.body.appendChild(canvas);
  g=canvas.getContext("2d");
  g.translate(0.5,0.5);
  //操作接口
  move=function(e){
    //添加节点
    s.push([e.layerX,e.layerY]);
    //计算点集
    s=getGreatePolygon(s);
    //擦除轨迹
    //g.clearRect(0,0,size,size);
    //绘制
    g.beginPath();
    for(var i=0;i<s.length;i++)g.lineTo(s[i][0],s[i][1]);
    g.lineTo(s[0][0],s[0][1]);
    g.stroke();
  };
  canvas.onmousedown=function(e){
    canvas.onmousemove=move,move(e);
  };
  document.onmouseup=function(){
    canvas.onmousemove=null;
  };
};

  演示实例:简单凸包算法
网名:
54.226.58.*
电子邮箱:
仅用于接收通知
提交 悄悄的告诉你,Ctrl+Enter 可以提交哦
神奇海螺
[查看全部主题]
各类Web技术问题讨论区
发起新主题
本模块采用即时聊天邮件通知的模式
让钛合金F5成为历史吧!
次碳酸钴的技术博客,文章原创,转载请保留原文链接 ^_^