注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

qus的博客

 
 
 

日志

 
 

lrj凸包  

2009-08-10 08:41:05|  分类: 资料 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

一下资料来自网上,出处忘记了。原作者想XX我的话就来


void graham_scan(void)
{
    int i;
int temp_top;
if (n <= 1)
{
   top = 0;
   return ;
}
    sort(point, point + n, cmp); // point[0]即为起点.
// 做右链.
top = -1;
stack[++top] = 0; stack[++top] = 1;
for (i = 2; i < n; i++)
{
        while (top >= 1 && dblcmp(cross(point[stack[top - 1]], point[i], point[stack[top]])) >= 0) top--; // 如果不能左转,则退栈. 如果只要求极点,则共线的点也是不要的(即要加等于).
   stack[++top] = i;
}
temp_top = top; // 此时的栈顶元素一定是第n个点.
// 做左链.
stack[++top] = n - 2;
for (i = n - 3; i >= 0; i--)
{
        while (top >= temp_top + 1 && dblcmp(cross(point[stack[top - 1]], point[i], point[stack[top]])) >= 0) top--; // 如果不能左转,则退栈. 如果只要求极点,则共线的点也是不要的(即要加等于).
   stack[++top] = i;
}
// 此时的栈顶元素是第1个点.(如果凸包是一条直线,则左右链倒置相同.)
// 凸包的顶点为point[stack[0]] 到 point[stack[top - 1]].
}

* 按照lrj的黑书来写的.
适用条件:简单多边形(点按顺时针或逆时针给出).
复杂度:O(n).
*/
void Melkman(void)
{
    int i;
    int temp;
 stack[n] = 0;
 // 注意:前三个点不能是共线的.
 for (i = 1; i < n; i++)
 {
    stack[n + 1] = i; // 当三点平行时要的是后一个点.
    if (dblcmp(cross(point[stack[n]], point[stack[n + 1]], point[i + 1]))) break; // 前三个点不共线.
 }
 bot = n, top = n + 1;
 stack[++top] = stack[--bot] = i + 1;
 // 保证开始的三个点成右手系,否则交换stack[n]和stack[n + 1] .
 if (dblcmp(cross(point[stack[n]], point[stack[n + 1]], point[stack[n + 2]])) < 0)
 {
    temp = stack[n]; stack[n] = stack[n + 1]; stack[n + 1] = temp;
 }
 // 维护栈里的点为右手系(即栈中任意连续三点组成的路径是左旋的,或成直线).
 for (i = i + 2; i < n; i++)
 {
    if (dblcmp(cross(point[stack[top - 1]], point[stack[top]], point[i])) > 0 &&
    dblcmp(cross(point[stack[bot]], point[stack[bot + 1]], point[i])) > 0)
  { // 如果该点对于栈顶左旋且对于栈底右旋,则说明该点在凸包内.
   continue;
  }
  while (dblcmp(cross(point[stack[top - 1]], point[stack[top]], point[i])) <= 0) top--;
  stack[++top] = i;
  while (dblcmp(cross(point[stack[bot]], point[stack[bot + 1]], point[i])) <= 0) bot++;
  stack[--bot] = i;
 }
}

  评论这张
 
阅读(65)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017