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

银河里的星星

落在人间

 
 
 

日志

 
 

计算几何:凸包模板  

2008-11-11 22:46:28|  分类: 算法与acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
写了老长时间,主要是中间犯了很多小错,写的时候不够严谨啊。。。
写凸包算法时犯的一些错误
1.while(!is_left_turn(convex_next_top,convex_top,res_filter[i])){//attention ! ...
当时忘了加这个!。。。
2.去除同线的点的时候,出错,光记得排除那些共线的点,反而忘了添加其他的不共线的普通点             
3.排序时候,交换写错,下面的end应该是swap(points_set[j],points_set[i++]);
                if(cmp(&points_set[j],&points_set[end]) < 0){
                      swap(points_set[end],points_set[i++]);         
                }                                                    
4.去除同线的点的时候,计算两点距离出错,两点间的距离公式竟然忘了求平方。。。
直接:(x1-x2)+(y1-y2)                                    
5.忘了在while循环中,更新convex_next_top,convex_top
            while(!is_left_turn(convex_next_top,convex_top,res_filter[i])){//attention !
               convex.pop_back();     
            } 
6.提交的时候忘了把#undef DEBUG加上

革命尚未成功啊。
               
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
#define MAX_PNUM 1000
#define DEBUG 1
#undef DEBUG
namespace convex_hull{
    using std::vector;
    struct point{
        int x;
        int y;
    }root;
    //point points_list[MAX_PNUM];
    int get_leftmost(point points_set[],int n){
        int index = 0;
        for(int j = 0; j < n ; j++){
                if(points_set[j].x < points_set[index].x){
                     index = j;          
                }
                else if(points_set[j].x == points_set[index].x){
                     if(points_set[j].y < points_set[index].y)
                          index = j;
                }
        }
        return index;
    }
    void swap(point & a,point & b){
        point c = a;
        a = b;
        b = c;
    }
    int distance_square(point a,point b){
        return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);

    }
    void sort_by_angle(point points_set[],int begin,int end,int(*cmp)(void *,void *)){
        if(begin >= end) return;
        int i = begin;
        for(int j = begin ; j < end ; j++){
                if(cmp(&points_set[j],&points_set[end]) < 0){
                      swap(points_set[j],points_set[i++]);         
                }                               
        }
        swap(points_set[i],points_set[end]);
        sort_by_angle(points_set,begin,i-1,cmp);
        sort_by_angle(points_set,i+1,end,cmp);       
    }
    int cmp(void * a,void * b){
        point p1 = *(point *)a;
        point p2 = *(point *)b;
        return (p2.x-root.x)*(p1.y-root.y)-(p1.x-root.x)*(p2.y-root.y);
    }
    bool is_left_turn(point a,point b,point c){
        return (c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y) < 0;
    }
    vector <point> graham_scan(point points_set[],int n){
        vector <point> res_filter;       
        vector <point> convex;
        int root_index = get_leftmost(points_set,n);
        //delete the root from the set.n is the num of points
        #ifdef DEBUG
        printf("root-index:%d\n",root_index);
        #endif
        root = points_set[root_index];
        points_set[root_index] = points_set[n-1];
        n--;
        //sort
        sort_by_angle(points_set,0,n-1,cmp);
        #ifdef DEBUG
        printf("after sort:\n");
        for(int i = 0 ; i < n ; i++)               
                printf("%d %d\n",points_set[i].x,points_set[i].y);
        #endif
        //delete the point with the same angle.
        res_filter.push_back(points_set[0]);
        for(int index = 1 ; index < n ; index++){
            point temp = res_filter.back();
            if(cmp(&points_set[index],&temp) == 0)
            {
                 if(distance_square(points_set[index],root) > distance_square(temp,root)){      
                    res_filter.pop_back();
                    res_filter.push_back(points_set[index]);  
                 }                      
            }
            else
                 res_filter.push_back(points_set[index]);  
                                      
        }
        #ifdef DEBUG
        printf("after filter:\n");
        for(int i = 0 ; i < res_filter.size() ; i++)               
                printf("%d %d\n",res_filter[i].x,res_filter[i].y);
        #endif
        //if all point is in one straight line,return null convex.
        if(res_filter.size() <= 1) return convex;
        //find convex hull
        convex.push_back(root);
        convex.push_back(res_filter[0]);
        convex.push_back(res_filter[1]);
        for(int i = 2 ; i < res_filter.size() ; i++){
            point convex_top =  convex.back(); 
            point convex_next_top = convex[convex.size()-2];
            while(!is_left_turn(convex_next_top,convex_top,res_filter[i])){//attention !
               convex.pop_back();  
               convex_top =  convex.back();  
               convex_next_top = convex[convex.size()-2];
            }
            convex.push_back(res_filter[i]);
        }
        #ifdef DEBUG
        printf("convex:\n");
        for(int i = 0 ; i < convex.size() ; i++)               
                printf("%d %d\n",convex[i].x,convex[i].y);
        #endif
        return convex;

    }

}//end of namespace
  评论这张
 
阅读(778)| 评论(0)

历史上的今天

评论

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

页脚

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