《算法技术手册》一3.5.4 解决方案

简介: 本节书摘来华章计算机《算法技术手册》一书中的第3章 ,第3.5.4节, George T.Heineman Gary Pollice Stanley Selkow 著 杨晨 曹如进 译 译更多章节内容可以访问云栖社区“华章计算机”公众号查看。

3.5.4 解决方案

如果手动计算凸包,你应该可以很轻松地处理好各种极端情况。但是如果需要用计算机语言来描叙每一个步骤,我们可能会觉得比较困难。Graham扫描算法的关键点在于计算和最低点的极角大小。一旦计算并且排序之后,算法只需要遍历所有的点,不断地构建凸包并且根据新发现的信息调整结构即可。代码见例3-1。
例3-1:Graham扫描算法的实现
public class NativeGrahamScan implements IConvexHull {

public IPoint[] compute(IPoint[] pts) {
    int n = pts.length;
    if (n < 3) {
        returnpts;
    }
    // 如果最后一个点不是最低点,
    // 那么找到最低点,然后和数组中最后一个点交换
    int lowest = 0;
    double lowestY = pts[0].getY();
    for (inti = 1; i < n; i++) {
        if (pts[i].getY() < lowestY) {
            lowestY = pts[i].getY();
            lowest = i;
        }
    }
    if (lowest != n - 1) {
        IPoint temp = pts[n - 1];
        pts[n - 1] = pts[lowest];
        pts[lowest] = temp;
    }

    // 将pts[0...n-2]按照和pts[n-1]的极角按照从大到小降序排列
    new HeapSort<IPoint>().sort(pts, 0, n - 2,
                                new ReversePolarSorter(pts[n - 1]));
   
    // 有三个点一定在凸包上,它们分别是:
    // 极角最小点pts[n-2]、最低点pts[n-1]还有极角最大点p[0]
    // 初始化凸包,从pts[n-2]和pts[n-1]开始
    DoubleLinkedList<IPoint> list = new DoubleLinkedList<IPoint>();
    list.insert(pts[n - 2]);
    list.insert(pts[n - 1]);
    // 先处理多点共线的情况
    double firstAngle = Math.atan2(pts[0].getY() - lowest, 
                                   pts[0].getX() - pts[n - 1].getX());
    double lastAngle = Math.atan2(pts[n - 2].getY() - lowest, 
                                  pts[n - 2].getX() - pts[n - 1].getX());
    if (firstAngle == lastAngle) {
        return new IPoint[]{pts[n - 1], pts[0]};
    }

    // 顺序访问每个点,删掉不正确的点
    // 一定会出现某个点"向右转",
    // 所以这个while循环必然能够结束
    for (int i = 0; i < n - 1; i++) {
        while (isLeftTurn(list.last().prev().value(), 
                          list.last().value(),
                          pts[i])) {
            list.removeLast();
        }

        // 将下一个点加入凸包中
        list.insert(pts[i]);
    }

    // 最后一个点是重复的,所以我们只需要从最低的点开始取n-1个点即可
    IPoint hull[] = new IPoint[list.size() - 1];
    DoubleNode<IPoint> ptr = list.first().next();
    intidx = 0;
    while (idx < hull.length) {
      hull[idx++] = ptr.value();
      ptr = ptr.next();
    }

    return hull;
}
/** 使用共线性检查来确定左拐 */
public static boolean isLeftTurn(IPoint p1, IPoint p2, IPoint p3) {
    return (p2.getX() - p1.getX()) * (p3.getY() - p1.getY()) -
           (p2.getY() - p1.getY()) * (p3.getX() - p1.getX()) > 0;
}

}

/* 排序类。按照和指定点的极角值降序排列 /
class ReversePolarSorter implements Comparator {

/** 存储用于比较的指定点的x、y坐标 */
final double baseX;
final double baseY;

/** ReversePolarSorter将所有点和指定点比较 */
public ReversePolarSorter(IPoint base) {
    this.baseX = base.getX();
    this.baseY = base.getY();
}

public int compare(IPoint one, IPoint two) {
    if (one == two) { return 0; }

    // 确保使用atan2方法来计算极角,
    // 这个办法可行是因为当前点的y值永远大于指定点的y值
    double oneY = one.getY();
    double twoY = two.getY();
    double oneAngle = Math.atan2(oneY - baseY, one.getX() - baseX);
    double twoAngle = Math.atan2(twoY - baseY, two.getX() - baseX);

    if (oneAngle > twoAngle) { return -1;}
    else if (oneAngle < twoAngle) { return +1; }
    
    // 如果角度相同,那么就比较y值,确保凸包算法能够得到正确的值
    if (oneY > twoY) { return -1; }
    else if (oneY < twoY) { return +1; }

    return 0;
}

}
如果整个点集(n > 2)的所有点都在同一条线上,那么在这种特殊情况下,凸包就只是首尾两端的点。在这种情况下计算出来的凸包可能会包含多个共线的连续点,因为算法中并没有逻辑去试图删除这些共线的点。

相关文章
|
1月前
|
存储 算法 物联网
R-Tree算法:空间索引的高效解决方案
【5月更文挑战第17天】R-Tree是用于多维空间索引的数据结构,常用于地理信息系统、数据库和计算机图形学。它通过分层矩形区域组织数据,支持快速查询。文章介绍了R-Tree的工作原理、应用场景,如地理信息存储和查询,以及Python的`rtree`库实现示例。此外,还讨论了R-Tree的优势(如空间效率和查询性能)与挑战(如实现复杂和内存消耗),以及优化和变种,如R* Tree和STR。R-Tree在机器学习、实时数据分析等领域有广泛应用,并与其他数据结构(如kd-trees和quad-trees)进行比较。未来趋势将聚焦于优化算法、动态适应性和分布式并行计算。
41 1
|
11天前
|
SQL 存储 算法
【MySQL技术内幕】6.4-锁的算法
【MySQL技术内幕】6.4-锁的算法
23 1
|
11天前
|
存储 算法 关系型数据库
【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
14 1
|
13天前
|
算法 C语言 Ruby
分形逃逸时间算法中的 Normalized Iteration Count(NIC)技术 让颜色更柔和
Normalized Iteration Count (NIC) 技术是一种提升逃逸时间算法中分形图像质量的方法,它产生更平滑的颜色过渡。数学公式表示为:`mu = n + 1 - log(log(|Z(n)|)) / log(p)`,其中 `Z(n)` 是迭代次数,`|Z(n)|` 是复数模长,`p` 通常取2。示例代码提供了 Ruby, Maxima 和 C 语言的实现。
|
15天前
|
存储 自然语言处理 算法
编辑距离算法全解析:优化文本处理的关键技术
编辑距离算法全解析:优化文本处理的关键技术
|
20天前
|
算法 NoSQL Python
开山之作!Python数据与算法分析手册,登顶GitHub!
若把编写代码比作行军打仗,那么要想称霸沙场,不能仅靠手中的利刃,还需深谙兵法。 Python是一把利刃,数据结构与算法则是兵法。只有熟读兵法,才能使利刃所向披靡。只有洞彻数据结构与算法,才能真正精通Python。
|
20天前
|
存储 人工智能 算法
RAG技术的高级应用和算法
文章主要探讨了RAG技术的高级应用和算法,系统化地整理了各种方法。
|
20天前
|
机器学习/深度学习 数据采集 算法
基于机器学习的推荐算法构建技术详解
【6月更文挑战第4天】本文详述了构建基于机器学习的推荐算法,特别是协同过滤方法。从用户和物品相似性的角度,解释了用户-用户和物品-物品协同过滤的工作原理。涵盖了数据准备、预处理、特征工程、模型训练、评估优化及结果展示的构建流程。推荐算法在电商、视频和音乐平台广泛应用,未来将受益于大数据和AI技术的进步,提供更智能的推荐服务。
|
26天前
|
算法 NoSQL Python
开山之作!Python数据与算法分析手册,登顶GitHub!
若把编写代码比作行军打仗,那么要想称霸沙场,不能仅靠手中的利刃,还需深谙兵法。 Python是一把利刃,数据结构与算法则是兵法。只有熟读兵法,才能使利刃所向披靡。只有洞彻数据结构与算法,才能真正精通Python
|
11天前
|
存储 算法 Java
分布式唯一ID解决方案-雪花算法
分布式唯一ID解决方案-雪花算法
10 0

热门文章

最新文章