data-structures - 用于在 Haskell 中遍历多边形段的数据结构？

Question

我有一个长度为 1 的水平/垂直段的无序列表，它们构建了一个或多个多边形。我现在需要找到每个多边形中所有连接角的列表。

例子:

[Horizontal (0,0), Vertical (2,0), Horizontal (1,0), Horizontal (2,2), Vertical (2,1)]

代表一条这样的线

2         X--X
          |
1         X
          |
0   X--X--X

    0  1  2

我会寻找角落 [(2,0), (2,2)]。

在命令式语言中，我可能会使用(双重)链接的数据结构并遍历它们。我无法在 Haskell 中为此提出优雅的表示。你会怎么做？

Answer 1

在我们去寻找角落之前，让我们退后一步。你想做什么？

I have an unordered list of horizontal/vertical segments of length 1, which build one or many polygons. I now need to find the list of all connected corners in each polygon.

“搜索”和“无序列表”并没有真正结合在一起，我相信你意识到了!即使在简单的查找中也是如此，但对于您正在做的事情来说更糟，这在概念上更接近于查找重复项，因为它需要将集合的元素相互关联，而不是独立检查每个元素。

所以，你肯定会想要一些有更多结构的东西。一种选择是在完整多边形方面更具有语义意义的表示，允许简单遍历不间断的周长，但我猜你没有可用的信息(例如，如果你试图创建这样的这里的结构)。

现在，您在评论中说:

The reason for this is, that the segments were stored in "Set"s before, in order to remove overlapping segments. This representation guarantees that there is only one segment (x,y)--(x+1,y).

这值得进一步思考。怎么样 Data.Set工作，为什么删除重复项比无序列表更好？最后一点有点像赠品，因为 Data.Set正是一个有序集合，因此通过为每个项目提供一个唯一排序的表示，您可以获得自动删除重复项和快速查找的综合好处。

如上所述，您的实际问题在概念上类似于查找重复项；您需要相邻的段，而不是寻找重叠的段。可以使用 Data.Set也在这里帮助你？

唉，不能。要了解原因，请考虑排序的工作原理。给定两个项目 X 和 Y，有三种可能的比较:X < Y、X == Y 或 X > Y。如果不同的相邻元素相差尽可能小，您可以安全地仅检查在排序集合。但是由于多种原因，这不能推广到线段，最简单的是最多四个不同的元素可以相邻，这不能用排序的序列来描述。

希望我的提示足够严厉，您现在想知道允许四个不同元素相邻的排序集合会是什么样子，以及它是否允许轻松搜索 Data.Set做。

后者的答案是肯定的，而第一个的答案是它会是一个更高维的搜索树。一个简单的二叉搜索树看起来像这样:

data Tree a = Leaf | Branch a (Tree a) (Tree a)

...确保在任何分支上，左半部分的所有叶值都小于右半部分的值。一个简单的二维搜索树看起来像这样:

data Tree a = Leaf | Branch a (Tree a) (Tree a) (Tree a) (Tree a)

...其中每个分支代表一个象限，通过在两个轴上独立比较进行排序。否则，它就像熟悉的一维搜索树一样工作，具有许多标准算法的直接翻译，并且给定特定的线段，您可以快速搜索任何相邻的线段。

编辑 : 事后看来，我在阐述中有点过于笼统，忘记提供引用。这根本不是一个新概念，并且有许多现存的变化:

我所描述的将被称为 point Quadtree并且是二叉搜索树的简单扩展，如 Data.Set .

相同的概念可以用区域而不是离散点来完成，查找结束于完全包含或排除的区域。这些是 tries 的类似扩展, 喜欢 Data.IntSet .

一个名为 R-trees 的变体类似于 B 树，并且对于某些目的具有有用的性能特征。

这些概念也可以扩展到更高的维度。沿着这些方向的数据结构用于模拟和视频游戏中的渲染和碰撞检测、具有“最近邻”搜索的空间数据库，以及您通常不会在几何上想到的更抽象的应用程序，其中可以对稀疏数据点进行排序多个轴和“距离”的一些组合概念是有意义的。

奇怪的是，我一直无法在 Hackage 上找到任何此类数据结构的实现，除了一个不完整且看似被遗弃的包。