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