Haskell 中的 Bentley-Ottmann 算法？

发布于 2024-11-17 01:19:02 字数 2020 浏览 1 评论 0原文

所以我一直在 Haskell 中编写一个计算几何库，因为我在 Hackage 上找不到一个，而且我认为无论如何这样做都会很有趣。然而，我在一个特定的算法上被困了近一周，我似乎无法进入一个很好的“类似哈斯克尔”的形式。该算法是 Bentley-Ottmann 算法，用于查找一组线段中的交点。如果你熟悉这个算法，你可以跳到最后一段来满足我的要求:)

我选择实现这个函数的方式是作为一个函数，它接受一个线段列表并返回一个点列表，而线在该点相交的线段。这让我们可以处理多个线段相交于同一点的情况。

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

该算法是扫线算法。我们想象一条线扫过平面，在各个偶数点进行算法工作。 Bentley-Ottmann 算法中的事件点是：

线段的起点。
线段的结束点。
一堆线段的交点。

请注意，一个事件点可以通过多种方式与多个线段相关联。为了跟踪哪些段对应于哪些端点，我使用容器包中的地图。该映射的键是点，值是线段列表，通过它们是否从该点开始、在该点结束或在该点相交来标记。

扫描线决定点的顺序。想象一条垂直线扫过平面，在事件点处停止以做功。事件点首先按其 x 值排序，首先处理较小的点。一般来说，这就是我们所需要的。在退化情况下，事件点可能具有相同的 x 坐标。我们还按 y 坐标排序，如果存在 x 坐标平局，则首先处理 y 坐标较小的事件点。

所以我使用的结构自然是优先级队列。我使用的来自 Hackage 的 heaps 包。

我们在每个事件点做什么工作？好吧，首先我们检查哪些段与事件点相关联。如果有多个，则为交点。我们可以将其添加到迄今为止找到的交叉点列表中。

棘手的部分来了。当我们扫描整个平面时，我们会跟踪一组线段，根据它们与扫描线相交的点进行排序。当我们处理一个事件点时，我们首先删除以该事件点结束的所有段。然后，在该点相交的所有线段都按顺序反转。最后，我们将从该事件点开始的段添加到有序集中。请注意，由于这些线段都在事件点相交，因此必须相对于前方稍微扰动的扫描线对它们进行排序。

在每个事件点，我们必须添加任何新的事件点、发生的新交叉点。因为我们跟踪与扫描线相交的线段的相对顺序，所以我们执行以下两件事之一：

如果我们交换两个线段或添加一个新线段，我们会找到最底部（相对于扫描线）的修改线段，最上面的修改线段，并测试它们与直接未修改的邻居的相交。
如果我们不交换或添加新的段，那么我们至少删除了一个段，从而使其以前的邻居现在相邻。我们测试它的这些新邻居是否相交。

这是 Bentley-Ottmann 算法的关键，当我们扫过平面时，我们只测试新的候选线段及其邻居。这意味着当交叉点相对较少时，我们击败了朴素的 O(n^2) 算法。

我的问题（最后，我很抱歉这太啰嗦了）是这样的：我不知道如何实现这个排序逻辑。我无法使用 Data.Set，因为当我们扫描时顺序会发生变化。我正在尝试实现我自己的数据结构来跟踪信息，但它很脏，有缺陷，可能效率低下，而且也很难看！我讨厌丑陋的代码。

我知道 Haskell 就是关于漂亮的代码。我还相信，如果我不能以漂亮的方式实现一个算法，这意味着我并没有真正理解它。谁能告诉我如何干净地实现这个算法？

编辑：我现在有一个“有效”的实现。我希望它能够处理通用输入，以及在同一点相交的多个线段和垂直线段。它似乎可以通过我所做的微不足道的测试来处理这些输入。当段重叠时，它不起作用。我还不知道如何处理这些。我希望能就如何容纳他们提供意见。目前，我的扫描线结构在同一节点中跟踪它们，但在相交测试中只会使用其中之一，并且可能会给出不一致的结果。

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

我希望得到关于重组实施的建议，这样它就不会那么丑陋了。我不知道它有多正确，这让我很紧张。

该代码可以在 hpaste 此处上找到

原文

So I've been writing a computational geometry library in Haskell because I couldn't find one on Hackage, and I figured it would be fun to do anyway. However, I've been stuck for nearly a week on one particular algorithm that I just can't seem to get into a nice 'haskell-like' form. That algorithm is the Bentley-Ottmann algorithm for finding the intersections in a set of line segments. If you are familiar with the algorithm, you can skip down to the last paragraph for my begging :)

The way I choose to implement this function is as a function that takes a list of line segments and returns a list of points, and the line segments that intersect at that point. This lets us deal with the case where multiple segments intersect at the same point.

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

The algorithm is a sweep-line algorithm. We imagine a line sweeping the plane, doing algorithmic work at various even points. The event points in the Bentley-Ottmann algorithm are:

The beginning end-point of a line segment.
The ending end-point of a line segment.
The intersection point of a bunch of segments.

Note that an event point can be associated with more than one line segment in more than one way. In order to keep track of which segments correspond to which end points, I use a map from the containers package. The keys of this map are points, and the values are lists of segments, labeled by whether they start at that point, end at that point, or intersect at that point.

The sweep-line determines the order of points. Imagine a vertical line sweeping the plane, stopping at event points in order to do work. Event points are ordered first by their x value, with smaller points being processed first. Generically, this is all we need. In degenerate cases, event points may have the same x-coordinate. We also order by their y coordinates, event points with smaller y coordinates are processed first if there is an x-coordinate tie.

So the structure I use, naturally, is a priority queue. The one I use is from the heaps package from Hackage.

What is the work that we do at each event point? Well, first we check which segments are associated to the event point. If there is more than one, it is an intersection point. We can add it to the list of intersections we have found so far.

Here comes the tricky part. While we are sweeping across the plane, we keep track of a set of segments, ordered with respect to the point where they intersect the sweep line. When we process an event point, we first remove all the segments that ended at that event point. Then, all the segments that intersected at that point are reversed in order. Finally, we add segments that begin at that event point to the ordered set. Note, that since these segments all intersect at the event point, they have to be ordered with respect to a sweep line that is slightly perturbed ahead.

At each event point, we must add any new event points, new intersections that occur. Because we keep track of the relative order of segments intersecting the sweep line, we do one of two things:

If we swapped two segments or added a new segment, we find the bottommost (with respect to the sweep line) modified segment, the topmost modified segment, and test them for intersections with their immediate non-modified neighbors.
If we did not swap or add new segments, then we at the very least removed a segment, thus making its former neighbors now adjacent. We test its these new neighbors for intersection.

This is the key to the Bentley-Ottmann algorithm, as we sweep across the plane, we only test new candidate segments with their neighbors. This means that we beat the naive O(n^2) algorithm when there are relatively few intersections.

My problem (finally, I'm sorry this is so long-winded) is this: I have no idea how to implement this ordering logic. I cannot use Data.Set because the ordering changes as we sweep. I am trying to implement my own data structure to keep track of the information, but it's grungy, buggy, probably inefficient, and also ugly! I hate ugly code.

I know Haskell is all about pretty code. I also believe that if I cannot implement an algorithm in a pretty way, it means I don't really understand it. Can anyone give me an insight into cleanly implementing this algorithm?

Edit: I have a 'working' implementation now. I intended it to work with generic input, as well as multiple segments intersecting at the same point, and vertical segments. It seems to work on those inputs with the paltry tests I did. It does not work when segments are overlapping. I do not know how to deal with those yet. I would appreciate input on how to accommodate them. Currently, my sweep line structure keeps track of them in the same node, but it will only use one of them in intersection tests, and can give inconsistent results.

I use Data.Set for my event queue, Data.Map for lookup, and an implementation of red-black trees with zippers that I based off of Okasaki's in his book. If my snippet is not enough context, I can add more.

I would appreciate tips on restructuring the implementation so it's... less ugly. I can't tell how correct it is and it makes me nervous.

The code can be found on hpaste here

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

无远思近则忧 2024-11-24 01:19:02

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

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

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