算法有点甜之 Graham's Scan 算法的水平序实现

2016-08-23 535 次浏览 算法有点甜 数据结构与算法

所需基础

计算几何 - 凸包、了解 Graham's Scan 算法及其极角序实现。

概述

Graham's Scan 算法的水平序实现是不同于「极角序」的另一种实现方式,它将平面点集按照水平序排序,即按 y 坐标排序,相同时再按 x 坐标排序,之后进行扫描来求得凸包。

优势

  • 排序规则更简单
  • 起始点十分容易确定
  • 解决了「极角序」方法中的共线点问题

时间复杂度

$O(nlogn)$

算法实现

  1. 将平面点集按照先 y 后 x 升序排序(图例中存在刻意设定的共线点情况);

Graham's Scan 算法的水平序实现 - 0

  1. 做右链扫描 (下标 0 ~ n-1);

Graham's Scan 算法的水平序实现 - 1

Graham's Scan 算法的水平序实现 - 2

Graham's Scan 算法的水平序实现 - 3

Graham's Scan 算法的水平序实现 - 4

Graham's Scan 算法的水平序实现 - 5

Graham's Scan 算法的水平序实现 - 6

  1. 反向做左链扫描(下标 n-1 ~ 0),忽略右链扫描时已生成的点。此部分图例用红线标出。

Graham's Scan 算法的水平序实现 - 7

Graham's Scan 算法的水平序实现 - 8

Graham's Scan 算法的水平序实现 - 9

Graham's Scan 算法的水平序实现 - 10


代码实现

const int MAXN = ?;    // n 的最大值

struct point {
    int x;
    int y;
    point operator - (const point &p) const {
        point ret;
        ret.x = x - p.x;
        ret.y = y - p.y;
        return ret;
    }
} p[MAXN];    // 点集数组
int n;    // 点的个数

// 水平序的排序比较函数
bool cmp(point a, point b) {
    if(a.y != b.y) return a.y < b.y;
    else return a.x < b.x;
}

// Det 和 Cross 函数用于计算叉积
int Det(int x1, int y1, int x2, int y2) {
    return x1*y2 - x2*y1;
}

int Cross(point a, point b, point p) {
    return Det(b.x-a.x, b.y-a.y, p.x-a.x, p.y-a.y);
}

// 计算平面上两点间直线距离
int CalculateDistance(point a, point b) {
    point p = a - b;

    return p.x*p.x + p.y*p.y;
}

// Graham's Scan 算法(水平序)
void GrahamScan() {
    sort(p, p+n, cmp);    // 水平序排序
    point res[MAXN];    // 用来记录求得的凸包点集
    int top = 0;
    for(int i=0; i<n; ++i) {    // 反向扫描右链
        while(top>=2 && Cross(res[top-2], res[top-1], p[i])<0) {
            top--;
        }
        res[top++] = p[i];
    }
    int tmp = top;
    for(int i=n-2; i>=0; --i) {    // 扫描左链
        // "top>tmp" 用于保证右链已生成的点不会被左链扫描所影响
        while(top>tmp && Cross(res[top-2], res[top-1], p[i])<0) {
            top--;
        }
        res[top++] = p[i];
    }
}

例题讲解

POJ 2187 Beauty Contest

大致题意

给出二维平面中的一组点集,求最大的两点间距离的平方。

解题思路

首先求得所给点集的凸包,然后枚举凸包上的所有点对,找出其中最大的两点间距离即可。

参考代码

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 50000;

struct point {
    int x;
    int y;
    point operator - (const point &p) const {
        point ret;
        ret.x = x - p.x;
        ret.y = y - p.y;
        return ret;
    }
} p[MAXN];
int n;

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

int Det(int x1, int y1, int x2, int y2) {
    return x1*y2 - x2*y1;
}

int Cross(point a, point b, point p) {
    return Det(b.x-a.x, b.y-a.y, p.x-a.x, p.y-a.y);
}

int CalculateDistance(point a, point b) {
    point p = a - b;

    return p.x*p.x + p.y*p.y;
}

int GrahamScan() {
    sort(p, p+n, cmp);
    point res[MAXN];
    int top = 0;
    for(int i=0; i<n; ++i) {
        while(top>=2 && Cross(res[top-2], res[top-1], p[i])<0) {
            top--;
        }
        res[top++] = p[i];
    }
    int tmp = top;
    for(int i=n-2; i>=0; --i) {
        while(top>tmp && Cross(res[top-2], res[top-1], p[i])<0) {
            top--;
        }
        res[top++] = p[i];
    }
    int ans = 0;
    // 枚举凸包上的所有点对
    for(int i=0; i<top-2; ++i) {
        for(int j=i+1; j<top-1; ++j) {
            ans = max(ans, CalculateDistance(res[i], res[j]));
        }
    }

    return ans;
}

int main(int argc, char const *argv[]) {
    scanf("%d", &n);
    for(int i=0; i<n; ++i) {
        scanf("%d %d", &p[i].x, &p[i].y);
    }
    printf("%d\n", GrahamScan());
    
    return 0;
}

参考资料

  • 《算法艺术与信息学竞赛》(清华大学出版社) 刘汝佳 黄亮 著

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2016/08/23/aiabs_graham-s_scan.dream

还不快抢沙发

添加新评论