Как проверить, что двумерное растровое изображение является смежным? - PullRequest
Новая
       12

Как проверить, что двумерное растровое изображение является смежным?

2 голосов
/ 10 сентября 2010

Допустим, у вас есть следующая структура в C #: 

struct Piece : IEquatable<Piece> {
    public readonly int size;
    public readonly bool[,] data;

    public Piece(Piece p) {
        size = p.size;

        data = (bool[,])p.data.Clone();
    }
    public Piece(int s, bool[,] d) {
        size = s;
        if (d.GetLength(0) != s || d.GetLength(1) != s) throw new ArgumentException();

        data = (bool[,])d.Clone();
    }

    public bool Equals(Piece other) {
        if (size != other.size) return false;

        return (data.Equals(other.data));
    }
}

Идея состоит в том, что она представляет size x size набор битов, который представляет форму (битовая карта, если выwill).

Теперь не все возможные комбинации битов действительны.У меня есть несколько требований:

  1. Всего должно быть только size бит.(Это легко, я уже реализовал это)
  2. Все биты должны быть смежными.

Итак, снова предполагая size==4, хорошо следующее: 

..#.
..#.
.##.
....

Хотя следующего нет: 

...#
...#
#...
#...

Как определить, являются ли все биты смежными или нет?

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

struct Point : IEquatable<Point> {
    public int X, Y;

    public Point(int x, int y) {
        X = x; Y = y;
    }

    public bool Equals(Point obj) {
        return X == obj.X && Y == obj.Y;
    }

    public override bool Equals(object obj) {
        if (obj == null) return false;

        if(obj is Point)
            return Equals((Point)obj);

        return false;
    }

    public override int GetHashCode() {
        return X ^ ~Y;
    }

    public static bool operator == (Point p1, Point p2) {
        return p1.X == p2.X && p1.Y == p2.Y;
    }

    public static bool operator !=(Point p1, Point p2) {
        return p1.X != p2.X || p1.Y != p2.Y;
    }

    public static readonly Point Empty = new Point(int.MinValue, int.MinValue);
}

struct Piece : IEquatable<Piece> {
    public readonly int size;
    public readonly bool[,] data;
    private bool valid;

    public Piece(Piece p) {
        size = p.size;
        valid = p.valid;
        data = (bool[,])p.data.Clone();
    }
    public Piece(int s, bool[,] d) {
        size = s;
        if (d.GetLength(0) != s || d.GetLength(1) != s) throw new ArgumentException();

        data = (bool[,])d.Clone();
        valid = false;

        CalcValidity();
    }

    public bool IsValid {
        get {
            return valid;
        }
    }


    private enum Square {
        White,
        Black,
        Red,
        Blue,
    }

    private int NumSquares(Square[,] map, Square q) {
        int ret = 0;
        for (int y = 0; y < size; y++) {
            for(int x = 0; x < size; x++) {
                if (map[x, y] == q) ret++;
            }
        }
        return ret;
    }

    private Point PickSquare(Square[,] map, Square q) {
        for (int y = 0; y < size; y++) {
            for (int x = 0; x < size; x++) {
                if (map[x, y] == q) return new Point(x, y);
            }
        }
        return Point.Empty;
    }

    private void MakeNeighboursRed(Square[,] map, Point p) {
        if (p.X > 0 && map[p.X - 1, p.Y] == Square.Black) map[p.X - 1, p.Y] = Square.Red;
        if (p.X < size - 1 && map[p.X + 1, p.Y] == Square.Black) map[p.X + 1, p.Y] = Square.Red;

        if (p.Y > 0 && map[p.X, p.Y - 1] == Square.Black) map[p.X, p.Y - 1] = Square.Red;
        if (p.Y < size - 1 && map[p.X, p.Y + 1] == Square.Black) map[p.X, p.Y + 1] = Square.Red;
    }

    private void CalcValidity() {
        Square[,] map = new Square[size, size];

        int count = 0;
        Point square = Point.Empty;


        for (int y = 0; y < size; y++) {
            for (int x = 0; x < size; x++) {
                if (data[x, y]) {
                    map[x, y] = Square.Black;
                    square = new Point(x, y);
                } else {
                    map[x, y] = Square.White;
                }
            }
        }

        if (square != Point.Empty) {
            map[square.X, square.Y] = Square.Red;
        }

        while (true) {
            if (NumSquares(map, Square.Red) == 0) {
                if (NumSquares(map, Square.Black) == 0) {
                    valid = count == size;
                    return;
                } else {
                    valid = false;
                    return;
                }
            } else {
                square = PickSquare(map, Square.Red);

                MakeNeighboursRed(map, square);
                map[square.X, square.Y] = Square.Blue;
                count++;
            }
        } 
    }

    #region IEquatable<Piece> Members

    public bool Equals(Piece other) {
        if (size != other.size) return false;

        for (int y = 0; y < size; y++) {
            for (int x = 0; x < size; x++) {
                if (data[x, y] != other.data[x, y]) return false;
            }
        }
        return true;
    }

    #endregion
}

Ответы [ 2 ]

6 голосов
/ 11 сентября 2010

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

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

Вы можете использовать этот алгоритм:

  1. Если чёрных квадратов нет, то верно, что чёрных не существует.регионы, так что вы сделали.
  2. В противном случае есть по крайней мере один черный квадрат.Выберите любой черный квадрат и сделайте его красным.
  3. Если красных и черных квадратов нет, значит, все готово, а черные области являются смежными .
  4. Если нет красных квадратов, но один или несколько черных квадратов, то все готово.Черные области не являются смежными .Область, которая все еще черная, не связана с областью, синей.
  5. В противном случае должен быть хотя бы один красный квадрат.Выберите любой красный квадрат.Поверните всех его черных соседей на красный, а затем на синий.
  6. Вернитесь к шагу 3.

Посмотрите, как это работает?Красные квадраты являются «краями» региона, который не заполнен.Синие квадраты - это затопленная область.Если синий заливает все черное, значит, он был смежным.

ОБНОВЛЕНИЕ: Re, ваш комментарий:

Спасибо вам большое!Это потрясающе.Мне нравится ваш блог, особенно статьи о LINQ и "писать, что вы имеете в виду", и я попытался применить эти принципы здесь

Спасибо за добрые слова.Если то, что вам нравится, - это очень "LINQ-y" решения для такого рода проблем, то я бы не использовал решение, которое я набросал здесь.Обратите внимание, что алгоритм в основном «изменяет структуру данных, чтобы узнать факты об этом».Это не очень то, что нужно для LINQ.LINQ - это все о запросах к структурам данных без их изменения.

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

Прежде всего, вы знаете, что такое "класс эквивалентности" или "отношение эквивалентности"?Я кратко опишу их, если вы не знаете. отношение - это функция, которая принимает две вещи и возвращает логическое значение.Например, «меньше чем», «равно», «имеют одну и ту же последнюю цифру в десятой десятке», а «сумма к четному числу» - все отношения на целых числах.Отношение эквивалентности (A ~ B) является отношением, рефлексивным (X ~ X всегда истинно), симметричным (X ~ Y и Y ~ Xодинаковы) и переходные (если X ~ Y и Y ~ Z оба истинны, то и X ~ Z).

В наших примерах "меньше чем" является транзитивным, но нерефлексивный или симметричный.Остальные три - отношения эквивалентности.

Отношение эквивалентности разбивает множество на классы эквивалентности.Например, отношение эквивалентности «сумма к четному числу» делит целые числа на два класса эквивалентности: четные числа и нечетные числа.Выберите любые два нечетных числа, и X ~ Y верно.Выберите любые два четных числа, и X ~ Y верно.Но нечетное число и четное число, X ~ Y ложно.Все четные числа являются «эквивалентными» для целей этого отношения.

Теперь рассмотрим отношение "является соседом в этом наборе плиток" для одного из ваших наборов плиток.Ясно, что это не отношение эквивалентности;это симметрично, но не рефлексивно или транзитивно.Но любое отношение может быть расширенным , чтобы быть отношением эквивалентности, путем определения нового отношения, которое является рефлексивным и транзитивным замыканием отношения.Это отношение «достижимо от».

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

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

Так как у вас есть способ подсчета плиток, и так как числа являются конечными целыми числами, мы можем сделать даже лучше, чем это.Мы можем просто спросить: «Является ли размер рефлексивного и транзитивного замыкания отношения соседей на произвольной черной плитке идентичным количеству всех черных плиток?»чтобы решить вашу проблему.

Так, как ответить на этот вопрос?Предположим, у вас есть метод, который берет плитку и возвращает последовательность ее соседей: 

public static IEnumerable<Tile> GetNeighbours(Tile tile)
{
     ... yield return the north, south, east and west neighbours
     ... if they exist and they are on
}

По сути, этот метод «задан плиткой, дайте мне все плитки, которые имеют отношение к соседям».Это прекрасно работает, если вы можете вычислить, какие члены имеют отношение с данным членом, что, очевидно, в этом случае вы можете сделать это дешево.

Теперь вы можете вычислить транзитивное и рефлексивное замыкание этого отношения, используя код Iразмещено здесь:

http://blogs.msdn.com/b/ericlippert/archive/2010/02/08/making-the-code-read-like-the-spec.aspx

И теперь весь ваш алгоритм действительно очень короток: 

bool HasExactlyOneRegion()
{
    return (tilesTurnedOn.Count == 0) ? 
        false : 
        TransitiveAndReflexiveClosure(GetNeighbours, tilesTurnedOn.First()).Count == tilesTurnedOn.Count;
}

Если у вас есть нужные инструменты в вашем распоряжении, то решениеодно утверждение!

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

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

0 голосов
/ 11 сентября 2010

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

Правка: Обратите внимание, что рекурсия будет запущенаНедостаточно места в стеке, если растровые изображения большие.

...