在文本正文中找到一个ASCII艺术图像，并具有一定的容错性 [英] Locate an ASCII art image inside a body of text with a certain toleration for error

问题描述

是否有任何算法可以找到以下ASCII艺术图像？

Are there any algorithms that would find the following ASCII-art image?

     +
     +
    +++
  +++++++
  ++   ++
 ++  +  ++
 ++ +++ ++
 ++  +  ++
  ++   ++
  +++++++
    +++

在以下正文中？

complete_file_here

              + +    +              ++           +       +++    +     +
 +  ++     +   + ++++    + +       +         +          +  +   +++     +++ +
     +            + +   ++      ++  ++    + ++       +     +      +  +   +
+   ++      +  ++       +          + +       ++        ++  +           +
 ++++++ + +    +   ++  +  +   +   +  ++      +         +                     +
  + +   +      +               +      ++     +  ++            +   +    + +
+++   + ++   +  +            +  +++       + +       ++                     +
  +++++  +      +                            +  + +            +   +  +
 +   +   +              +    +      +            +  +   +      +    +     +
 ++    +              +     +       ++   +          +       +           ++

我必须以黄色突出显示与完整形状相对应的ASCII艺术图像。见附图：

I must highlight the ASCII art image in yellow which corresponds to the complete shape. See the picture attached:

我必须搜索一个包含粗糙形状的文件，但不是完整的，一些 + 可以是失踪）。形状中缺少 + 的容差应该手动设置。

I have to search a file which contains the rough shape, but not completely, a number of + can be missing). The tolerance for a missing + in the shape should be set by hand.

现在，我有两个2D数组数据数组：[100] [100]和SlimeTorpedo数组：[13] [11]。

Now, I have two 2D arrays data array: [100][100] and the SlimeTorpedo array: [13][11].

如@kjartan所述进行检测的代码（3 -4 bullet）：

Code for how to make the detection as stated by @kjartan (3-4 bullet):

     int match = 0;
     for (int i = 0; i < 100; i++) {
         for (int j = 0; j < 100; j++) {
             //Compare DataArr[i][j] with SlimeTorpedoArr[i][j]
             //Look for "checked" position in the picture ("+"), 
             //which corresponds to a checked position in the 
             //slime torpedo array.
             //match++;
        }
    }

如何处理此问题的一般指导？

What would be general guidance for how to approach this problem?

推荐答案

假设您的第一个形状已知宽度和高度参数（以字符数表示）。让他们宽度和身高。

Let's say width and height parameters (in terms of number of characters) are known for your first shape. Let them be width and height.

• 将输入编码为2D数组（或+符号）。所以你有
  int [] [] inputBits = new int [height] [width]; 你应该正确填充
  。 （这是你的任务，老兄。）


• 然后在较大的形状上应用简单的搜索（假设它是
  编码到另一个2D数组中）。每次将枢轴区域向右移动
  （枢轴区域等于第一个
  形状的区域）并检查枢轴区域（2D阵列）是否具有
  等于的所有元素第一个形状。这是一个暴力算法=）

• Encode your input into a 2D array of bits (or + signs). So you have int[][] inputBits = new int[height][width]; and you should populate it correctly. (It's your task, dude.)
• Then apply a simple search on the larger shape (assuming it is encoded into another 2D array as well). Shift the pivot area to right by one each time (the pivot area is equivalent to the area of first shape) and check whether pivot area (2D array) has all its elements equal to the first shape. That's a brute-force algorithm =)

这篇关于在文本正文中找到一个ASCII艺术图像，并具有一定的容错性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！