1.线段求交

给定由平面上 n 条闭线段构成的一个集合 S，报告出 S 中各线段之间的所有交点。

我们所希望得到的算法，其运行时间不仅取决于输入中线段的数目，还取决于（实际的）交点数目。这样的算法，被称为“输出敏感的”算法（output-sensitive algorithm）⎯⎯也就是说，这种算法的运行时间对（实际）输出的大小很敏感。也可以称这样一个算法是“交点敏感的”（intersection-sensitive）⎯⎯因为，输出的大小就是由交点的数目决定的。

设需要对其进行求交的线段构成集合S : = {s1, s2, …, sn}。我们希望避免对相距很远的线段对进行求交。然而具体应该如何做呢？

首先排除一种简单的情况。如 图 2-5 所示，将一条线段在y-轴上的正交投影，定义为它的y-区间（y-interval）。任何两条线段，只要其y-区间没有重叠部分⎯⎯此时，也可以说，它们在y-方向上相距很远⎯⎯它们就一定不会相交。这样，只需要对那些y-区间相互有所重叠（即与同一条垂线相交）的线段对进行测试。

为找出这些线段对，可以想象着用一条直线l，从一个高于所有线段的位置起，自上而下地扫过整个平面。在这条假想的直线扫过平面的过程中，跟踪记录所有与之相交的线段⎯⎯后面将解释其详细实现⎯⎯以找出所需的所有线段对。

这类算法被称为平面扫描算法（plane sweep algorithm），其中使用到的直线 l 被称为扫描线（sweep line）。与当前扫描线相交的所有线段构成的集合，被称为扫描线的状态（status）。随着扫描线的向下推进，它的状态不断变化，不过，其变化并不是连续的。

只有在某些特定的位置，才需要对扫描线的状态进行更新。我们称这些位置为平面扫描算法的事件点（event point）。就本算法而言，这里的事件点就是各线段的端点。

只有在扫描线触及某个事件点的时候，算法才会进行实质的处理⎯⎯更新扫描线的状态，并进行一些相交测试。

具体地，若事件点为某条线段的上端点，则意味着这条线段将开始与扫描线相交，因此需要将该线段插入到状态结构（status structure）中。然后，需要将这条线段，和那些与当前扫描线相交的其它线段分别进行测试，确定是否相交。

若事件点为某条线段的下端点，则意味着这条线段将不再与扫描线相交，因此需要将该线段从状态结构中删去。按照这样的方式，只需要对那些可能与某条水平直线同时相交的线段对进行测试。

不幸的是，这还不够⎯⎯因为，在某些（特殊的）情况下，尽管实际的交点数目很少，却依然需要对平方量级的线段对进行测试。一个这样的简单例子就是，所有的线段都是垂直的，而且都与 x-坐标轴相交。因此，目前的这个算法还算不上是输出敏感的。问题在于，与同一扫描线相交的两条线段，在水平方向上仍然有可能相距很远。

在考虑到水平方向的临近性后，我们可以沿着扫描线，将与之相交的所有线段自左向右排序。这样，只有当其中的某两条线段沿水平方向相邻时，才需要对其进行测试。

这就意味着，每引入一条线段，只需要将其与另外的两条线段（具体地讲，就是与新线段上端点左、右紧邻的那两条线段）进行测试。此后，当扫描线向下推进到某个新的位置时，与某条线段紧邻的邻居有可能会发生变化，此时，需要将它与新的邻居进行测试。在算法的状态结构中，这一新策略应该有所反映⎯⎯现在，状态结构不仅要记录与当前扫描线相交的所有线段，而且还要对这些线段排序。为适应新的要求，状态结构不仅要在线段的端点处进行更新，在各交点处，也要做更新⎯⎯因为在这些位置，（与扫描线）相交的各线段（中有至少两条）的次序必然会有所变化（如 图 2-7 所示）。

在这种情况下，需要找出位置发生变化的那两条线段，然后将它们与各自的新邻居进行测试。这样，就出现了新的一类事件点。

在将这些构思落实为高效的算法之前，我们需要确定，这种方法的确是对的。在需要进行测试的线段对减少之后，是否还能够将所有的交点都找出来呢？

换而言之，对于任何两条相交的线段 si和 sj，是否总存在某个位置，当扫描线 l 抵达该位置时，si和 sj沿着 l 是紧邻的？

我们还是先忽略掉一些“棘手”的情况⎯⎯我们假设：没有水平线段；任何两条线段最多相交于一点（也就是说，任何两条线段都不会有局部的相互重叠）；任何三条线段不会相交于同一点。至于某条线段的端点落在另一条线段上的情况，等到扫描线触及相应的端点时，这类交点也不难被检测出来。

这样，唯一剩下的问题就是：线段之间在内部的每一交点，是否都能被检测出来？

证明：

如 图 2-8 所示，令l为比p略高的一条水平线。只要l与p相距足够近，则沿着l，si和sj必然是紧邻的（更准确地说，没有任何事件点落在我们所取的l上，而且也没有任何事件点夹在l与通过p的水平线之间）。

总而言之，必然存在某个位置，当扫描线到达这个位置时，si 和 sj是紧邻的。因此，必然存在某个事件点 q，在 q 的位置，si 和 sj 开始变为紧邻的，从而接受相交测试。

这样，就确定了算法是正确的⎯⎯至少，在暂不考虑此前所提及的那些手的情况时，它是正确的。现在，可以进一步完善我们的平面扫描算法。让我们对整个算法做一扼要重述。假想有一条水平线 l 自上而下扫过整个平面。在某些事件点，扫描线会停留片刻；就目前的算法而言，事件点既包括（事先就可以确定的）各线段端点，也包括（在算法运行过程中逐步发现的）交点。在扫描线移动的过程中，要维护一个有序序列，该序列由所有与当前扫描线相交的线段组成。每遇到一个事件点，扫描线都会停留片刻。此时，上述线段序列会有所变化，因此，必须通过一些动作，对状态结构进行更新，并检测出新的交点⎯⎯具体的处置方法，取决于事件点的类型。

若事件点对应于某条线段的上端点，就意味着将有一条新的线段开始与扫描线相交（如 图 2-9所示）。新引入的这条线段必须经过测试，以判断它是否与沿扫描线与之紧邻的另外两条线段相交。

只有位于当前扫描线下方的那些交点，才需要加以考虑；至于高于当前扫描线的那些交点，在此之前必然已经被检测出来了。例如，若沿着扫描线，线段 si和 sk 原本是紧邻的，而（在某个时刻）第三条线段 sj的上端点出现在它们之间，则此时就必须分别将 sj与 si和 sk进行测试。在检测出来的（最多两个）交点中，只要位于当前扫描线的下方，就是一个新的事件点。在处理完该上端点之后，将继续考虑下一个事件点。

若事件点对应于某个交点，则如 图 2-10 所示，有关的两条相交线段就会交换其（沿扫描线的）次序。它们各自可能（最多）有一条新的紧邻线段，因此，必须分别将它们与其各自的新邻居进行测试，以找出可能的交点。

与上面同理，我们只对位于当前扫描线下方的交点感兴趣。假设在扫描线触及 sk和 sl 的交点那一时刻，有四条线段 sj、sk、sl 和 sm依次出现在扫描线上。此后，sk 和 sl 将交换次序，于是需要分别对 sl 和 sj、sk和 sm进行测试，以找出它们可能位于扫描线下方的交点。

当然，若果真找到了这样的交点，它们也应该属于算法中的事件点。然而值得注意的是，这些事件有可能在此前已经被发现了⎯⎯比如，有可能某两条线段在此前的一段时间内曾经是紧邻的，后来一度不再紧邻，最终又再次变成是相互紧邻的。

若事件点对应于某条线段的下端点，则它此前的（一左一右）两个邻居现在就会变成是相互紧邻的，因此需要对它们进行相交测试。若它们果真相交，且交点位于当前扫描线的下方，则该交点也将成为一个事件点（同样地，这个事件点也可能在早先已经被发现过）。如 图 2-11 所示，假设（在某一时刻）沿着扫描线，有依次相邻的三条线段sk、sl和sm，扫描线继续前移后遇到了sl的下端点。于是，sk和sm将变成是相互紧邻的，因此我们要对它们进行相交测试。

在扫描完整个平面之后（更准确地讲，在处理完所有事件点之后），就确定了所有的交点。

正确性证明：

之所以能够保证这一点，是由于在平面扫描过程中，如下不变性始终成立：（在任何时刻，）处于扫描线上方的所有交点都已经被正确地检测出来了。

实现层面：

在对该算法做了上述简要概述之后，现在需要进行更为详细的讨论。而且，我们也可以顾及到可能出现的各种退化情况。

我们从算法所使用到的数据结构开始介绍。

首先，需要一种数据结构⎯⎯所谓的事件队列（event queue）⎯⎯来存放（当前已被检测出来，但尚未发生的）事件。这个事件队列记作Q。我们还需要用到一种操作⎯⎯把即将发生的下一事件从Q中删除掉，并将它返回（给主程序），以便对它进行处理。这个事件，就是位于扫描线下方、位置最高的那个事件。倘若有两个事件点的y-坐标相同，则约定返回x-坐标更小的事件点。也就是说，位于同一条水平线上的事件点，将按照从左到右的次序接受处理。按照这一约定，若是一条水平线段，则应该将其左（右）端点视为上（下）端点。于是，对于水平线段，扫描线将首先触及它的左端点，然后再触及右端点；

该事件队列必须支持插入操作⎯⎯因为在算法的运行过程中，可能会出现新的事件。请注意，不同事件点的位置可能重合。例如，两条不同的线段，其上端点可能重合。显然，将它们做为同一事件点来处理，会更加自然一些。因此，在进行插入操作的时候，必须检查待插入的事件是否已经出现在 Q 中了。

我们这样来实现事件队列。首先，要在各事件点之间定义一个次序≺，各事件点将按照这个次序接受处理。对于任何两个事件点 p 和 q，定义“p ≺ q 当且仅当 py > qy，或者 py = qy且 px < qx”。所有的事件点将按照由≺确定的次序，组织为一棵平衡二分查找树（balanced binary search tree）。于 Q 中的每一个事件点 p，我们还同时记录下起始于 p 的（也就是以 p 为其上端点的）那条线段。

这两种操作⎯⎯取出下一事件和插入新的事件⎯⎯每次各需要 O(logm)时间，其中的 m 为 Q 中事件的数目。（这里并没有使用堆来实现事件队列，因为还需要测试某个给定的事件是否已经存在于 Q 之中。）

其次，还需要维护算法的状态。所谓状态，也就是与当前扫描线相交的所有线段构成的有序序列。借助一个状态结构（status structure），可以访问某一给定线段s的（左、右）邻居⎯⎯这样，在插入s之后，就可以立即进行相应的相交测试。这个状态结构记作T。它必须是动态的⎯⎯一旦有某条线段开始（或不再）与扫描线相交，就应将它插入到状态结构中（或从状态结构中删去）。在任一时刻，状态结构中的所有线段之间具有一个定义明确的次序，因此可以使用一棵平衡二分查找树来实现状态结构（图 2-13）。

算法 FINDINTERSECTIONS(S) 
输入：平面线段集 S 
输出：S 中各线段之间的所有交点（以及穿过各交点的线段的信息）
初始化一个空的事件队列 Q
将所有线段的（上、下）端点插入 Q 中；对于上端点，还要记录其对应的线段
初始化一个空的状态结构 T
while (Q 非空)
{
	找出 Q 中的下一事件点 p，将其出事件队列
	HANDLEEVENTPOINT(p)
} 

这里额外说明下：

1.扫描方式会影响线段起点，终点的定义。从y轴自上向下的扫描方式下，规定线段两个端点a,b比较，若(a.y>b.y) || (a.y=b.y && a.x<b.x)时a为起点，否则b为起点。

2.检测到交点时，构造交点事件时，需记录交点关联到的线段1，线段2。记录时需要以交点之上扫描线与两个线段的交点的x坐标进行排序。线段1记录的是x坐标较小的，线段2记录的是x坐标较大的。

3.状态集合的维护。只在遇到线段起点类型的事件点时，才需向状态结构插入关联线段。每次向有序平衡容器插入新元素，删除元素时，可能引发内部元素之前调整，而调整需要进行元素比较。这就需要在容器实例层面定义自定义比较器，在每次操作层面提前设置比较器以来的数据，这里是扫描线y位置。因为比较器比较两个线段时，需基于此位置计算扫描线和线段交点。再依据交点x坐标作为比较依据。

4.状态集合中相邻两个线段交换位置。在有序平衡容器中，一种方式是先从容器移除两个线段，再分别插入。向前面说的，插入，删除前我们需要设置比较器需要的扫描线位置。可以将扫描线y位置设置为交点y坐标。同时，比较器的实现中，两条直线和指定y位置的扫描线交点x坐标相同时，我们继续取两条线段终点中y坐标较大者作为新的临时扫描位置，重新计算两个交点，以此交点x坐标来决定线段顺序，即可实现交点处交换效果。

前面已经介绍了不同事件的处理方法：若是线段的端点，则需要在状态结构T中插入或删除线段；若是交点，则需要交换（对应的）两条线段的次序。无论何种情况，在事件发生后，对每一对新近成为邻居的线段, 都要进行相交测试。在退化情况下⎯⎯即某个事件点涉及到多条线段时⎯⎯具体的实现将更为微妙。下面的子程序，将描述正确处理各类事件点的方法（如 图 2-15 所示）。

实现参考代码：

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
};

struct Segment {
    Point p1, p2;
    Segment(Point p1, Point p2) : p1(p1), p2(p2) {}
    // 线段的起点，终点
    // p1.y > p2.y || (p1.y == p2.y && p1.x < p2.x)时p1为起点，否则，p2为起点
};

// Event
struct Event {
    Point p;
    enum Type { START, END, INTERSECTION } type;
    Segment *seg1, *seg2;
    Event(Point p, Type type, Segment *seg1 = nullptr, Segment *seg2 = nullptr)
        : p(p), type(type), seg1(seg1), seg2(seg2) {}
    // 最小的Event，越被最先扫描处理
    // 自定义操作符<
    // 当pa.y > pb.y || (pa.y == pb.y && pa.x < pb.x)时，可认为pa小于pb
};


struct CompareSegments {
    double yPos;
    bool operator()(const Segment *s1, const Segment *s2) const {
        // 基于y位置，分别计算此位置扫描线与s1,s2的交点。
        // 依据交点x坐标决定次序。
        // 特别的，交点x坐标一致的两个线段。
        // 选取线段1，线段2终点中y坐标较大者，计算扫描线位于此位置分别与线段1，线段2交点。用此交点x坐标决定次序。
    }
};

std::vector<Point> findIntersections(const std::vector<Segment> &segments) {
	// 最小堆。用于存储待处理事件集合
    minheap eventQueue;
    // 状态集合
    status sweepLine(比较器对象指针);
    std::vector<Point> intersections;
    // 构建初始事件队列。此时每个事件关联到一个线段
    for (const auto &seg : segments) {
        eventQueue.push(Event(seg.p1, Event::START, const_cast<Segment *>(&seg)));
        eventQueue.push(Event(seg.p2, Event::END, const_cast<Segment *>(&seg)));
    }

    while (!eventQueue.empty()) {
        Event event = eventQueue.top();
        eventQueue.pop();
        // 处理起点事件
        if (event.type == Event::START) {
            // 需要将事件所在的线段，加入状态集合
            // 新线段加入到状态集合时，需要依次和状态集合现有线段进行有序分析后，确定最终插入位置
            // 向状态集合插入前，需设置比较器的比较依据
            sweepLine.insert(event.seg1);
            auto it = sweepLine.find(event.seg1);
            if (it != sweepLine.begin()) {
                auto prev = std::prev(it);
                checkIntersection(event.seg1, *prev, eventQueue, intersections);
            }
            if (std::next(it) != sweepLine.end()) {
                auto next = std::next(it);
                checkIntersection(event.seg1, *next, eventQueue, intersections);
            }
        } else if (event.type == Event::END) {
            auto it = sweepLine.find(event.seg1);
            if (it != sweepLine.begin() && std::next(it) != sweepLine.end()) {
                auto prev = std::prev(it);
                auto next = std::next(it);
                checkIntersection(*prev, *next, eventQueue, intersections);
            }
            // 从平衡容器移除元素也可能引发元素位置调整。所以，也应用调整前设置比较器的y值。
            sweepLine.erase(it);
        } else if (event.type == Event::INTERSECTION) {
            intersections.push_back(event.p);
            auto it1 = sweepLine.find(event.seg1);
            auto it2 = sweepLine.find(event.seg2);
          	// 严格的一致性约束容器是不允许直接改变元素key的。
          	// 这里的而交换可以通过先分别移除，在分别插入实现。
          	// 同样的，操作前应先设置好比较器以来的y值。直接设置为交点y值即可。
            std::swap(*it1, *it2);
            if (it1 != sweepLine.begin()) {
                auto prev = std::prev(it1);
                checkIntersection(*prev, event.seg1, eventQueue, intersections);
            }
            if (std::next(it2) != sweepLine.end()) {
                auto next = std::next(it2);
                checkIntersection(event.seg2, *next, eventQueue, intersections);
            }
        }
    }

    return intersections;
}


void checkIntersection(Segment *s1, Segment *s2, std::priority_queue<Event, std::vector<Event>, std::greater<Event>> &eventQueue, std::vector<Point> &intersections) {
  	// 线段相交检测
    Point p = findIntersection(s1, s2);
    // 交点被发现时，需要将其插入事件队列
    // 设置交点事件时，需设置交点关联的线段1，线段2。
    // 若交点位于当前扫描线位置之下，则应取线段1，线段2起点y坐标较小者，计算扫描线位于此位置和两个线段交点
    // 依据交点x坐标小者作为线段1，另一个作为线段2
    // 若交点位于当前扫描线之上，无需处理
}

// 相交检测
Point findIntersection(Segment *s1, Segment *s2) {
    略
}

正确性证明：

算法 FINDINTERSECTIONS 能够正确地计算出所有的交点，并能同时给出穿过各交点的线段。

任取一个交点 p，假定所有优先级更高的交点 q 已经被正确地计算出来了。令集合 U§由所有以 p 为上端点（对于水平线段，则是左端点）的线段组成；令集合 L§由所有以 p 为下端点（对于水平线段，则是右端点）的线段组成；令集合 C§由所有在其内部包含 p 的线段组成。

首先，假设 p 是某条或某几条线段公共的端点。这种情况下，在算法的第一步，p 就已经出现在事件队列 Q 中了。来自 U§的线段都与 p 存放在一起，因此它们都可以被查找出来。在p 接受处理的时候，L§和 C§中的线段已经存储在 T 中，因此在 HANDLEEVENTPOINT 的第 2 行，这些线段也会被查找出来。总之，只要 p 是一条或多条线段的共同端点，则 p 以及与之相关的线段都可以被正确地查找出来。

接下来，假设p不是某条线段的端点。只需证明：或早或晚，p必将被插入到Q中。需要注意的是，相关的所有线段，都将p包含于内部。将这些线段，按照其围绕p的角度排序，任取其中相邻的两条线段si和sj。必然存在优先级高于p的某个事件点q，使得在（扫描线）越过q之后，si和sj开始变成是相互紧邻的。根据归纳假设，事件点q已经被正确地处理过了⎯⎯也就是说，p已经被检测出来，并存入到Q之中。

时间复杂度分析：

对于由平面上任意 n 条线段组成的集合 S，算法 FINDINTERSECTIONS 的运行时间都是 O(nlogn + Ilogn)，其中 I 为 S 中各线段之间的交点总数。

算法的第一步，就是将所有线段的端点组成（初始的）事件队列。既然我们使用了平衡二分查找树来实现事件队列，故这一步需要的时间为O(nlogn)。

对状态结构的初始化只需要常数时间。接下来，开始进行平面扫描，逐一处理各事件。为了处理某一事件，需要对事件队列Q进行（最多）三次操作：在FINDINTERSECTIONS的第 4 行，将该事件从Q中删除掉；还需要对FindNewEvent调用一到两次⎯⎯相应地，最多会有两个新事件加入到Q中。Q的每次删除或插入操作需要O(logn)时间。对状态结构T，也要进行一些操作⎯⎯插入、删除以及查找紧邻线段。每一次这类操作也只需 O(logn) 时间；而操作的总数线性正比于 m§ := card(L§)∪U§∪C§)⎯⎯也就是与该事件相关的线段总数。若令m为所有事件点p对应的m§之和，则该算法的运行时间就是O(mlogn)。显然，m = O(n+k)，其中 k 为输出的规模。无论如何，只要 m§ > 1，事件点 p 所涉及到的所有线段都会被报告出来，而任一线段所涉及到的事件点，无非就是线段的端点。

我们的目标是要证明m = O(n+I)，其中I是交点的总数。为证明这一点，我们将所有输入线段的集合看成是嵌入于平面空间的一幅平面图。

图 2-16 所示，该图的顶点就是各线段的端点以及各线段之间的交点，而其中的边则是联接于各顶点之间的线段（或线段的局部）。现考察某个事件点p。它必然是图中的一个顶点，因而m§不会超过该顶点的度数。这样一来，m就不会超过图中所有顶点的度数总和。其中，每条边为两个（而且正好两个）顶点（亦即其端点）分别贡献一度，因此，m不会超过 2ne，其中ne为图中边的总数。现在，要根据n和I来给出ne的上界（upper bound）。考虑其中顶点的总数nv，根据定义，nv ≤ 2n+I。另外，正如总所周知的，对于平面图而言，必有ne = O(nv)⎯⎯这样，该引理的结论就已经得证。

空间复杂度分析：

每条线段在树 T 中存储至多一份，故该结构只需要 O(n)空间。不过，Q 的规模可能会很大。每发现一个交点之后，都需要将它插入到事件队列 Q 中；每处理完一个交点事件之后，也要删除它。如果要等待很长的时间，交点事件才能处理完毕，那么 Q 的规模就可能会很大。当然，其规模不可能超过 O(n+I)。不过，要是占用空间的大小总是线性的，就更好了。

总结：

给定由平面上任意 n 条线段构成的一个集合 S。可以在 O(nlogn + Ilogn)时间内，使用 O(n)空间，报告出 S 中各线段之间的所有交点，以及与每个交点相关的所有线段。其中，I 为实际的交点总数。
。不过，Q 的规模可能会很大。每发现一个交点之后，都需要将它插入到事件队列 Q 中；每处理完一个交点事件之后，也要删除它。如果要等待很长的时间，交点事件才能处理完毕，那么 Q 的规模就可能会很大。当然，其规模不可能超过 O(n+I)。不过，要是占用空间的大小总是线性的，就更好了。

[外链图片转存中…(img-HD46mivt-1729120707039)]

总结：

给定由平面上任意 n 条线段构成的一个集合 S。可以在 O(nlogn + Ilogn)时间内，使用 O(n)空间，报告出 S 中各线段之间的所有交点，以及与每个交点相关的所有线段。其中，I 为实际的交点总数。