32

问题

我有一个位数组，它代表“瓷砖”的二维“地图”。此图像提供了位数组中位的图形示例：

位数组示例

我需要确定数组中存在多少个连续的位“区域”。在上面的示例中，有两个这样的连续“区域”，如下所示：

毗邻地区

瓦片必须直接位于瓦片的 N、S、E 或 W 处才能被视为“连续”。对角接触的瓷砖不算在内。

到目前为止我得到了什么

因为这些位数组可能变得相对较大（大小为几 MB），所以我有意避免在我的算法中使用任何类型的递归。

伪代码如下：

LET S BE SOURCE DATA ARRAY
LET C BE ARRAY OF IDENTICAL LENGTH TO SOURCE DATA USED TO TRACK "CHECKED" BITS
FOREACH INDEX I IN S
    IF C[I] THEN 
        CONTINUE 
    ELSE
        SET C[I]
        IF S[I] THEN
            EXTRACT_AREA(S, C, I)

EXTRACT_AREA(S, C, I):
    LET T BE TARGET DATA ARRAY FOR STORING BITS OF THE AREA WE'RE EXTRACTING
    LET F BE STACK OF TILES TO SEARCH NEXT
    PUSH I UNTO F
    SET T[I]
    WHILE F IS NOT EMPTY
        LET X = POP FROM F
        IF C[X] THEN 
            CONTINUE
        ELSE
            SET C[X]
            IF S[X] THEN
                PUSH TILE NORTH OF X TO F
                PUSH TILE SOUTH OF X TO F
                PUSH TILE WEST OF X TO F
                PUSH TILE EAST OF X TO F
                SET T[X]
    RETURN T

我的算法动画

我不喜欢我的解决方案的地方

  • 只是为了运行，它需要两倍于它正在处理的位图数组的内存。
  • 在提取“区域”时，它使用位图数组的三倍内存。
  • “要检查的图块”堆栈中存在重复项 - 这看起来很难看，但不值得避免我现在拥有的方式。

我想看什么

  • 更好的内存配置文件
  • 更快地处理大面积

解决方案/跟进

我重新编写了仅探索边缘的解决方案（根据@hatchet 的建议）。

这实现起来非常简单——并且完全消除了跟踪“访问过的图块”的需要。

基于三个简单的规则，我可以遍历边缘，跟踪最小/最大 x 和 y 值，并在我再次到达起点时完成。

这是我使用的三个规则的演示：

解决方案

4

2 回答 2

11

一种方法是周边步行。给定沿形状边缘的任意位置的起点，记住该点。

仅从该点开始边界框。

使用顺时针规则集走周边 - 如果用于到达当前点的点在上方，则首先向右看，然后向下看，然后向左看以找到形状周边上的下一个点。这有点像解决迷宫的简单策略，在该迷宫中，您不断跟随墙壁并始终向右移动。

每次访问新的周界点时，如果新点在边界框之外，则展开边界框（即跟踪最小和最大 x 和 y。

继续直到到达起点。

缺点：如果形状有很多单像素“细丝”，你会在步行回来时重新审视它们。

优点：如果形状有大片的内部占用空间，您永远不必访问它们或记录它们，就像您在洪水填充中记录访问过的像素一样。

因此，可以节省空间，但在某些情况下会以牺牲时间为代价。

编辑

通常情况下，这个问题是已知的、命名的，并且有多种算法解决方案。您描述的问题称为最小边界矩形。解决此问题的一种方法是使用Contour Tracing。我上面描述的方法属于该类，称为Moore-Neighbor Tracing或Radial Sweep。我为他们提供的链接详细讨论了它们并指出了我没有发现的问题。有时你会重新回到之前的起点你已经穿越了整个周边。例如，如果您的起点是沿着单个像素“细丝”的某处，您将在完成之前重新访问它，除非您考虑这种可能性，否则您将过早停止。我链接到的网站讨论了解决这个停止问题的方法。该网站的其他页面还讨论了另外两种算法：Square Tracing 和 Theo Pavlidis 算法。需要注意的一件事是，这些认为对角线是连续的，而您却没有，但这应该只是可以通过对基本算法进行少量修改来处理的东西。

解决您的问题的另一种方法是Connected-component labeling。但是，对于您的需求，这可能是一个比您需要的更耗时的解决方案。

附加资源：

C++ 中的摩尔邻域轮廓跟踪算法

于 2013-07-31T19:48:05.917 回答
4

我曾经在一次采访中遇到过这样的问题。

您可以假设数组是一个图，而连接的节点是相邻的节点。我的算法将涉及向右移动 1 直到找到标记的节点。当您找到一个以 O(n) 运行并避免递归的广度优先搜索时。当 BFS 返回时，继续从您离开的地方搜索，并且如果该节点已被先前的 BFS 之一标记，您显然不需要搜索。我不确定你是否真的想返回找到的对象的数量，但是当你点击第一个标记的方块时，只需增加一个计数器就可以很容易地跟踪。

通常，当您执行洪水填充类型算法时，您会被放置在一个位置并被要求填充。由于这是找到所有已填充区域的一种方法，因此您希望对其进行优化，以避免重新检查以前 BFS 中已标记的节点，不幸的是，目前我想不出一种方法来做到这一点。

减少内存消耗的一种巧妙方法是存储 ashort[][]而不是布尔值。然后使用这个方案来避免制作整个第二个二维数组

未标记 = 0，已标记 = 1，已检查且未标记 = 3，已检查且已标记 = 3

这样，您可以通过其值检查条目的状态并避免创建第二个数组。

于 2013-07-31T19:12:42.437 回答