在大图中搜索简单图
我创建了由正方形组成的大人物。 我还有一些由正方形组成的简单图形。
如何在大图中找到我的简单图？
-- 谢谢。
I create big figure consisting of squares.
Also I have some simple figures consisting of squares too.
How can I find my simple figures in the big figure?
--
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
既然您说这些方块位于网格上，您可以尝试简单地用每个小数字在网格上循环，看看相应的方块是否相等。如果是这样，您就找到了一个简单图形的实例。
如果你想变得更奇特，你可以将简单的图形编码为不相交的路径，即第一个简单的图形可能是这样的路径：从头开始，向右移动。然后，对于大图形的每个方格，如果您可以完成路径并停留在大图形的方格上，那么您就找到了单个图形的实例。
Since you said the squares are located on a grid, you could try simply looping over the grid with each small figure, to see if the corresponding squares are equal. If so, you've found one instance of a simple figure.
If you want to get fancier, you could encode simple figures as non-intersecting paths, i.e. the first simple figure might be a path like: from start, move right. Then for each square of the big figure, if you can complete the path and stay on the big figure's squares, you have found an instance of a single figure.
假设大数字 B 的每一行都由压缩的位数组表示，并假设最大的小数字可以包含在 h×v 网格中。 （在您的示例图中，h=3，v=2。）使用 h*v 位（或更多位，例如 4*2、或 4*4、或 8*2 等，以获得方便的大小）为每个小图形s制作一个掩码M_s。在 B 上和下移动一个 h×v“窗口”，在每个 (x,y) 处形成一个值 M(x,y)，该值表示 B 中设置的且位于当前窗口中的位。 （这个值可以增量计算，即通过为窗口的每一行移入一位。）每当
M_s & M(x,y) == M_s，您发现了小数字 s 的出现。请注意，上述方法假设小数字中的空白单元格“不关心”，ie可以匹配 B 中的空白或非空白。如果此类单元格不< /em>“不关心”，那么除了之前使用的非空白图之外，每个小图形还需要补充空白图。该图针对 M(x,y) 的补集进行测试。可以将测试组合在一起并测试
M_s ^ M(x,y) == 0而不是M_s & M(x,y) == M_s，如果M(x,y)窗口与小图形大小相同。如果 B 非常大并且有点稀疏，那么移动小数字模式并直接针对 B 的单词进行测试可能会更快，而不是将 B 的位转换为值 M(x,y)；或预先计算移位小图案的数组。
如果小数字的数量很大，则对它们进行排序，使得如果小数字u包含在w中，则只要没有找到u，就可以跳过对w的测试。类似地，如果 u 和 v 都包含在 w 中，则每当未找到 u 或 v 时，您可以跳过对 w 的测试。然而，只有当第一段中概述的基本方法太慢时，才应该尝试像这样的优化和前一个优化。
Suppose each row of the big figure, B, is represented by a packed array of bits, and suppose the largest small figure can be contained within a h-by-v grid. (In your example figure, h=3, v=2.) Using h*v bits (or a few more, eg 4*2, or 4*4, or 8*2 etc., to get to a convenient size) make a mask M_s for each small figure s. Move an h-by-v "window" across and down B, at each (x,y) forming a value M(x,y) that represents the bits that are set in B and are in current window. (This value can be computed incrementally, ie by shifting one bit in for each row of the window.) Whenever
M_s & M(x,y) == M_s, you have found an occurrence of small figure s.Note, the method above supposes that blank cells in a small figure are "don't cares", ie can match either a blank or non-blank in B. If such cells are not "don't cares", then a complementary map of blanks is needed for each small figure, besides the map of non-blanks used before. This map tests against the complement of M(x,y). It is possible to combine the tests together and test for
M_s ^ M(x,y) == 0instead of forM_s & M(x,y) == M_s, if the M(x,y) window is the same size as the small figure.If B is extremely large and sort of sparse, it may be faster to shift the small-figure patterns and test them directly against words of B, instead of getting bits of B into a value M(x,y); or pre-compute arrays of shifted small patterns.
If the number of small figures is large, sort them such that if small figure u is contained in w, you can skip testing for w whenever u is not found. Similarly, if both u and v are contained in w, you can skip testing for w whenever either of u or v is not found. However, optimizations like this and the previous one should only be tried if the basic method outlined in first paragraph is too slow.