代码之家 › 专栏 › 技术社区 › Amichai

分割标签的双数组

language-agnostic algorithm

3

Amichai · 技术社区 · 16 年前

问题:

我有一个大型的双(2d)数组,填充了各种标签。双数组中的每个元素(单元格)都包含一组标签,并且双数组中的某些元素可能为空。我需要一个算法将双数组中的元素聚类成离散的段。段被定义为双数组中相邻的一组像素和段中所有这些像素的共同标签。(对角线邻接不算数,我也不聚集空单元格)。

|-------|-------|-------|
| Jane  | Joe   |       |
| Jack  | Jane  |       |
|-------|-------|-------|
| Jane  | Jane  |       |
|       | Joe   |       |
|-------|-------|-------|
|       | Jack  | Jane  |
|       | Joe   |       |
|-------|-------|-------|

在上述分布在九个元素上的标签排列中,最大的簇是占据左上四个单元格的__Jane_簇。

我认为:

我已经考虑了遍历双数组中每个单元格的每个标签,并进行测试,以查看正在检查的单元格标签组合是否可以与先前存在的段相关联。如果被检查的元素不能与先前存在的段关联,它将成为新段的第一个成员。如果标签/单元格组合可以与它关联的先前存在的段相关联。

当然,为了使这个方法合理化,我必须实现一个详细的哈希系统。我必须跟踪所有与先前存在的段相邻的单元格标签组合,这些组合在迭代通过双数组的递增索引的路径中。这种散列方法可以避免在每个先前存在的段中迭代每个像素以找到邻接。

为什么我不喜欢它:

同样,上述算法没有考虑到双数组中的一个元素可以与两个唯一的段相关联的情况,一个在水平方向,一个在垂直方向。为了正确地处理这些情况,我需要为这个特定的情况实现一个测试,然后实现一个方法,将被检查的元素与一个段相关联,然后将两个相邻的相同段连接起来。

总的来说,这种方法和它需要的复杂的散列系统感觉非常不雅。另外,我只关心在双数组中找到大的片段,我更关心这个算法的速度而不是分割的准确性,所以我在寻找更好的方法。我假设有一些随机方法可以做到这一点,我还没有想到。

有什么建议吗?

编辑:

我想要的输出是一个段列表,每个段都是一个标签和一个点列表。因此,在上面的示例中,我希望返回两个段:

Segment 1 - Jane: (1,3), (2,3), (1,2), (2,2)
Segment 2 - Joe: (2,3), (2,2), (2,1)

1 回复 | 直到 16 年前

1

2

Rex Kerr 16 年前

您基本上想要实现一个泛洪填充算法——将数组看作一组图像,每个不同的标签一个,其中标签是一种颜色,缺少标签是黑色的;然后您想要将它分割成该颜色的所有连接组件。

对所有标签重复以上操作,就完成了。

如果标签比较稀疏,最好不要实际为每个标签创建图像,并使用现有的泛洪填充例程。在这种情况下,通过创建数组的副本并在销毁现有标签的同时一次构建一个已连接的块来完成宽度优先填充。

我将一个条目称为“像素”,整个数组称为“图像”。

算法大致是这样的,

for each pixel in the image
  for each label in the pixel
    1. remove the label
    2. mark the current pixel
    3. for each marked pixel, look in every adjacent pixel for the label
    4. remove any labels found
    5. if labels are found, clear marks, and mark the newly label-removed pixels
    6. if anything is marked, go back to 3
    7. report the set of points where you removed labels

因为这是破坏性的,你不必担心回溯。(如果你不能销毁你的原稿,也不能复制,那么你就必须一路追踪你所做的事情,这是一件更麻烦的事情。)