在2D位序列查找位的毗连区 [英] Finding Contiguous Areas of Bits in 2D Bit Array
问题描述
我有一点阵列重新presents二维地图的砖。这个图象提供了比特阵列中的比特的图形示例：
I have a bit array which represents a 2-dimensional "map" of "tiles". This image provides a graphical example of the bits in the bit array:
我需要确定多少比特的连续的区域的阵列中存在。在上面的例子中，有两个这样的连续的区，如这里所示：
I need to determine how many contiguous "areas" of bits exist in the array. In the example above, there are two such contiguous "areas", as illustrated here:
瓷砖必须直接位于N，S，E或瓦片W对被认为是连续的。对角感人的瓷砖不计。
Tiles must be located directly N, S, E or W of a tile to be considered "contiguous". Diagonally-touching tiles do not count.
由于这些位列可以成为比较大的（几MB大小），我特意用任何一种递归在我的算法避免。
Because these bit arrays can become relatively large (several MB in size), I have intentionally avoided using any sort of recursion in my algorithm.
伪code是如下：
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的建议）。
I re-wrote the solution to explore the edges only (per @hatchet 's suggestion).
这是非常简单的实现 - 而不再需要跟踪走访砖的问题。
This was very simple to implement - and eliminated the need to keep track of "visited tiles" completely.
根据三个简单的规则，我可以遍历边缘，跟踪最小/最大X'放大器; y值，并完全当我到达开始了。
Based on three simple rules, I can traverse the edges, track min/max x & y values, and complete when I've arrived at the start again.
下面是用三个规则我用了演示：
Here's the demo with the three rules I used:
推荐答案
一种方法周边的步行路程。 给定一个起点，沿着形状边缘的任何地方，记住这一点。
One approach would be a perimeter walk. Given a starting point anywhere along the edge of the shape, remember that point.
启动边框刚才这一点。
利用顺时针规则集走外线 - 如果用于获取到当前点的点高于，那么首先看的权利，然后放下，再左边找到的形状边界下一个点。这是一种像解决一个迷宫，你一直跟随在墙上，总是舍不得权的简单策略。
Walk the perimeter using a clockwise rule set - if the point used to get to the current point was above, then first look right, then down, then left to find the next point on the shape perimeter. This is kind of like the simple strategy of solving a maze where you continuously follow a wall and always bear to the right.
每当你访问一个新的边界点，展开边框如果新点是在它之外（即跟踪最小的和最大x和y。
Each time you visit a new perimeter point, expand the bounding box if the new point is outside it (i.e. keep track of the min and max x and y.
继续，直到出发点是达到了。
Continue until the starting point is reached.
缺点：如果形状有很多单个像素的'丝'，你会重新考虑他们的散步回来
Cons: if the shape has lots of single pixel 'filaments', you'll be revisiting them as the walk comes back.
优点：如果形状有内部空间占用的大片，你从来没有去拜访他们或者记录他们像你想，如果你是录音访问像素倾倒填充
Pros: if the shape has large expanses of internal occupied space, you never have to visit them or record them like you would if you were recording visited pixels in a flood fill.
所以，可以节省空间，但是在某些情况下，在时间的代价。
So, conserves space, but in some cases at the expense of time.
修改
正如通常的情况一样，这个问题是已知的，命名，并具有多种算法解决方案。你描述的问题是所谓的最小边界矩形。要解决这个问题的方法之一是使用<一个href="http://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/alg.html"相对=nofollow>轮廓跟踪。予上述的方法是在那个类，被称为<一href="http://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/moore.html"相对=nofollow>摩尔，邻居跟踪或<一href="http://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/ray.html"相对=nofollow>径向扫描。我已经包括了他们的链接中详细讨论，并指出一个问题，我没有抓到。有时你会重温的你已经走过了整个周边开始前点的。如果你的出发点是比如某处单个像素'丝'，你会再重新考虑你做之前，除非你考虑这种可能性，你会停下prematurely。该网站我联系有关如何解决该停止的问题举行了会谈。在该网站的其他页面也要讲两个算法：方跟踪，和西奥Pavlidis算法。有一点需要注意的是，这些考虑对角线为连续的，而你没有，但应该只是一些可以稍作修改处理的基本算法。
As is so often the case, this problem is known, named, and has multiple algorithmic solutions. The problem you described is called Minimum Bounding Rectangle. One way to solve this is using Contour Tracing. The method I described above is in that class, and is called Moore-Neighbor Tracing or Radial Sweep. The links I've included for them discuss them in detail and point out a problem I hadn't caught. Sometimes you'll revisit the start point before you have traversed the entire perimeter. If your start point is for instance somewhere along a single pixel 'filament', you will revisit it before you're done, and unless you consider this possibility, you'll stop prematurely. The website I linked to talks about ways to address this stopping problem. Other pages at that website also talk about two other algorithms: Square Tracing, and Theo Pavlidis's Algorithm. One thing to note is that these consider diagonals as contiguous, whereas you don't, but that should just something that can be handled with minor modifications to the basic algorithms.
这是另一种方法，你的问题是连接组件标签。因为虽然你的需求，这可能是更多的时间昂贵的解决方案比你所需要。
An alternative approach to your problem is Connected-component labeling. For your needs though, this may be a more time expensive solution than you require.
其它资源：
这篇关于在2D位序列查找位的毗连区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
