正文

多边形面积并ACM算法详解从基础原理到代码实现解决几何竞赛难题

/0 浏览量
0625

嘿，朋友。看到“多边形面积并”这几个字，你是不是脑子里立刻浮现出那些复杂的交点计算、乱七八糟的区域分割，还有在考场上盯着屏幕怀疑人生的绝望？别慌，咱们今天不整那些虚头巴脑的学术定义，我就当是你旁边那个刚刷完几百道几何题的学长，咱们坐下来，泡杯咖啡，把这块硬骨头一点点啃下来。

你要知道，在ACM/ICPC或者各类算法竞赛里，计算几何往往是“劝退区”。但好消息是，多边形面积并其实是计算几何里相对“干净”的一个问题。它不像求凸包那样有无数种写法，也不像直线相交那样容易卡精度。它有一个非常经典、优雅且通用的解法：扫描线算法（Sweep Line）。

准备好了吗？咱们开始。

一、 为什么我们需要“扫描线”？

想象一下，你面前有一堆随意摆放的多边形（可能是矩形，也可能是任意多边形）。现在，你想算出它们覆盖的总面积。

如果你直接去算所有多边形的并集形状，那简直是噩梦。因为并集可能是一个极其复杂的、带有孔洞的多边形。手动拆分这些区域？除非你想在赛场上发疯。

这时候，扫描线的思想就登场了。

核心直觉：切蛋糕

想象一把无限长的垂直刀（扫描线），从图形的最左边慢慢往右边切过去。

  1. 刀碰到第一个顶点：开始切割。
  2. 刀在两排顶点之间移动：在这一小段水平距离内，图形被切割成的“截面”形状是不变的（或者说，截面的总长度变化是有规律的）。
  3. 刀碰到下一个顶点：截面发生变化，我们更新状态，继续切。
  4. 刀切到最后：结束。

每一小段“切片”，其实都是一个矩形条。如果我们知道这一小段水平宽度是多少，以及当前扫描线上被多边形覆盖的总长度是多少，那么：

\[ \text{这一小块的面积} = \text{覆盖总长度} \times \text{水平宽度} \]

把所有小块的面积加起来，就是总面积！

是不是瞬间简单多了？我们只需要解决两个核心问题：

  1. 如何高效地管理扫描线上的覆盖情况？
  2. 如何快速计算扫描线上被覆盖的总长度？

二、 从矩形并集说起：离散化与线段树

为了讲清楚原理，我们先看最简单的情况：多个矩形的面积并。这是所有多边形面积并的基础。

1. 事件点（Events）

对于矩形，只有左右两条竖边对扫描线有影响。

  • 左边界：进入多边形，覆盖长度+1。
  • 右边界：离开多边形，覆盖长度-1。

我们需要把这些边界提取出来，按X坐标排序。每个边界就是一个“事件”。

class Event:
    def __init__(self, x, y_bottom, y_top, type):
        self.x = x       # 扫描线的X位置
        self.y_bottom = y_bottom # 覆盖区间的下界
        self.y_top = y_top       # 覆盖区间的上界
        self.type = type     # 1 表示入边, -1 表示出边
    
    def __lt__(self, other):
        # 排序规则：先按X坐标，如果X相同，入边优先于出边（这点很重要，防止面积为0或负数）
        if self.x == other.x:
            return self.type > other.type
        return self.x < other.x

2. Y轴的离散化

线段树通常建立在连续的整数索引上。但在几何问题中，Y坐标可以是任意浮点数，而且范围巨大。我们不能为每个可能的Y值开一个节点。

解决方案：离散化。

收集所有矩形的 \(y_{bottom}\) 和 \(y_{top}\)，去重，排序。假设得到数组 ys。 ys[i] 和 ys[i+1] 构成了一个基本区间。我们只需要关心这些基本区间是否被覆盖。

例如，Y坐标有 1, 3, 5, 8。 离散化后，我们有三个基本区间：\([1,3], [3,5], [5,8]\)。 线段树的叶子节点就对应这三个区间。

3. 线段树维护覆盖长度

这是最精妙的部分。传统的线段树维护的是“最大值”或“和”，但这里我们要维护的是“被覆盖的长度”。

每个线段树节点代表一个Y轴区间 \([L, R)\)。我们需要记录两个值：

  • cnt: 这个区间被完整覆盖了多少次（由矩形的上下边决定）。
  • len: 这个区间实际被覆盖的长度。

状态转移逻辑：

  • 如果 cnt[node] > 0：说明这个节点代表的整个区间都被覆盖了。那么 len[node] = ys[R+1] - ys[L]（即该区间的总长度）。
  • 如果 cnt[node] == 0：说明当前没有矩形完全覆盖这个区间。那么 len[node] 取决于它的子节点。
    • 如果是叶子节点，len = 0。
    • 如果不是叶子节点，len[node] = len[left_child] + len[right_child]。

注意：我们不需要 push_down（下传标记），因为 cnt 记录的是完整覆盖次数，只要 cnt > 0，子节点的状态就不重要了，直接取总长度即可。

// 简化的C++线段树核心逻辑示意
struct Node {
    int cnt; // 覆盖次数
    double len; // 当前区间被覆盖的长度
};

Node tree[MAXN << 2];
double ys[MAXN]; // 离散化后的Y坐标数组

void push_up(int node, int l, int r) {
    if (tree[node].cnt > 0) {
        // 如果当前区间被完全覆盖，长度就是该区间的物理长度
        tree[node].len = ys[r + 1] - ys[l];
    } else {
        if (l != r) {
            // 如果没有被完全覆盖，长度等于左右子节点的覆盖长度之和
            tree[node].len = tree[node << 1].len + tree[node << 1 | 1].len;
        } else {
            tree[node].len = 0;
        }
    }
}

void update(int node, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) {
        tree[node].cnt += val;
        push_up(node, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) update(node << 1, l, mid, ql, qr, val);
    if (qr > mid) update(node << 1 | 1, mid + 1, r, ql, qr, val);
    push_up(node, l, r);
}

4. 计算总面积

初始化线段树，将所有事件按X排序。 遍历每个事件：

  1. 计算与前一个事件的X距离：dx = event[i].x - event[i-1].x。
  2. 累加面积：total_area += tree[root].len * dx。
  3. 更新线段树：update(1, 0, m-1, y_index_bottom, y_index_top-1, event[i].type)。

三、 进阶：任意多边形面积并

好了，矩形搞定了。现在问题来了：如果多边形是任意的，边是斜的怎么办？

扫描线算法依然有效，但我们需要更精细地处理“扫描线与多边形边的交点”。

1. 事件点的变化

对于任意多边形，事件点不仅仅是顶点的X坐标。 扫描线在移动过程中，会与多边形的边相交。

  • 当扫描线经过一个顶点时，覆盖的区间集合会发生“突变”（增加或减少一段区间）。
  • 但是，在两个顶点之间，扫描线可能与多条边相交。这些交点的Y坐标会随着X线性变化。

关键难点： 我们不能再简单地用离散的区间更新线段树了，因为交点是连续的。

2. 解决方案：分段扫描 + 动态维护

实际上，对于任意多边形面积并，标准的ACM做法通常是：

  1. 将所有多边形的边打断：以所有顶点的X坐标为分割点，将整个平面切分成若干个垂直的带状区域（Strip）。
  2. 在每个带状区域内：多边形的边变成了直线段。扫描线在该区域内移动时，与边的交点Y坐标是X的线性函数。
  3. 在带状区域内进一步细分：由于交点Y坐标随X变化，不同带状区域内的覆盖情况可能不同。我们需要找到带状区域内，交点Y坐标发生“大小关系交换”的点吗？
    • 其实不需要那么复杂。我们只需要保证在每个最小的垂直条带内，边的相对顺序不变？不，这太复杂了。

更通用的ACM标准做法：

我们将所有多边形的边看作线段。

  1. 收集所有顶点的X坐标，排序去重，得到 \(x_1, x_2, ..., x_k\)。
  2. 这将平面划分为 \(k-1\) 个垂直条带。
  3. 对于第 \(i\) 个条带 \([x_i, x_{i+1}]\)：
    • 找出所有与该条带相交的多边形边。
    • 在条带的中间取一个 \(x_{mid} = (x_i + x_{i+1}) / 2\)。
    • 计算扫描线在 \(x_{mid}\) 处与所有相关边的交点Y坐标。
    • 对这些交点Y坐标排序。
    • 相邻的两个交点构成一个区间。我们需要判断这个区间是在多边形内部还是外部。
    • 利用奇偶规则（Ray Casting Algorithm的变种）：从该区间中点向右发射射线，统计穿过边界的次数。如果是奇数，则在内部；偶数，则在外部。
    • 如果区间在内部，则累加其高度 \(\times\) 条带宽度 \((x_{i+1} - x_i)\)。

等等，这种方法复杂度较高，且容易出错。 在竞赛中，对于任意多边形面积并，还有一个更强大的工具：平面扫描 + 线段树（维护覆盖计数），但这里的线段树不再是维护离散区间，而是维护连续区间上的覆盖深度。

然而，绝大多数情况下，如果题目给出的是任意多边形，且数量不多（N <= 100），我们可以使用更暴力的分解法：

方法A：三角剖分/网格化（适用于小规模）

将多边形分解为三角形，然后求三角形面积并。但这依然复杂。

方法B：基于扫描线的通用实现（推荐）

让我们回到扫描线，但这次我们处理的是任意多边形的边。

  1. 预处理边：将每条边表示为 \((x_1, y_1) \to (x_2, y_2)\)。

  2. 事件点：所有顶点的X坐标。

  3. 带状区域处理： 在 \([x_i, x_{i+1}]\) 之间，多边形的边是直线。 我们需要知道在这个带状区域内，哪些Y范围是被覆盖的。

    这里有一个技巧：将多边形分解为梯形。 任意多边形可以分解为一系列梯形（或三角形，视为退化梯形）。 对于一个多边形，从左到右扫描：

    • 遇到顶点，更新当前的“活跃边”列表。
    • 活跃边是指当前扫描线穿过的边。
    • 在两个X坐标之间，活跃边的Y坐标线性变化。
    • 我们将这些活跃边按Y坐标排序。
    • 相邻两条活跃边之间的区域，如果属于同一个多边形，则可能被覆盖。

    这太复杂了！ 让我们换一个思路，这也是很多ACM选手使用的“割补法”结合“扫描线”。

    实际上，对于任意多边形面积并，最稳健的竞赛算法是：

    1. 将所有多边形的边进行离散化X切割。
    2. 在每个垂直条带内，计算所有边与条带中线 \(x_{mid}\) 的交点。
    3. 将这些交点Y坐标排序。
    4. 判断每个小区间 \([y_j, y_{j+1}]\) 的覆盖状态。
      • 取区间中点 \(y_{mid}\)。
      • 构造一个测试点 \((x_{mid}, y_{mid})\)。
      • 使用点在多边形内判断（Point in Polygon）算法，判断该点被多少个多边形覆盖。
      • 如果覆盖层数 \(> 0\)，则该小区间贡献面积：\((y_{j+1} - y_j) \times (x_{i+1} - x_i)\)。

    复杂度分析：

    • X坐标排序：\(O(N \log N)\)。
    • 条带数量：\(O(N)\)。
    • 每个条带内，最多有 \(2N\) 个交点。排序 \(O(N \log N)\)。
    • 每个小区间判断点是否在多边形内：\(O(M)\)，其中M是多边形总数。
    • 总复杂度：\(O(N^2 M)\)。

    如果N（多边形数量）较小（比如N<=50），这个算法是完全可行的，而且代码实现比线段树简单得多，不容易出错！

四、 代码实战：任意多边形面积并（通用解法）

鉴于线段树处理任意多边形过于繁琐且易错，我为你提供一个基于“垂直条带+点包含测试”的实现。这种方法逻辑清晰，适合N较小的情况，也是很多ACM题目的通解。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

const double EPS = 1e-8;

struct Point {
    double x, y;
    bool operator<(const Point& other) const {
        if (abs(x - other.x) > EPS) return x < other.x;
        return y < other.y;
    }
    bool operator==(const Point& other) const {
        return abs(x - other.x) < EPS && abs(y - other.y) < EPS;
    }
};

struct Polygon {
    vector<Point> pts;
};

// 判断点p是否在多边形poly内部
// 使用射线法：从p向右水平发射射线，统计与多边形边的交点数
bool isInside(const Point& p, const Polygon& poly) {
    int intersections = 0;
    int n = poly.pts.size();
    for (int i = 0; i < n; ++i) {
        Point p1 = poly.pts[i];
        Point p2 = poly.pts[(i + 1) % n];
        
        // 确保p1是下方的点，p2是上方的点（或者反之，统一处理）
        if (p1.y > p2.y) swap(p1, p2);
        
        // 如果点在边的端点上，视为在内部
        if (abs(p.y - p1.y) < EPS && abs(p.x - p1.x) < EPS) return true;
        if (abs(p.y - p2.y) < EPS && abs(p.x - p2.x) < EPS) return true;
        
        // 检查射线是否与边相交
        // 条件1: p的y坐标在边的高度范围内 (p1.y <= p.y < p2.y)
        // 条件2: p在边的左侧 (通过叉积或直线方程判断)
        if (p.y >= p1.y && p.y < p2.y) {
            // 计算边在高度p.y处的x坐标
            double x_intersect = p1.x + (p2.x - p1.x) * (p.y - p1.y) / (p2.y - p1.y);
            
            if (p.x < x_intersect) {
                intersections++;
            }
        }
    }
    return (intersections % 2) == 1;
}

double polygonAreaUnion(const vector<Polygon>& polys) {
    if (polys.empty()) return 0.0;
    
    // 1. 收集所有顶点的X坐标
    vector<double> xs;
    for (const auto& poly : polys) {
        for (const auto& pt : poly.pts) {
            xs.push_back(pt.x);
        }
    }
    sort(xs.begin(), xs.end());
    // 去重
    xs.erase(unique(xs.begin(), xs.end(), [](double a, double b){ return abs(a-b) < EPS; }), xs.end());
    
    double totalArea = 0.0;
    
    // 2. 遍历每个垂直条带
    for (size_t i = 0; i < xs.size() - 1; ++i) {
        double x_left = xs[i];
        double x_right = xs[i+1];
        
        // 跳过宽度为0的条带
        if (abs(x_right - x_left) < EPS) continue;
        
        // 取条带中间的X坐标
        double x_mid = (x_left + x_right) / 2.0;
        
        // 3. 收集该条带内所有边与扫描线 x=x_mid 的交点Y坐标
        vector<double> ys;
        for (const auto& poly : polys) {
            int n = poly.pts.size();
            for (int j = 0; j < n; ++j) {
                Point p1 = poly.pts[j];
                Point p2 = poly.pts[(j + 1) % n];
                
                // 如果边跨越了 x_mid
                if ((p1.x <= x_mid && p2.x > x_mid) || (p1.x > x_mid && p2.x <= x_mid)) {
                    // 计算交点Y
                    // 直线方程: (y - p1.y) / (x - p1.x) = (p2.y - p1.y) / (p2.x - p1.x)
                    // y = p1.y + (x - p1.x) * (p2.y - p1.y) / (p2.x - p1.x)
                    double slope = (p2.y - p1.y) / (p2.x - p1.x);
                    double y_inter = p1.y + slope * (x_mid - p1.x);
                    ys.push_back(y_inter);
                }
            }
        }
        
        // 4. 对Y坐标排序
        sort(ys.begin(), ys.end());
        
        // 5. 遍历相邻Y坐标构成的区间
        for (size_t k = 0; k < ys.size() - 1; ++k) {
            double y_bottom = ys[k];
            double y_top = ys[k+1];
            
            if (abs(y_top - y_bottom) < EPS) continue;
            
            // 取区间中点作为测试点
            double test_x = x_mid;
            double test_y = (y_bottom + y_top) / 2.0;
            Point testPt = {test_x, test_y};
            
            // 判断该点是否被至少一个多边形覆盖
            bool covered = false;
            for (const auto& poly : polys) {
                if (isInside(testPt, poly)) {
                    covered = true;
                    break;
                }
            }
            
            if (covered) {
                totalArea += (y_top - y_bottom) * (x_right - x_left);
            }
        }
    }
    
    return totalArea;
}

int main() {
    // 示例：两个重叠的矩形
    // Rect 1: (0,0) -> (2,2)
    // Rect 2: (1,1) -> (3,3)
    
    Polygon p1, p2;
    p1.pts = {{0,0}, {2,0}, {2,2}, {0,2}};
    p2.pts = {{1,1}, {3,1}, {3,3}, {1,3}};
    
    vector<Polygon> polys = {p1, p2};
    
    cout << fixed << setprecision(2);
    cout << "Total Area of Union: " << polygonAreaUnion(polys) << endl;
    
    return 0;
}

代码解读

  1. 离散化X轴：我们只关心顶点所在的垂直线。在这些线之间，多边形的拓扑结构（谁在左谁在右）不会改变，只有边的Y坐标线性变化。
  2. 条带内交点：在每个条带 \([x_i, x_{i+1}]\) 中，我们取中点 \(x_{mid}\)。所有穿过这个条带的边都会与 \(x=x_{mid}\) 相交。这些交点的Y坐标将条带在Y方向上分割成若干小区间。
  3. 区间测试：在每个小区间 \([y_j, y_{j+1}]\) 中，取中点 \((x_{mid}, y_{mid})\)。因为这个点在条带内部且远离所有边的交叉点，所以它要么完全在多边形内，要么完全在外。我们使用经典的射线法判断点是否在多边形内。
  4. 累加面积：如果点被覆盖，说明整个小矩形条都被覆盖了，累加其面积。

优缺点分析

  • 优点：
    • 代码逻辑极其清晰，不易出错。
    • 不需要处理复杂的线段树和离散化Y轴。
    • 适用于任意多边形（凸或凹）。
  • 缺点：
    • 时间复杂度较高：\(O(N^2 \cdot M)\)，其中N是顶点总数，M是多边形数量。
    • 如果多边形数量非常多（如N > 1000），可能会超时。

对于大规模数据，你需要使用扫描线+线段树的高级版本，但那涉及到更复杂的连续区间维护和浮点精度控制，通常在竞赛中，如果N较大，题目会给出特殊性质（如矩形）或者允许近似解。对于一般的几何竞赛题，上述算法足以应对大部分非极限情况。

五、 避坑指南：精度与陷阱

在ACM赛场上，几何题最容易挂的地方就是精度。

  1. EPS的使用： 永远不要用 == 比较浮点数。定义一个很小的 EPS（如 \(1e-8\) 或 \(1e-9\)），所有比较都用 abs(a-b) < EPS。

  2. 排序稳定性： 在收集事件点或Y坐标时，如果两个坐标非常接近，它们的相对顺序可能影响结果。确保你的排序是稳定的，或者在比较时加入次要关键字（如Y坐标）。

  3. 垂直边处理： 在判断点是否在多边形内时，如果测试点恰好落在边上，通常视为在内部。但在扫描线算法中，测试点取的是区间中点，所以很少会恰好落在边上。不过，计算交点时，要注意除以零的情况（垂直边）。

  4. 自相交多边形： 上述算法假设多边形是简单的（不自交）。如果多边形自交，射线法的奇偶规则可能会失效。此时需要使用非零绕数规则（Non-zero Winding Rule），修改 isInside 函数中的计数逻辑。

六、 总结

多边形面积并，看似复杂，实则可以通过“化整为零”的思想解决。

  • 矩形并：用扫描线+线段树，效率高，\(O(N \log N)\)。
  • 任意多边形并：用垂直条带+点包含测试，逻辑简单，鲁棒性强，\(O(N^2 M)\)。

作为程序员，我们不仅要写出能跑的代码，更要写出可维护、可理解的代码。在考场上，一个逻辑清晰、虽然慢一点但绝不会WA（Wrong Answer）的算法，往往比一个复杂但容易出错的优化算法更能带你拿牌。

希望这篇文章能帮你理清思路。下次再看到多边形面积并，别再头疼了，拿起笔，画出扫描线，一切迎刃而解。加油！

-- 展开阅读全文 --