Поиск всех циклов/замкнутых фигур в 2D сетке

Ответ 1

Я бы сделал это вот так:

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 1 0 1 0 1 0
0 1 1 1 1 1 0
0 0 0 0 0 0 0

• заполнить фон 2

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

  [0]0-0-0-0-0-0
   0 1 1 1 1 1 0
   0 1 0 1 0 1 0
   0 1 1 1 1 1 0
   0 0 0 0 0 0 0
  
   2 2 2 2 2 2 2
   2 1 1 1 1 1 2
   2 1 0 1 0 1 2
   2 1 1 1 1 1 2
   2 2 2 2 2 2 2
  

  Не используйте для этого недопустимые рекурсивные заливки!, потому что для "бесконечной" области вы будете переполнять поток. Вы можете ограничить уровень рекурсии и, если достигнут вместо рекурсии, добавьте точку в некоторый que для дальнейшей обработки последней. Это обычно ускоряет работу и ограничивает использование стека...

• найти первую 0

   2 2 2 2 2 2 2
   2 1 1 1 1 1 2
   2 1[0]1 0 1 2
   2 1 1 1 1 1 2
   2 2 2 2 2 2 2
  

• поток заполнить его 3

   2 2 2 2 2 2 2
   2 1 1 1 1 1 2
   2 1 3 1 0 1 2
   2 1 1 1 1 1 2
   2 2 2 2 2 2 2
  

• выберите все 1 рядом с 3

  это ваша схема. Если вы помните bbox при заполнении # 3, вам нужно отсканировать только область, увеличенную на одну ячейку с каждой стороны... Выбранные ячейки - это ваша схема.

   2 2 2 2 2 2 2
   2 * * * 1 1 2
   2 * 3 * 0 1 2
   2 * * * 1 1 2
   2 2 2 2 2 2 2
  

• заливка заливки 3 с помощью 2

  это позволит избежать использования уже обработанных схем

   2 2 2 2 2 2 2
   2 1 1 1 1 1 2
   2 1 2 1 0 1 2
   2 1 1 1 1 1 2
   2 2 2 2 2 2 2
  

• loop # 2, а 0 найден

• изменить все 2 на 0

   0 0 0 0 0 0 0
   0 1 1 1 1 1 0
   0 1 0 1 0 1 0
   0 1 1 1 1 1 0
   0 0 0 0 0 0 0
  

Ответ 2

Исходя из теоретико-графического представления проблемы, вы можете интерпретировать каждое 0 вашей карты как node, соседние 0s связаны с ребром. Мне кажется, что то, что вы хотите сделать, - вычислить связанные компоненты этого графика (и, возможно, их связь на 1 значение, найти "соседние комнаты" той же структуры)

Если вы хотите только вычислить эту информацию один раз, достаточно простого подхода с использованием структуры объединение-поиск, где вы применяете union один раз за край.

Если вы хотите динамически редактировать свою карту, лучшим подходом, основанным на модели графа, вероятно, будет некоторая динамическая структура данных, которая поддерживает операции split или de-union, см., например, здесь или here

Ответ 3

Это проблема поиска контуров.

Один из возможных алгоритмов описан Satoshi Suzuki и Keiichi Abe в своей статье под названием "Топологический структурный анализ оцифрованных двоичных изображений по границе", следующий в 1985 году. И это не тривиально. Но вы можете использовать OpenCV, cv2.findContours() реализует этот алгоритм.

Если вы решите использовать OpenCV, решение будет легко. Вы извлекаете контуры вдоль иерархии. Контуры, которые имеют по крайней мере один ребенок (отверстие) и их контуры ребенка, являются объектами, которые вы ищете. Пример использования управляемой оболочки OpenCV, называемой OpenCvSharp:

byte[,] a = new byte[7, 6]
{
    { 0, 1, 1, 1, 0, 0 },
    { 0, 1, 0, 1, 0, 0 },
    { 0, 1, 1, 1, 0, 0 },
    { 0, 0, 0, 0, 0, 0 },
    { 0, 1, 1, 1, 1, 1 },
    { 0, 1, 0, 1, 0, 1 },
    { 0, 1, 1, 1, 1, 1 }
};
// Clone the matrix if you want to keep original array unmodified.
using (var mat = new MatOfByte(a.GetLength(0), a.GetLength(1), a))
{
    // Turn 1 pixel values into 255.
    Cv2.Threshold(mat, mat, thresh: 0, maxval: 255, type: ThresholdTypes.Binary);
    // Note that in OpenCV Point.X is a matrix column index and Point.Y is a row index.
    Point[][] contours;
    HierarchyIndex[] hierarchy;
    Cv2.FindContours(mat, out contours, out hierarchy, RetrievalModes.CComp, ContourApproximationModes.ApproxNone);
    for (var i = 0; i < contours.Length; ++i)
    {
        var hasHole = hierarchy[i].Child > -1;
        if (hasHole)
        {
            var externalContour = contours[i];
            // Process external contour.
            var holeIndex = hierarchy[i].Child;
            do
            {
                var hole = contours[holeIndex];
                // Process hole.
                holeIndex = hierarchy[holeIndex].Next;
            }
            while (holeIndex > -1);
        }
    }
}

Ответ 4

Вы можете попробовать список точек и проверить те, которые связаны.

class PointList : List<Point>
{
    /// <summary>
    /// Adds the point to the list and checks for perimeters
    /// </summary>
    /// <param name="point"></param>
    /// <returns>Returns true if it created at least one structure</returns>
    public bool AddAndVerify(Point point)
    {
        this.Add(point);

        bool result = LookForPerimeter(point, point, point);
        Console.WriteLine(result);
        return result;
    }

    private bool LookForPerimeter(Point point, Point last, Point original)
    {
        foreach (Point linked in this.Where(p => 
            (p.X == point.X -1 && p.Y == point.Y)
            || (p.X == point.X + 1 && p.Y == point.Y)
            || (p.X == point.X && p.Y == point.Y - 1)
            || (p.X == point.X && p.Y == point.Y + 1)
        ))
        {
            if (!linked.Equals(last))
            {
                if (linked == original) return true;

                bool subResult = LookForPerimeter(linked, point, original);
                if (subResult) return true;
            }
        }

        return false;
    }
}

Этот код предназначен как отправная точка, он, вероятно, имеет ошибки и не учитывает периметры без 0 внутри

Пример использования:

class Program
{
    static void Main(string[] args)
    {
        PointList list = new PointList();

        list.AddAndVerify(new Point() { X = 0, Y = 0 }); //returns false
        list.AddAndVerify(new Point() { X = 0, Y = 1 }); //returns false
        list.AddAndVerify(new Point() { X = 0, Y = 2 }); //returns false
        list.AddAndVerify(new Point() { X = 1, Y = 2 }); //returns false
        list.AddAndVerify(new Point() { X = 2, Y = 2 }); //returns false
        list.AddAndVerify(new Point() { X = 2, Y = 1 }); //returns false
        list.AddAndVerify(new Point() { X = 2, Y = 0 }); //returns false
        list.AddAndVerify(new Point() { X = 1, Y = 0 }); //returns True
    }
}

Ответ 5

У меня была аналогичная проблема, пытаясь найти все круги в 2D графике карты улиц (данный файл SVG). Поскольку вы заявляете, что я тоже не смог найти алгоритм для этого.

Я нашел следующее решение.

Предположения

Макет сетки: Каждый "1" в сетке находится в одном из следующих состояний (или гомоморфизма этого):

1.   0      2.   0      3.   0      4.   0      5.   0      6.   1
   0 1 0       1 1 0       1 1 0       1 1 1       1 1 1       1 1 1
     0           0           1           0           1           1

Но только пример 3-6 имеет смысл для связной стены, так как в соединенной стене каждый "1" имеет по крайней мере два "1 в своей окрестности.

• Пример 3 указывает на угол. Этот угол занимает не более одной структуры.
• Пример 4 обозначает прямую линию. Это может быть стена нуля, одна или две структуры.
• Пример 5 показывает t-стенку. Это может быть стена из нулевой, одной, двух или трех структур.
• Пример 6 показывает поперечную стенку. Это может быть угол нуля, один, два, три или четыре структуры.

Алгоритм

Идея

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

Реализация

Я отправлю реализацию в ближайшие несколько дней для этого.

Ответ 6

Повторное опубликование моего решения с объяснением и некоторым кодом.

Прошло несколько дней, прежде чем были отправлены ответы. Я попытался найти решение и считаю, что нашел тот, который очень хорошо работает для моих нужд.

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

Для двумерной сетки с 1 или 0 в ячейке:

0 1 1 1 1 1
0 1 0 1 0 1
0 1 1 1 1 1

Начиная с ячейки, которую я уже знаю, есть 1, я начинаю свой поиск:

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

Клонирование позволяет каждой "ветке" стать уникальным циклом без точек смешивания.

Я не выполнял профилирование производительности, но он очень хорошо работает с примерами, которые я на него набросал.

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

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

public class CycleDetection {
    // Cache found cycles
    List<Cycle> cycles = new List<Cycle>();

    // Provide public readonly access to our cycle list
    public ReadOnlyCollection<Cycle> Cycles {
        get { return new ReadOnlyCollection<Cycle>(cycles); }
    }

    // Steps/slopes that determine how we iterate grid points
    public Point[] Steps = new Point[] {
        new Point(1, 0),
        new Point(0, 1),
        new Point(-1, 0),
        new Point(0, -1)
    };

    // Cache our starting position
    Point origin;

    // Cache the validation function
    Func<Point, bool> validator;

    public CycleDetection(Point origin, Func<Point, bool> validator) {
        this.origin = origin;
        this.validator = validator;

        this.Scan();
    }

    // Activate a new scan.
    public void Scan() {
        cycles.Clear();

        if (validator(origin)) {
            Scan(new List<Point>(), origin);
        }
    }

    // Add a cycle to our final list.
    // This ensures the cycle doesn't already exist (compares points, ignoring order).
    void AddCycle(Cycle cycle) {
        // Cycles have reached some existing point in the trail, but not necessarily
        // the exact starting point. To filter out "strands" we find the index of
        // the actual starting point and skip points that came before it
        var index = cycle.Points.IndexOf(cycle.Points[cycle.Points.Count - 1]);

        // Make a new object with only the points forming the exact cycle
        // If the end point is the actual starting point, this has no effect.
        cycle = new Cycle(cycle.Points.Skip(index).ToList());

        // Add unless duplicate
        if (!cycles.Contains(cycle)) {
            cycles.Add(cycle);
        }
    }

    // Scan a new point and follow any valid new trails.
    void Scan(List<Point> trail, Point start) {
        // Cycle completed?
        if (trail.Contains(start)) {
            // Add this position as the end point
            trail.Add(start);

            // Add the finished cycle
            AddCycle(new Cycle(trail));

            return;
        }

        trail.Add(start);

        // Look for neighbors
        foreach (var step in Steps) {
            var neighbor = start + step;

            // Make sure the neighbor isn't the last point we were on... that'd be an infinite loop
            if (trail.Count >= 2 && neighbor.Equals(trail[trail.Count - 2])) {
                continue;
            }

            // If neighbor is new and matches
            if (validator(neighbor)) {
                // Continue the trail with the neighbor
                Scan(new List<Point>(trail), neighbor);
            }
        }
    }
}

Я разместил здесь полный источник: https://github.com/OutpostOmni/OmniGraph (включая некоторые несвязанные утилиты графа)