阅读 ‧ 电子书库

解决方案

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

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

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

广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元

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

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