Algorithm23 计算几何凸包算法

[TOC]

POJ1113-凸包算法

题目链接：http://poj.org/problem?id=1113 凸包算法的板题，找出凸包，计算凸包的周长加上以要求的距离为半径的圆的周长即可。

卷包裹法

思路：

点集预处理，以横坐标为准从小到大(横坐标相同以纵坐标从小到大)
从点集的第一个点开始找上凸包。
- 如果要添加的点在凸包的点集中最新添加的两个点所形成的直线的右边，将改点添加进凸包的点集。
- 如果在左边，把凸包点集中最靠后的点移除，再判断，直到在右边就添加。
从点集的最后一个点开始找下凸包。

判断点在线的左边还是右边：利用叉积(几何意义就是通过比较斜率，利用叉积的大小可以防止斜率为零或者无穷的情况)

Graham扫描法

思路：

点集预处理：通过两次预处理，首先提取处横纵坐标都最小的，也就是以横坐标为准从小到大(横坐标相同以纵坐标从小到大)，然后再平移坐标轴使原点与第一步找到的点重合，根据其他点与原点的斜率大小进行排序
按照预处理的顺序找凸包，要保证新添加的点在凸包的点集中最新添加的两个点所形成的直线的左边。

关于得到凸包点集中是否要凸包的边上的点(初顶点以外的其他点)

eg: (1,1) (1,2) (2,1) (1,2) (3,1) 包含凸包边上的点：(1,1) (1,2) (2,1) (1,2) (3,1) 不包含：(1,1) (1,2) (1,2) (3,1)

卷包裹法得到不包含凸包边上的点 解析：此时abc在一条直线，x同或者y同，那么得到的叉积必为零，同时不满足添加进凸包点集的条件就是在线的左边或者在线上，要等于号。

int cross(point a,point b,point c){
    return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}

int solve(){
    int idx = 0;
    // upper 0 -> n-1
    for (int i = 0; i < n; i++){
        while (idx >1 && cross(con[idx-1], e[i], con[idx-2]) >= 0) idx--;
        con[idx++] = e[i];
    }
    int s = idx;
    // lower n-1 -> 0
    for (int i = n-1; i >= 0; i--) {
        while (idx > s && cross(con[idx-1], e[i], con[idx-2]) >= 0) idx--;
        con[idx++] = e[i];
    }
    return idx;
}

Graham-Scan法：同样道理：

int idx = 0;
for (int i = 0; i < n; i++) {
	if (i > 1 && cross(con[idx-1], e[i], con[idx-2]) <= 0) idx--;
   	con[idx++] = e[i];
}
con[idx++] = e[0];

完整代码：

卷包裹法：

//
//  main.cpp
//  poj1113_凸包板题
//
//  Created by 陈冉飞 on 2020/2/2.
//  Copyright © 2020 陈冉飞. All rights reserved.
//

#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 1010
struct point{
    int x,y;
    bool operator < (const point a)const{
        if(x == a.x) return y < a.y;
        return x<a.x;
    }
}e[maxn],con[maxn];
int n,l,T;
double ans =0;
#define PI atan(1.0)*4
#include <cmath>

int cross(point a,point b,point c){
    return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}

int solve(){
    int idx = 0;
    // upper 0 -> n-1
    for (int i = 0; i < n; i++){
        while (idx >1 && cross(con[idx-1], e[i], con[idx-2]) >= 0) idx--;
        con[idx++] = e[i];
    }
    int s = idx;
    for (int i = n-1; i >= 0; i--) {
        while (idx > s && cross(con[idx-1], e[i], con[idx-2]) >= 0) idx--;
        con[idx++] = e[i];
    }
    // lower n-1 -> 0
    return idx;
}

int main(int argc, const char * argv[]) {
    scanf("%d",&T);
    while(T--) {
        ans = 0;
        scanf("%d%d",&n,&l);
            for (int i = 0; i < n; i++) scanf("%d%d",&e[i].x,&e[i].y);
            sort(e, e+n);
            for (int i = 1; i < solve(); i++) {
//                printf("%d %d %d\n",i,con[i].x,con[i].y);
                ans += sqrt(1.0*(con[i].x-con[i-1].x)*(con[i].x-con[i-1].x)+(con[i].y-con[i-1].y)*(con[i].y-con[i-1].y));
            }
            
            printf("%.0lf\n",ans+2*PI*l);
        if(T)printf("\n");
    }
    return 0;
}

graham-scan：

//
//  main.cpp
//  poj1113_凸包板题_graham扫描算法
//
//  Created by 陈冉飞 on 2020/2/3.
//  Copyright © 2020 陈冉飞. All rights reserved.
//

#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 1010
struct point{
    int x,y;
}e[maxn],con[maxn];
int n,l,T;
double ans =0;
#define PI atan(1.0)*4
#include <cmath>

int cross(point a,point b,point c){
    return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}

double dis(point a,point b){
    return sqrt(1.0*pow(a.x-b.x, 2)+pow(a.y-b.y, 2));
}

bool cmp1(point a,point b){
    if(a.x == b.x) return a.y < b.y;
    return a.x<b.x;
}

bool cmp2(point a,point b){
    int c1 = cross(e[0], a, b);
    if (!c1) return dis(e[0], a)< dis(e[0], b);
    return c1 > 0;
}

int solve(){
    int idx = 0;
    for (int i = 0; i < n; i++) {
        if (i > 1 && cross(con[idx-1], e[i], con[idx-2]) <= 0) idx--;
        con[idx++] = e[i];
    }
    con[idx++] = e[0];
    return idx;
}

int main(int argc, const char * argv[]) {
    scanf("%d",&T);
    while(T--) {
        ans = 0;
        scanf("%d%d",&n,&l);
        for (int i = 0; i < n; i++) scanf("%d%d",&e[i].x,&e[i].y);
        sort(e, e+n,cmp1);
        sort(e+1, e+n, cmp2);
        for (int i = 1; i < solve(); i++) ans += dis(con[i-1], con[i]);
        printf("%.0lf\n",ans+2*PI*l);
        if(T)printf("\n");
    }
    return 0;
}

Posted on Feb 4, 2020

Algorithm23 计算几何 凸包算法