Частичное заполнение наводнения

Question

Я пишу генератор мира на основе вороной, в котором я различаю географические объекты, такие как горы, озера, леса и океаны.

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

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

Я бы хотел со временем пометить их"West 100 Acre Wood" и "East 100 Acre Wood", давая им знание, что они происходят из одного и того же непрерывного массива леса.Я искал логику частичного заполнения, но мой поиск застрял из-за отсутствия предметной терминологии.

Если вы хотите увидеть код, с которым я работаю: https://github.com/olinkirkland/map

Answer 1

Обычно вы используете «морфологическое отверстие» , см. Определение Википедии , которое представляет собой морфологическую эрозию с последующей дилатацией. Если вы представляете интересующий белый объект переднего плана на черном фоне, эрозия разрушит (откусит по краям) объект, и расширение расширит / отожжет края назад - таким образом удаляя небольшие полосы и узкие соединения.

Вы можете сделать это с помощью модуля Scikit-Image в Python или с OpenCV в Python или C ++. Я решил сделать это в командной строке терминала, используя ImageMagick , который установлен в большинстве дистрибутивов Linux и доступен для macOS и Windows.

Итак, используя это изображение карты:

Я загружаю его, инвертирую / отменяю его, чтобы сделать лес белым, затем применяю морфологическое отверстие, которое я упомянул, а затем инвертирую обратно и сохраняю:

magick convert map.png -negate -morphology open disk:5 -negate result.png 

Answer 2

После того, как вы найдете подключенную область, вы можете обвести внутреннюю часть, используя правило правой руки (https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower).

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

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

1. BFS для удаления пикселей, которые находятся на расстоянии менее w от границы.

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

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

4. Добавьте обратно удаленные пиксели, соединив их с ближайшим центром.

Answer 3

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

Разделение лесов с помощью размытия и применения порога

На верхнем изображении представлена ​​исходная ситуация с двумя лесами, которые связаны тонким коридором. Процесс шаг за шагом убирает коридор.

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