在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

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

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

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

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

现在,你在评论中说:

这样做的原因是,段之前存储在"Set"中,以便删除重叠的段.这种表示保证只有一个段(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)

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

编辑:事后看来,我在博览会上有点过于局促,忘了提供参考.这根本不是一个新颖的概念,并且有许多现存的变化:

这些概念也扩展到更高的维度.沿着这些线的数据结构用于模拟和视频游戏中的渲染和碰撞检测,具有"最近邻"搜索的空间数据库,以及几何上通常不会想到的更抽象的应用,其中稀疏数据点可以被排序.多轴和一些"距离"的组合概念是有意义的.

奇怪的是,除了一个不完整且看似被遗弃的软件包之外,我一直无法在Hackage上找到任何这种数据结构的实现.