Haskell中的Bentley-Ottmannalgorithm？
所以我一直在Haskell中编写一个计算几何库，因为我在Hackage上找不到一个，我认为这样做会很有趣。 然而，我在一个特定的algorithm上被困了近一个星期，我似乎无法进入一个很好的“类似于haskell”的表单。 该algorithm是用于在一组线段中find交点的Bentley-Ottmannalgorithm。 如果你熟悉algorithm，你可以跳到最后一段为我的求助:)
我select实现这个function的方式是把一个线段列表作为一个函数，并返回一个点列表，以及在那个点上相交的线段。 这让我们可以处理多个线段在相同点处相交的情况。
bentleyOttmann :: [Segment] -> [(Point, [Segment])]
该algorithm是一个扫描线algorithm。 我们想象一条线扫过飞机，在不同的地方做algorithm工作。 Bentley-Ottmannalgorithm中的事件点是：
- 线段的起始端点。
- 线段的结束端点。
- 一堆细分的交点。
请注意，事件点可以以多种方式与多个线段关联。 为了跟踪哪些段对应于哪个端点，我使用容器包中的映射。 这张地图的关键是点，这些值是分段的列表，标记是从那一点开始，在那一点结束还是在那一点相交。
扫描线决定点的顺序。 想象一下，一条垂直线扫过飞机，在事件点停下来做工。 事件点先按x值sorting，小点先处理。 一般来说，这是我们所需要的。 在退化情况下，事件点可能具有相同的x坐标。 我们还通过它们的y坐标来sorting，如果存在x坐标系，那么首先处理具有较小y坐标的事件点。
所以我使用的结构自然是一个优先队列。 我使用的是来自Hackage的堆包。
我们在每个活动点上所做的工作是什么？ 那么，首先我们检查哪些段与事件点相关联。 如果有多个，那就是一个交点。 我们可以将它添加到我们迄今为止发现的十字路口列表中。
棘手的部分来了。 当我们扫过飞机时，我们会跟踪一组相对于扫掠线相交点的线段 。 当我们处理事件点时，我们首先删除在该事件点结束的所有段。 然后，在该点相交的所有分段按顺序颠倒 。 最后，我们将从该事件点开始的段添加到有序集。 请注意，由于这些分段都在事件点相交，所以必须相对于稍前扰动的扫掠线进行sorting。
在每个事件点，我们必须添加任何新事件点，新发生的交点。 因为我们跟踪与扫掠线相交的线段的相对顺序，我们做两件事之一：
-
如果我们交换了两个分段或添加了一个新的分段，我们find最下面的（相对于扫掠线）修改的分段，最上面的修改分段，并testing它们与它们的直接未修改的邻居的交集。
-
如果我们没有交换或添加新的细分市场，那么我们至less会删除一个细分市场，从而使其前邻居现在相邻。 我们testing这些新邻居的交集。
这是Bentley-Ottmannalgorithm的关键，当我们横扫飞机时，我们只用邻居来testing新的候选片段。 这意味着当交叉口相对较less时，我们击败了天真的O（n ^ 2）algorithm。
我的问题（最后，我很抱歉，这是如此冗长）是这样的：我不知道如何实现这个顺序逻辑。 我无法使用Data.Set，因为在我们扫描时sorting发生了变化。 我试图实现我自己的数据结构来跟踪信息，但它是蹩脚的，越野车，可能是低效的，也是丑陋的！ 我讨厌丑陋的代码。
我知道Haskell是关于漂亮的代码。 我也相信，如果我不能以一种漂亮的方式实现一个algorithm，这意味着我并不真正了解它。 任何人都可以给我一个洞察力干净地实现这个algorithm？
编辑：我现在有一个“工作”的实施。 我打算使用通用input法，以及在同一点上交叉的多个线段和垂直线段。 这似乎与我所做的微不足道的testing有关。 段在重叠时不起作用。 我不知道如何处理这些。 我将不胜感激关于如何适应他们的意见。 目前，我的扫描线结构跟踪它们在同一个节点，但它只会使用其中的一个在相交testing，并可以给出不一致的结果。
我使用Data.Set作为我的事件队列，Data.Map进行查找，并且在他的书中使用了基于Okasaki的基于拉链的红黑树。 如果我的片段没有足够的上下文，我可以添加更多。
我将不胜感激关于重构实施的提示，所以它不那么难看。 我不知道它有多正确，这让我感到紧张。
代码可以在这里find
如果片段仅在交点处改变，并且仅在给定点处相交的片段的顺序。 这可以通过删除交叉段并再次插入来实现。
sorting函数是由y坐标，当y是相等时，由斜率。 相交的部分将以正确的顺序插入。 随着扫描的进行，扫描线段的交点的实际y坐标将改变。 不要紧，因为顺序将保持不变（直到我们交换，即删除并再次插入，相交段）。 实际的y坐标无需存储。 对于扫描线的任何给定位置，应该dynamic计算，因为我们插入或移除段。
所讨论的数据结构不应该被称为Set ，它是一个Map ，更确切地说，是一个Ordered Map。 find一个元素的邻居的操作在这里是必不可less的。
