Алгоритм для минимизации количества линий для рисования?

Question

В настоящее время я работаю над оптимизацией моего проекта, которому уже несколько лет. Цель состоит в том, чтобы нарисовать изображение после нажатия определенной комбинации клавиш. Оригинальная версия, которую я сделал несколько лет назад, вручную переместилась в каждый квадратный раздел, но я недавно оптимизировал ее, чтобы рисовать прямоугольники для последовательных квадратов, что делает ее намного быстрее.

Следующим шагом, который я хочу предпринять, является оптимизация способа, которым программа рисует данный макет, но я не знаю, с чего начать искать. Я надеюсь, что кто-то может указать мне в правильном направлении, так как я даже не могу думать о поисковом термине для этого.

В настоящее время программа имеет функцию под названием Draw, который принимает входной сигнал, как это:

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

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

Компоновка выше для этого изображения:

Жеребьевка этот макет и рисовать это сверху вниз, слева направо следующим образом:

Для завершения изображения требуется 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

Это расширено от ответа EpiGen, но я почувствовал, что ему нужно собственное сообщение, чтобы объяснить различия.

Это текущий статус того, что у меня есть, но он по-прежнему не на 100% оптимален во всех случаях (как показано ниже). Если есть какие-либо улучшения, не стесняйтесь их добавлять.

Таким образом, основной поток алгоритма выглядит следующим образом:

1. Получить горизонтальную длину от текущей точки
2. Получить вертикальную длину от текущей точки
3. Pick большой длины и использовать это направление

Однако он не просто дает длину, которую он видит.Вместо этого он выбирает максимальную длину, которая не пересекает линию с большей длиной. Вот шаги:

1. Проверить, если следующий пиксель является 1 (Переход вправо по горизонтали, по вертикали вниз по)
2. Если это так, то проверьте длину в противоположном направлении, начиная с этого индекса.
3. Если длина этой длины больше текущей, сохраните текущую длину и значение противоположной длины.
4. Как только символ, который не является 1, рассматривается, если максимальная длина в проверяемом направлении меньше максимальной длины в противоположном направлении, тогда верните длину в нашем направлении до этой точки.

Вот пример этой логики в действии. Серые линии представляют собой линии, которые уже были нарисованы, зеленая линия представляет проверяемую линию, а красная линия указывает границу.

Так как горизонтальная длиной красной линии является больше, чем текущая вертикальной длиной в этой точке, значения сохраняются в их текущем виде (вертикальная 1, горизонтальная 7). После того, как проверка вертикальной линии завершится и найдет длину 2, она увидит, что она пересекла линию длины 7. Так как менее эффективно разбить эту строку на меньшую, вместо этого она изменяет свою длину на 1, что и есть перед тем, как он пересек эту линию. Это делает окончательный вывод похожим на это с 16 сегментами, что является оптимальным, насколько я знаю.

Тем не менее, он терпит неудачу при определенных условиях; в частности нижний левый угол этого изображения.

Зеленая линия имеет длину 10, а строка останавливается на имеет длину 9. Так как эта строка не больше или равен его размер, он делит линию, которая оставляет один блок в сторону. Если бы эта проблема была исправлена, то это изображение было бы оптимальным, насколько мне известно. (Самый низкий, который я получил, - 44, текущая логика - 45).

Независимо от того, что это работает так хорошо, как мне это нужно. Если на следующий день появятся другие ответы с лучшими решениями, я посмотрю на них.

В качестве дополнительного, вот GIF из него работает для одного из самых крупных из них:

Answer 2

Вы должны сделать какой-то анализ первых в любом случае. Впоследствии я бы предложил передать «изображение» в обоих направлениях и сохранить более длинную строку (отметьте каждую ячейку более длинной строки как пройденную или «черную», чтобы вы не повторяли проверку).

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); 
}