企业官网建设流程全解析

前言

计算两个矩形重叠部分的面积,听起来是一行公式的事,实际写起来却集中了坐标归一化、边界钳制、整数溢出、浮点比较四类问题。最常见的场景是轴对齐矩形(axis-aligned bounding box, AABB),也就是矩形的边平行于坐标轴,此时重叠区域仍然是矩形,可以用「右边界取小、左边界取大」直接算出宽高。另一类场景是任意旋转的矩形,那需要分离轴定理(separating axis theorem, SAT),没有简单的区间交公式。

典型误解有三个。第一,拿到两个角点就直接相减,没有先保证「左下、右上」的顺序,遇到x2 < x1的输入会算出负宽度。第二,把负的重叠宽高直接相乘,得到正数,把「不相交」误判成「有重叠」。第三,用int存坐标却用int算面积,坐标接近十万时乘积就溢出,而有符号整数溢出是未定义行为(undefined behavior, UB)。

本文只讨论轴对齐矩形,先讲区间交的推导,再分别给出浮点版与整数版的实现,然后说明相切、包含、多个矩形等边界情形,最后列出常见坑点。示例以 C++17 为基准,不涉及任何图形库。

一、一维区间交是二维问题的基础

两个闭区间[a1, a2]与[b1, b2]的交集长度是max(0, min(a2, b2) - max(a1, b1))。这个式子的含义很直白:交集的左端点是两个左端点中较大的那个,右端点是两个右端点中较小的那个;若右端点小于左端点,说明区间分离,长度取 0。

二维轴对齐矩形的重叠区域,正是「x 方向区间的交」与「y 方向区间的交」的笛卡尔积。因此重叠面积等于两个方向交集长度的乘积。只要矩形是轴对齐的,这个分解就严格成立;一旦矩形旋转,投影到坐标轴上的区间交会高估真实重叠,公式失效。

需要区分「闭区间」与「开区间」的语义。几何上两个矩形共享一条边时,交集是一条线段,面积为 0。用闭区间公式算出的宽度恰好是 0,面积也是 0,结果一致。真正需要小心的是浮点误差:理论上相切的情形,浮点减法可能得到1e-16这样的微小正数,直接判断> 0会把相切误判为有重叠。是否处理这一点取决于业务:图形渲染通常无所谓,几何判定则应当引入容差。

二、坐标归一化

很多接口用「任意两个对角点」描述矩形,例如鼠标拖拽时起点可能在右下、终点在左上。此时必须先归一化:左下角取两个点坐标的分量最小值,右上角取分量最大值。归一化之后,后续所有公式都可以假定x1 <= x2、y1 <= y2。

归一化还有一个好处:让「包含」情形自然成立。当一个矩形完全在另一个内部时,取小取大的结果仍然是内层矩形的边界,宽度高度都是内层尺寸,不需要额外分支。

三、整数版与浮点版

整数坐标适合网格、像素、地图格子等场景。此时宽高用整数减法,面积必须用更宽的类型。假设坐标范围是[-10^9, 10^9],宽高最大约2 * 10^9,乘积约4 * 10^18,仍在long long的范围内(约9.22 * 10^18)。如果坐标范围更大,或者需要累加多个面积,就必须考虑__int128(GCC/Clang 扩展)或高精度库,并且要明确标注平台相关性。

浮点坐标适合几何计算、图形学。此时面积用double,比较用容差。不要用float存大范围坐标,有效位数不够,减法会产生明显的抵消误差。

无论哪种类型,「先算宽度、判断是否为正、再乘高度」的顺序都比「先乘再判断」安全:前者在宽度为负时直接返回 0,不会产生负面积,也不会让两个负数相乘得到正数。

四、完整示例

下面给出浮点版与整数版两套实现,以及两个矩形的并集面积(容斥)。并集只对两个矩形成立,矩形数量增加后不能简单相加。

// 适用于 C++17
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>

struct Rect {
double x1, y1, x2, y2; // 约定 x1 <= x2, y1 <= y2
};

// 由任意两个对角点构造,自动归一化
Rect makeRect(double ax, double ay, double bx, double by) {
return Rect{std::min(ax, bx), std::min(ay, by),
std::max(ax, bx), std::max(ay, by)};
}

double rectArea(const Rect& r) {
return (r.x2 - r.x1) * (r.y2 - r.y1);
}

double overlapWidth(const Rect& a, const Rect& b) {
return std::max(0.0, std::min(a.x2, b.x2) - std::max(a.x1, b.x1));
}

double overlapHeight(const Rect& a, const Rect& b) {
return std::max(0.0, std::min(a.y2, b.y2) - std::max(a.y1, b.y1));
}

double overlapArea(const Rect& a, const Rect& b) {
return overlapWidth(a, b) * overlapHeight(a, b);
}

// 两个矩形的并集面积:容斥原理,只适用于两个矩形
double unionArea(const Rect& a, const Rect& b) {
return rectArea(a) + rectArea(b) - overlapArea(a, b);
}

struct IRect {
long long x1, y1, x2, y2;
};

IRect makeIRect(long long ax, long long ay, long long bx, long long by) {
return IRect{std::min(ax, bx), std::min(ay, by),
std::max(ax, bx), std::max(ay, by)};
}

long long overlapAreaI(const IRect& a, const IRect& b) {
const long long w = std::min(a.x2, b.x2) - std::max(a.x1, b.x1);
if (w <= 0) {
return 0; // 分离或相切
}
const long long h = std::min(a.y2, b.y2) - std::max(a.y1, b.y1);
if (h <= 0) {
return 0;
}
return w * h; // 坐标范围需保证乘积不溢出
}

int main() {
Rect a = makeRect(0.0, 0.0, 4.0, 3.0);
Rect b = makeRect(2.0, 1.0, 6.0, 5.0);
std::cout << overlapArea(a, b) << '\n'; // 宽 2、高 2
std::cout << unionArea(a, b) << '\n'; // 12 + 16 - 4

Rect touch = makeRect(4.0, 0.0, 7.0, 3.0);
std::cout << overlapArea(a, touch) << '\n'; // 共享一条边,面积 0

IRect ia = makeIRect(0, 0, 4, 3);
IRect ib = makeIRect(2, 1, 6, 5);
std::cout << overlapAreaI(ia, ib) << '\n';

IRect inside = makeIRect(1, 1, 2, 2); // 完全包含
std::cout << overlapAreaI(ia, inside) << '\n';
return 0;
}

按标准语义推演:第一个重叠区域是[2,4] × [1,3],面积 4;并集为12 + 16 - 4 = 24;相切矩形宽度为 0,面积 0;整数版同样得到 4;完全包含时交集就是内层矩形,面积为 1。这些结果由公式直接得出,未经编译运行核对。

五、多个矩形与旋转矩形

矩形数量超过两个时,并集面积不能靠容斥手算——容斥的项数随矩形数指数增长。常用做法是扫描线:把所有竖直边按 x 排序,相邻两条竖边之间形成一条带状区域,统计该带内被覆盖的 y 区间总长度,乘以带宽后累加。y 方向的覆盖长度通常用线段树维护。这套算法与「矩形面积并」是同一个问题,复杂度为 O(n log n)。

旋转矩形则是另一类问题。两个任意朝向的矩形是否相交,要用分离轴定理:分别检查两个矩形的四条边法线,以及额外的两条正交方向,若存在一条轴使两者投影不重叠,则不相交。要算重叠面积,还得求两个凸多边形的交,再用鞋带公式算多边形面积。这不是几行区间交能解决的,遇到这类需求应当使用成熟的几何库,并以其官方文档为准。

常见坑点

一、不归一化直接相减

❌double w = std::min(a.x2, b.x2) - std::max(a.x1, b.x1);而输入可能是x1 > x2,算出负宽度。

✅ 构造时用makeRect统一取std::min与std::max,或者在使用前断言x1 <= x2 && y1 <= y2。

二、负宽高直接相乘

❌return (minX2 - maxX1) * (minY2 - maxY1);两个负数相乘得到正面积,分离的矩形被算成重叠。

✅ 宽高分别std::max(0.0, ...),或者先判断if (w <= 0 || h <= 0) return 0;。

三、用int计算面积

❌int area = w * h;坐标到十万量级时乘积溢出,有符号溢出是 UB。

✅ 宽高与面积都用long long;浮点场景用double,不要用float。

四、浮点直接比较是否相切

❌if (overlapArea(a, b) == 0.0)判断不相交,浮点误差会让理论上的 0 变成极小正数或负数。

✅ 用容差:if (overlapArea(a, b) <= 1e-9);容差大小按坐标量级选取,不要照搬固定值。

五、把公式用在旋转矩形上

❌ 对旋转 45 度的矩形仍用区间交公式,重叠面积被高估。

✅ 轴对齐才能用区间交;旋转矩形用分离轴定理判交、用凸多边形裁剪求面积,或直接使用几何库。

六、多个矩形面积直接相加

❌ 把三个以上矩形的面积相加再减去两两重叠,重复计算了三重重叠区域。

✅ 两个矩形用容斥;多个矩形用扫描线加线段树,或者用网格离散化(坐标范围小时)。

七、忽略「包含」情形

❌ 额外写分支判断谁包含谁,分支写错反而漏算。

✅ 区间交公式本身就能处理包含,取小取大后自然得到内层边界,不需要特判。

八、坐标类型与输出格式不匹配

❌ 整数版面积用%d输出long long,在部分平台上输出错乱。

✅ 用std::cout输出,或者用%lld(并注意平台差异),更好的做法是统一用流式输出。

总结

矩形重叠面积的核心就是一句「右边界取小、左边界取大,再钳制到非负」,剩下的工作全在类型与边界上:坐标先归一化,宽高先判正,面积用更宽的类型,浮点比较留容差。把这四点做到,公式本身几乎不会出错。