最小化绘制线条数量的算法？

Question

我目前正在优化我的一个已有几年历史的项目。目的是在按下特定的键组合后绘制图像。几年前我制作的原始版本手动移动到每个正方形部分，但我最近对其进行了优化，为连续的正方形绘制矩形，这使得它更快。

我想采取的下一步是优化程序绘制给定布局的方式，但我不知道从哪里开始寻找。我希望有人能为我指明正确的方向，因为我什至想不出搜索词。

目前该程序有一个名为 Draw 的函数，它接受这样的输入：

Invader =
(
00100000100
00010001000
00111111100
01101110110
11111111111
10111111101
10100000101
00011011000
)

Draw(Invader, 10) ; Where 10 is the size in pixels of each square

上面的布局适用于这张图片：

Draw 将采用该布局并按以下方式从上到下、从左到右绘制它：

一共需要18个独立的部分来完成这幅画。我正在寻找的是一些可以最小化这个数字的算法。例如，以下是只有 16 个部分的几种方法之一：

同样，当前方式与我刚刚为这张图片现场制作的方式之间的差异是 19（65 比 46）。

我应该从哪里开始？

也供参考，这里是当前的Draw函数：

Draw(Layout, BlockSize)
{
  Len := StrLen(Layout)                         ; Total amount of characters
  RowSize := StrLen(StrSplit(Layout, "`n")[1])  ; Size of a single row
  Index := 0

  While (Index < Len)
  {
    Length := 1
    Char := GetChar(Layout, Index)  ; Get next character in string

    if (Char == "1")
    {
      ; Get the number of consecutive 1s
      While (GetChar(Layout, Index + Length) == "1")
      {
        Length := Length + 1
      }

      ; Draw the rectangle
      FillRectangle(Length, BlockSize)
    }
    else if (Char == "0")
    {
      ; Get the number of consecutive 0s
      While (GetChar(Layout, Index + Length) == "0")
      {
        Length := Length + 1
      }

      ; Skip the entire length
      MouseMove, BlockSize * Length, 0, 0, R
    }
    else
    {
      ; End of line, reset position
      MouseMove, -(RowSize * BlockSize), BlockSize, 0, R
    }

    Index := Index + Length
  }
}

FillRectangle(Width, BlockSize)
{
  MouseGetPos, mX, mY
  mY2 := mY                     ; Same Y for straight line
  mX2 := mX + Width * BlockSize ; Add Width of rectangle times the block size to get final X position

  Loop %BlockSize%
  {
    ; Draw line
    MouseClickDrag, L, mX, mY, mX2, mY2

    ; Move to next line
    mY -= 1
    mY2 -= 1
  }

  ; Move mouse to next position
  MouseMove, 0, BlockSize - 1, 0, R
}

GetChar(String, Index)
{
  return SubStr(String, Index, 1)
}

Answer 1

无论哪种方式，您都应该先进行某种分析。之后我会建议通过 "image" 两种方式并保留较长的行（将较长行的每个单元格标记为已通过或 "black" 这样你就不会重复检查）。

void analyze(){
     var horSize = 0, verSize = 0;

     // run horizontally & vertically for each white cell
     while(!reached_boundary){
         ++horSize ;   
     }
     while(!reached_boundary){
         ++verSize ;   
     }
     someContainer.Add( (horSize > verSize) ? horSize:verSize);
}

Answer 2

这是从 EpiGen 的回答扩展而来的，但我觉得它需要自己的 post 来解释差异。

这是我目前的状态，但在所有情况下仍然不是 100% 最佳（如下所示）。如果有任何改进，请随时添加。

所以，算法的基本流程如下：

从当前点获取水平长度
从当前点获取垂直长度
选择更大的长度并使用那个方向

但是，它不只是给出它看到的长度。相反，它会选择不与长度更长的线相交的最大长度。以下是步骤：

检查下一个像素是否为 1（水平向右，垂直向下）
如果是，则检查从该索引开始的相反方向的长度。
如果该长度比当前长度长，则保存当前长度和相反的长度值。
一旦看到一个不是1的字符，如果被检查方向的最大长度小于相反方向的最大长度，那么return之前我们方向的长度观点。

下面是这个逻辑的一个例子。灰色线代表已经绘制的线，绿色线代表正在检查的线，红色线代表边界。

由于此时红线的水平长度大于当前的垂直长度，因此值以当前形式保存（垂直1，水平7）。在垂直线检查完成并发现长度为 2 后，它会发现它穿过了一条长度为 7 的线。由于将这条线拆分为更小的线效率较低，因此它会将其长度改回 1，这就是它的长度在它越过那条线之前。这使得最终输出看起来像这样，总共有 16 个段，据我所知这是最佳的。

但是，在某些情况下它会失败；特别是这张图片的左下角。

绿线的长度为 10，它停止的行的长度为 9。由于该行不大于或等于它的大小，它将留下一个块的线拆分为边。如果这个问题得到解决，那么据我所知，这张图片将是最佳的。（我得到的最低值是 44，当前逻辑得到 45）。

无论如何，这似乎已经达到了我需要的效果。如果第二天有更好的解决方案的其他答案，我会看看它们。

另外，这里有一个更大的 gif 运行：

最小化绘制线条数量的算法？

Algorithm for minimizing the amount of lines to draw?

algorithm

autohotkey