首页 » 算法技术手册 » 算法技术手册全文在线阅读

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

关灯直达底部

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

图 9-16 EventPoint类 图 9-17 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方法中:遍历左边和右边之间的这些线段来寻找交点。这些类的详细信息可以在本书所附的代码库中找到。

[1]这就是LINESWEEP必须能够决定是否优先队列中包含一个特定的EventPoint对象的原因。 [2]事实上是最右边的端点,因为S6是水平的。