Ответ 1

Прежде всего, рассмотрим, что для общей матрицы вывод может состоять из более чем одного замкнутого цикла; например, границы матрицы

образуют три различные петли, один из которых помещен внутри другого.

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

data = [[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
        [ 0, 1, 1, 1, 1, 0, 0, 0, 0, 0 ],
        [ 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 ],
        [ 0, 1, 0, 0, 1, 0, 1, 1, 1, 0 ],
        [ 0, 1, 1, 1, 1, 0, 0, 1, 1, 0 ],
        [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]]

rows = len(data)
cols = len(data[0])

walls = [[2*(data[r][c] != data[r][c+1]) + (data[r][c] != data[r+1][c])
          for c in range(cols-1)]
         for r in range(rows-1)]

В приведенном выше примере я использую два бита: 0x01, чтобы отметить горизонтальные стены и 0x02, чтобы отметить вертикальные стены. Для данной ячейки (r, c) стенки представляют собой правую и нижнюю стенки ячейки.

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

Чтобы создать список границ, вам нужно просто начать с любой точки на стене и перемещать стены, удаляя стены с карты при их обработке. Когда вы больше не можете двигаться, цикл завершен (вы гарантированно завершаете циклы, потому что в графе, построенном таким образом, из матрицы внутренних/внешних флагов степень гарантирована даже во всех вершинах).

Заполнение всех этих циклов одновременно с использованием правил нечетного заполнения также гарантированно воспроизводит исходную матрицу.

В следующем коде я использую r и c как индекс row/col и i и j вместо этого, чтобы представлять точки на границе... например, для ячейки (r=3, c=2) схема является:

где красная стена соответствует бит 0x02, а зеленая стена - бит 0x01. Матрица walls имеет одну строку и один столбец меньше исходной матрицы данных, поскольку она предполагала, что никакие стены не могут присутствовать в последней строке или столбце.

result = []
for r in range(rows-1):
    for c in range(cols-1):
        if walls[r][c] & 1:
            i, j = r+1, c
            cycle = [(i, j)]
            while True:
                if i < rows-1 and walls[i][j-1] & 2:
                    ii, jj = i+1, j
                    walls[i][j-1] -= 2
                elif i > 0 and walls[i-1][j-1] & 2:
                    ii, jj = i-1, j
                    walls[i-1][j-1] -= 2
                elif j < cols-1 and walls[i-1][j] & 1:
                    ii, jj = i, j+1
                    walls[i-1][j] -= 1
                elif j > 0 and walls[i-1][j-1] & 1:
                    ii, jj = i, j-1
                    walls[i-1][j-1] -= 1
                else:
                    break
                i, j = ii, jj
                cycle.append((ii, jj))
            result.append(cycle)

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

Сложность алгоритма - O (строки * cols), т.е. пропорциональна размеру входа и оптимальна (в смысле большого О), потому что вы не можете вычислить результат без по крайней мере чтения ввода. Это легко увидеть, потому что тело в то время не может быть введено больше времени, чем общее количество стен на карте (при каждой итерации стена удаляется).

Изменить

Алгоритм может быть изменен, чтобы генерировать в качестве выходных только простые циклы (т.е. пути, в которых каждая вершина посещается только один раз).

result = []
index = [[-1] * cols for x in range(rows)]
for r in range(rows-1):
    for c in range(cols-1):
        if walls[r][c] & 1:
            i, j = r+1, c
            cycle = [(i, j)]
            index[i][j] = 0
            while True:
                if i > 0 and walls[i-1][j-1] & 2:
                    ii, jj = i-1, j
                    walls[i-1][j-1] -= 2
                elif j > 0 and walls[i-1][j-1] & 1:
                    ii, jj = i, j-1
                    walls[i-1][j-1] -= 1
                elif i < rows-1 and walls[i][j-1] & 2:
                    ii, jj = i+1, j
                    walls[i][j-1] -= 2
                elif j < cols-1 and walls[i-1][j] & 1:
                    ii, jj = i, j+1
                    walls[i-1][j] -= 1
                else:
                    break
                i, j = ii, jj
                cycle.append((ii, jj))
                ix = index[i][j]
                if ix >= 0:
                    # closed a loop
                    result.append(cycle[ix:])
                    for i_, j_ in cycle[ix:]:
                        index[i_][j_] = -1
                    cycle = cycle[:ix+1]
                index[i][j] = len(cycle)-1

Это реализуется путем добавления к выходу отдельного цикла, когда одна и та же вершина встречается дважды в процессе обработки (таблица index хранит для заданного i,j точки, основанные на 0 в текущем цикле).

Ответ 2

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

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

Если ячейка справа - это земля, то вы меняете текущую ячейку на нее и меняете угол в верхнем левом углу (это одна и та же точка). Затем вы переходите к следующей итерации.

В другом случае, если вы начали с верхнего правого угла какой-либо земной ячейки и хотите идти по часовой стрелке. Если ячейка справа не является землей, чем вы не меняете текущую ячейку и меняете угол внизу справа, (это следующая точка)

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

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

Мне также понадобится дополнительный массив с почти теми же размерами, что и матрица для маркировки обработанных контуров, он должен быть на 1 ячейку шире, чем у матрицы, потому что я собираюсь отметить вертикальные линии, и каждая вертикальная линия должна иметь координаты ячейку справа от нее. Обратите внимание, что есть только 2 случая midst 8, описанных выше, когда вам нужно отметить вертикальную линию.

    int mark[,] = new int[height,width+1]       
    start_i = i = 0;
    start_j = j = 0;
    direction = start_direction = top_left;
    index = 0;

    //outer cycle through different contours
    while(true)
    {
      ++index;
      //scanning for contours through all the matrix
      //continue from the same place, we stopped last time
      for(/*i = i*/; i < n; i++)
      {
        for(/*j = j*/; j < n; j++)
        {
           //if we found earth
           if(m[i,j] == 1)
           {
               //check if previous cell is nothing
               //check if line between this and previous contour doesn't already added
               if(m[i,j - 1] == 0 && mark[i,j] == 0)
               {
                   direction = bottom_left;
                   break;
               }

               //the same for next cell
               if(m[i,j + 1] == 0 && mark[i,j+1] == 0)
               {
                   direction = top_right;
                   break;
               }
           }
        }
        //break if we found contour
        if(i != start_i || j != start_j)
          break;
      }

      //stop if we didn't find any contour
      if(i == start_i && j == start_j)
      {
        break;
      }

      polygon = new polygon;
      start_i = i;
      start_j = j;
      start_direction = direction;

      //now the main part of algorithm described above
      do
      {
        if(direction == top_left)
        {
           if(n(i-1,j) == 1)
           {
              direction = bottom_left;
              position = (i-1,j)
           }
           else
           {
              direction = top_right;
              polygon.Add(i,j+1);       
           }
        }
        if(direction == top_right;)
        {
           if(n[i,j + 1] == 1)
           {
              direction = top_left;
              position = (i,j + 1)
           }
           else
           {
              direction = bottom_right;
              mark[i, j + 1] = index;//don't forget to mark edges!
              polygon.Add(i+1,j+1);       
           }
        } 
        if(direction == bottom_right;
        {
           if(n[i+1,j] == 1)
           {
              direction = top_right;
              position = (i+1,j)
           }
           else
           {
              direction = bottom_left;
              polygon.Add(i+1,j);       
           }
        } 
        if(direction == bottom_left)
        {
           if(n[i,j - 1] == 1)
           {
              direction = bottom_right;
              position = [i,j - 1]
           }
           else
           {
              direction = top_left;
              mark[i, j] = index;//don't forget to mark edges!
              polygon.Add(i,j);       
           }
        } 
      //and we can stop as we reached the starting state
      }while(i != start_i || j != start_j || direction != start_direction);

      //stop if it was last cell
      if(i == n-1 && j == n- 1)
      {
        break;
      }
    }

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

  ...
  //continue from the same place, we stopped last time
  for(/*i = i*/; i < n; i++)
  {
    for(/*j = j*/; j < n; j++)
    {
       if(mark[i,j] != 0)
       {
           if(stack.top() == mark [i,j])
           {
                stack.pop();
           }
           else
           {
                stack.push(mark [i,j]);
           }
       }
       //if we found earth
       if(m[i,j] == 1)
       {
           ...

Ответ 3

Кажется, это сработало бы со мной:

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

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

Повторите, чтобы создать список путей. Простой полигон должен быть одним из путей. В этом случае сложный многоугольник - один с отверстиями в середине - будет несколько.

Ответ 4

Если ваша матрица может содержать случайные шаблоны, ответ намного сложнее, чем кажется.

С одной стороны, они могут быть произвольным числом различных полигонов, и каждый из них может быть полым.

Кроме того, поиск контура области (даже без отверстий) мало помогает при рисовании поверхности. Ваш графический процессор в конечном итоге будет нуждаться в треугольниках, что означает, что вам нужно разложить ваши полигоны на прямоугольники.

Нахождение оптимального разложения полого пучка квадратов (т.е. наименьшего множества прямоугольников, которые будут покрывать их все) является хорошо изученной NP-полной задачей без известного решения.

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

Жадный алгоритм намного проще реализовать и обычно дает приемлемые результаты.

Итак, я бы сделал жадный поиск на вашей матрице, собирая прямоугольники, пока не будут посещены все значения "1". Поворот этих прямоугольников в координаты должен быть достаточно простым, так как вы точно знаете, где расположены верхние левые и нижние правые углы.

Жадное сканирование будет выглядеть так:

while your matrix is not empty
    move to first "1" value. This is the rectangle top left corner
    from this corner, extend the rectangle in x and y to maximize its surface
    store the rectangle in a list and clear all corresponding "1" values