扫描线

​扫描线把问题拆成按某个坐标排序的事件，并用数据结构维护相邻事件之间的状态。使用扫描线前必须明确：

• 哪些位置会改变状态；
• 同一位置的多个事件如何成批处理；
• 数据结构中的顺序在扫描过程中为何仍然有效；
• 端点接触、重合和退化对象是否计入答案。

轴对齐矩形面积并

​给出 $n$ 个边平行于坐标轴的矩形。沿 $x$ 轴扫描时，每个非退化矩形产生左边加入、右边删除两个事件，维护扫描线上被覆盖的 $y$ 区间总长度。

​将所有 $y$ 端点离散化后，可以使用线段树维护区间覆盖次数和覆盖总长度。设上一个事件横坐标为 $x_{pre}$、当前覆盖长度为 $L$，到达新的横坐标 $x$ 时先累加

$$L(x-x_{pre})$$

​再统一处理该横坐标的所有加入、删除事件。同一横坐标必须分组，否则事件的任意先后容易污染状态语义。区间通常按半开形式 $[y_l,y_r)$ 维护；零宽或零高矩形对面积没有贡献。时间复杂度为 $O(n\log n)$。

判断线段集中是否存在交点

​朴素做法需要 $O(n^2)$。扫描线算法从左向右处理线段端点，并维护所有活动线段在当前扫描位置的纵向次序。必须先约定交点语义：下文的通用版本将线段视为闭集，端点接触和共线重合也算相交。

一般位置下的简化算法

​先假设所有线段均非竖直、端点横坐标互不相同，并且不存在共端点、端点落在其它线段上、共线重合或三线共点等退化情况。事件只有左、右端点：

• 遇到左端点时插入该线段，并检查它与活动集合中前驱、后继是否相交；
• 遇到右端点时，记录该线段原来的前驱、后继，删除后检查这两个新相邻的线段是否相交。

​活动集合按线段在当前横坐标处的 $y$ 值排序。虽然比较式依赖扫描横坐标，但在这个“只判断是否存在并在发现后立即返回”的算法中，可以证明它在返回前不会改变已有元素的相对次序：取横坐标最小的交点，在该交点左侧足够近的位置，两条相交线段必然相邻；否则夹在它们之间的线段会更早相交或经过同一个交点。它们成为相邻项时，只可能刚插入了其中一条线段，或刚删除了原本夹在中间的线段，因此已经进行过邻接检查。在发现第一个交点之前，任意两条活动线段的真实纵向次序都没有交换。

​因此，依赖当前横坐标的 set 比较器不是无条件可用：必须保证上面的不变量。比较器还必须形成严格弱序；相同 $y$ 时应按事件一侧的斜率和唯一编号继续区分，不能直接使用可能破坏传递性的 eps 判等。整数坐标可以通过有理数交叉相乘进行精确比较，并使用足够宽的中间类型。

​在上述一般位置假设下，每条线段至多插入、删除一次，每次只检查常数个相邻项，时间复杂度为 $O(n\log n)$。如果需要枚举全部 $K$ 个交点，则纵向次序确实会在交点处改变，必须将交点也加入事件；Bentley--Ottmann 一类算法的复杂度是输出敏感的 $O((n+K)\log n)$，不能继续沿用只含端点的 set。

同横坐标与退化情况

​若要支持任意闭线段，不能只给同一横坐标的事件规定一个简单的全局先后顺序，而应成批处理。所有在该横坐标开始、结束或退化为竖线的线段在该位置都有效；必须先完成共端点、端点在线段上等接触检查，再按扫描线左侧的次序删除结束线段，并按右侧的次序插入开始线段。若只把严格内点相交计入答案，则事件批处理和线段相交谓词都要相应排除端点接触。

​竖线段没有单一的 $y(x)$，不能作为普通元素插入上述活动集合。对 $x=x_0$、纵坐标范围为 $[y_l,y_r]$ 的竖线段，应在 $x_0$ 的事件批次内查询所有当前有效非竖线段中是否存在 $y(x_0)\in [y_l,y_r]$ 的线段；这里“当前有效”同时包括在 $x_0$ 结束和开始的线段。判断存在性时，找到第一个不低于 $y_l$ 的元素并验证其不高于 $y_r$ 即可。同一 $x_0$ 上的多条竖线段还要将 $y$ 区间排序，检测端点接触或区间重叠；零长度线段则按 $[y_l,y_r]$ 退化为一点的同批查询处理。

​共线重合、零长度线段、一个端点落在另一条线段内部等情况必须使用完整的方向测试和包围盒判断，不能只检查两个严格叉积异号。事件应携带线段唯一编号，删除时应定位这条具体线段；仅按当前 $y$ 做一次等价键查找，可能找到错误元素。支持这些退化情况的实现仍可做到 $O(n\log n)$ 的存在性判定，但需要上述批事件、区间查询和严格的数据结构契约，不能由简化版直接推出。

三角形面积并

​设输入为 $n$ 个非退化闭三角形，共有 $3n$ 条边。令 $K$ 为相交边对数；多条边经过同一点时仍按边对计数，共线重合的一对边也计入。于是 $K=O(n^2)$，且最坏可以达到 $\mathrm{\Theta }(n^2)$。因此，三角形面积并不能无条件套用只有线性事件数的 $O(n\log n)$ 扫描线。

法一：按横坐标分条积分

​事件横坐标至少包括所有三角形顶点、所有非重合边交点，以及共线重合段端点的横坐标。将不同事件横坐标排序后，在两个相邻事件 $x_j,x_{j+1}$ 之间，没有边开始、结束或交换纵向次序。每个三角形与竖截线的交集为空或一个区间，这些区间端点都是 $x$ 的一次函数；覆盖区间并的组合保持不变，因此总覆盖长度 $L(x)$ 也是一次函数。该竖条面积可以用梯形公式精确计算：

$${\displaystyle \frac{x_{j+1}-x_j}{2}}(L(x_j^{+})+L(x_{j+1}^{-}))$$

​这里必须使用开竖条内活动边给出的单侧极限，并维护竖截区间的并，而不只是给边排序。同一横坐标的顶点和交点应统一处理；竖直边只位于事件位置，本身没有正宽度。共端点、多边共点、相切和共线重合边还需要统一的去重与覆盖计数规则。

​一个容易实现但较慢的版本，可以在每个竖条中点求出所有三角形的截线区间，排序合并，并用同一组边函数计算竖条两端的覆盖长度。共有 $O(n+K)$ 个竖条时，这种实现的复杂度为 $O((n+K)n\log n)$，最坏可达 $O(n^3\log n)$。若要达到 $O((n+K)\log n)$ 一类的输出敏感复杂度，还需要输出敏感地发现边交点，并动态维护活动边排列、覆盖计数以及 $L(x)$ 的一次函数系数；若预先枚举所有边对，前处理本身已经是 $O(n^2)$。

法二：构造并集轮廓

​三角形并是一个多边形区域，但它可能包含多个不连通分量和孔洞，并且可能出现共线重合边。完整的轮廓法至少需要：

1. 将所有非退化三角形统一为逆时针方向；
2. 求出所有边交点，共线重合时还要加入重合段端点；
3. 按交点参数将每条输入边切成原子子线段；
4. 判断每条原子子线段两侧是否分别属于并集内部和外部，只保留分隔内外的线段，并将其定向为并集内部位于左侧；
5. 为重合边设置唯一归属规则，删除内部边和重复边；
6. 将暴露的有向子线段连接成若干闭环，并累加

$${\displaystyle \frac{1}{2}}\mathrm{cross}(p_i,p_{i+1})$$

​在标准右手直角坐标系中，若所有边都定向为并集内部位于左侧，则外轮廓为逆时针、孔洞轮廓为顺时针，因此有向面积会自动扣除孔洞。仅检查子线段中点是否位于其它三角形内部，只在无重合的一般位置下才可能足够；一般输入需要检查线段两侧的局部覆盖状态并去重。

​显式构造交点或完整轮廓时，复杂度必须包含 $K$。若朴素地为每条切分后的子线段再次遍历所有三角形，最坏还会达到三次量级；要得到输出敏感界，必须真正构造线段排列、平面图或等价的多边形布尔并结构，不能把“找到轮廓”本身省略。整数端点产生的交点通常是有理数，事件排序、切边和端点合并应使用精确谓词及可靠的有理数表示；直接用含糊的 eps 合并事件可能改变平面图拓扑。