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

例9-3的解决方案基于图9-16和图9-17定义的EventPoint、EventQueue和LineState类。

例9-3：线段扫描算法Java实现

EventQueue最开始存储2*n个EventPoint对象，每个对象存储的是以这个点为起点的ILineSegment（上部线段）和为终点的IlineSegment（下部线段）。当线段扫描算法发现线段之间存在交点时，表示交点的EventPoint对象就会插入到EventQueue中，直到它在扫描线下方时。这样，所有的交点都能够被找到，而且不会存在重复的点。如果交点已经存在于EventQueue中，那么在队列中，相交的信息将会更新，而不是重复插入[1]。

在图9-14中，当表示线段S6低点的事件点被插入到优先队列中[2]，那么线段扫描算法会将S6作为下部线段存储，处理这条线段时，线段扫描算法会将S4作为相交线段存储。在一个更加复杂的例子中，当表示线段S2和S5交点的事件点插入到优先队列中时，优先队列不会存储额外的信息。一旦这个事件点被处理时，优先队列会把S6、S2和S5作为相交线段存储。

线段扫描算法的计算引擎包含在图9-17的LineState类中。LineState在从上到下扫描时，维护当前的扫描点。pointSorter这个比较器在笛卡儿平面从上至下，从优先队列中，返回EventPoint对象。线段扫描算法的工作实际上是在LineState的determineIntersecting方法中：遍历左边和右边之间的这些线段来寻找交点。这些类的详细信息可以在本书所附的代码库中找到。