Haskell中的Bentley-Ottmann算法？

Question

所以我一直在Haskell编写一个计算几何库,因为我在Hackage上找不到一个,而且我觉得无论如何都会很有趣.但是,我已经在一个特定的算法上被困了将近一个星期,我似乎无法进入一个很好的'类似haskell'的形式.该算法是用于在一组线段中找到交叉点的Bentley-Ottmann算法.如果您熟悉算法,可以跳到最后一段为我的求助:)

我选择实现此函数的方式是一个函数,它获取一个线段列表并返回一个点列表,以及在该点相交的线段.这让我们可以处理多个段在同一点相交的情况.

bentleyOttmann :: [Segment] -> [(Point, [Segment])]

该算法是扫描线算法.我们想象一条扫过飞机的线,在不同的点上进行算法工作.Bentley-Ottmann算法中的事件点是:

• 线段的起始端点.
• 线段的结束终点.
• 一堆段的交叉点.

请注意,事件点可以以多种方式与多个线段相关联.为了跟踪哪些段对应于哪些端点,我使用容器包中的映射.此贴图的关键点是点,值是段的列表,标记为它们是从该点开始,在该点结束还是在该点处相交.

扫描线确定点的顺序.想象一下垂直线扫过飞机,在事件点停下来做功.事件点首先按其x值排序,首先处理较小的点.一般来说,这就是我们所需要的.在退化情况下,事件点可以具有相同的x坐标.我们还按其y坐标排序,如果存在x坐标关系,则首先处理具有较小y坐标的事件点.

所以我自然使用的结构是一个优先级队列.我使用的是来自Hackage的堆包.

我们在每个活动点做的工作是什么？好吧,首先我们检查哪些段与事件点相关联.如果有多个,则为交叉点.我们可以将它添加到目前为止我们找到的交叉点列表中.

这是棘手的部分.当我们扫过飞机时,我们会跟踪一组段,这些段相对于它们与扫描线相交的点排序.当我们处理事件点时,我们首先删除在该事件点结束的所有段.然后,在该点交叉的所有段按顺序颠倒.最后,我们将从该事件点开始的段添加到有序集.注意,由于这些段都在事件点处相交,因此必须针对前方略微扰动的扫描线进行排序.

在每个事件点,我们必须添加任何新的事件点,发生的新交叉点.因为我们跟踪与扫描线相交的段的相对顺序,所以我们做以下两件事之一:

• 如果我们交换了两个段或添加了一个新段,我们找到最下面的(相对于扫描线)修改的段,最顶层的修改段,并测试它们与它们的直接非修改邻居的交叉点.

• 如果我们没有交换或添加新的段,那么我们至少会移除一个段,从而使其前邻居现在相邻.我们测试这些新邻居的交叉点.

这是Bentley-Ottmann算法的关键,当我们扫过飞机时,我们只测试与其邻居的新候选区段.这意味着当交叉点相对较少时,我们击败了天真的O(n ^ 2)算法.

我的问题(最后,我很抱歉这是如此啰嗦)是这样的:我不知道如何实现这个排序逻辑.我不能使用Data.Set,因为顺序随着扫描而改变.我正在尝试实现我自己的数据结构以跟踪信息,但它是蹩脚的,错误的,可能是低效的,也是丑陋的!我讨厌丑陋的代码.

我知道Haskell就是漂亮的代码.我也相信如果我不能以一种漂亮的方式实现算法,那就意味着我并不真正理解它.任何人都可以让我深入了解这个算法吗？

编辑:我现在有一个"工作"的实现.我打算使用通用输入,以及在同一点和垂直段相交的多个段.它似乎通过我做的微不足道的测试来处理这些输入.它并没有在段重叠的工作.我不知道如何处理这些问题.我希望得到关于如何容纳它们的意见.目前,我的扫描线结构在同一节点中跟踪它们,但它只会在相交测试中使用其中一个,并且可能会产生不一致的结果.

我使用Data.Set作为我的事件队列,使用Data.Map进行查找,以及使用拉链的红黑树的实现,我在他的书中使用了Okasaki的.如果我的代码段没有足够的上下文,我可以添加更多内容.

我很欣赏关于重组实施的提示,所以它不那么难看.我不知道它是多么正确,它让我感到紧张.

代码可以在hpaste上找到

Answer 1

如果线段仅在交点处发生变化，并且仅针对在给定点处相交的线段，则排序。这可以通过删除相交线段并再次插入它们来实现。

排序函数按y坐标排序，当ys 相等时，按斜率排序。然后相交的线段将以正确的顺序插入。随着扫描的进行，y扫描线段交点的实际坐标将发生变化。没关系，因为顺序将保持不变（直到我们交换，即删除并再次插入相交的线段）。y无论如何都不需要存储实际坐标。当我们插入或删除线段时，应该针对扫描线的任何给定位置动态计算它。

有问题的数据结构不应该被称为Set，它是一个Map，或者更准确地说，一个有序映射。查找给定元素的邻居的操作在这里至关重要。