Найти области в матрице ..?

Question

Допустим, у меня очень большая матрица с элементами 10000x10000 со значением «0».Допустим, есть несколько больших «гнезд» из 1.Эти области могут даже быть связаны, но очень еженедельно соединяться с помощью «трубы» из «1».

Я хочу получить алгоритм, который очень быстро (и, если необходимо, грязный) находит эти «гнезда» из 1.Здесь он не должен «разрезать» два еженедельно связанных «гнезда».

Есть идеи, как мне сделать такой алгоритм?

Answer 1

Возможно, алгоритм поиска пути, такой как A * (или что-то более простое, например, BFS или DFS), может работать в этом случае.

Вы можете:

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

Answer 2

1. Превращение матрицы в черно-белое растровое изображение
2. Масштабирование матрицы таким образом, чтобы гнезда размера N становились единым пикселем (поэтому, если вы ищете гнезда 10x10, масштабируйте с коэффициентом N = 10).
3. Используйте оставшиеся пиксели вывода, чтобы найти гнезда.Используйте координату центра (умноженную на коэффициент выше), чтобы найти то же гнездо в матрице.
4. Используйте фильтр нижних частот, чтобы избавиться от всех "труб", которые соединяют гнезда.
5. Найдите границу гнезда с контрастным фильтром на растровом изображении.
6. Создайте растровое изображение, не содержащее гнезд (т. Е. Установите все пиксели гнезд на 0).
7. Использованиефильтр, расширяющий отдельные пиксели для увеличения контура гнезд.
8. Побитовый AND выходные данные 7 и 5 для получения точек соединения всех труб.
9. Следуйте по трубам, чтобы увидетькак они соединяют гнезда

Answer 3

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

Если у вас нет никакой другой информации, возможно, один из них будетвозможность:

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

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

Убедитесь, что вы используете реализацию набора с оченьнизкая стоимость поиска, такая как хеш-таблица или, возможно, фильтр Блума, если вы можете справиться с вероятностными эффектами.