То, что вы описываете, это проблема сегментации . Мне жаль говорить, что это на самом деле нерешенная проблема. Но один метод, который я бы порекомендовал для этого - алгоритм на основе Graph-Cut . Graph-Cut представляет изображение в виде графа локально связанных узлов. Он рекурсивно подразделяет связанные компоненты графа таким образом, что граница между двумя подкомпонентами имеет минимальную длину с использованием теоремы Max-flow-min-cut и алгоритма Форда Фулкерсона .
По сути, вы соединяете все плитки воды в график. Присвойте весам ребра на графике, которые соответствуют различиям между соседними водными плитками. Я думаю, что в вашем случае все весовые коэффициенты могут быть равны 1. Вам придется играть с различными схемами взвешивания, чтобы получить желаемый результат. Например, вам может понадобиться добавить вес, который включает в себя смежность с побережьем.
Затем найдите все связанные компоненты графа. Это очевидные моря / озера и так далее.
Наконец, для каждого подключенного компонента рекурсивно подразделите компонент так, чтобы ребра, соединяющие два новых подкомпонента, имели минимальный вес . Продолжайте рекурсивное деление до тех пор, пока все подкомпоненты не достигнут минимального размера (например, как максимальный размер моря), или если края, режущие два компонента, имеют слишком большой вес. Наконец, пометьте все оставшиеся подключенные компоненты.
Что это будет делать на практике, так это отрезать моря друг от друга в каналах, но не через большие пролеты океанов.
Вот это в псевдокоде:
function SegmentGraphCut(Map worldMap, int minimumSeaSize, int maximumCutSize)
Graph graph = new Graph();
// First, build the graph from the world map.
foreach Cell cell in worldMap:
// The graph only contains water nodes
if not cell.IsWater():
continue;
graph.AddNode(cell);
// Connect every water node to its neighbors
foreach Cell neighbor in cell.neighbors:
if not neighbor.IsWater():
continue;
else:
// The weight of an edge between water nodes should be related
// to how "similar" the waters are. What that means is up to you.
// The point is to avoid dividing bodies of water that are "similar"
graph.AddEdge(cell, neighbor, ComputeWeight(cell, neighbor));
// Now, subdivide all of the connected components recursively:
List<Graph> components = graph.GetConnectedComponents();
// The seas will be added to this list
List<Graph> seas = new List<Graph>();
foreach Graph component in components:
GraphCutRecursive(component, minimumSeaSize, maximumCutSize, seas);
// Recursively subdivides a component using graph cut until all subcomponents are smaller
// than a minimum size, or all cuts are greater than a maximum cut size
function GraphCutRecursive(Graph component, int minimumSeaSize, int maximumCutSize, List<Graph> seas):
// If the component is too small, we're done. This corresponds to a small lake,
// or a small sea or bay
if(component.size() <= minimumSeaSize):
seas.Add(component);
return;
// Divide the component into two subgraphs with a minimum border cut between them
// probably using the Ford-Fulkerson algorithm
[Graph subpartA, Graph subpartB, List<Edge> cut] = GetMinimumCut(component);
// If the cut is too large, we're done. This corresponds to a huge, bulky ocean
// that can't be further subdivided
if (GetTotalWeight(cut) > maximumCutSize):
seas.Add(component);
return;
else:
// Subdivide each of the new subcomponents
GraphCutRecursive(subpartA, minimumSeaSize, maximumCutSize);
GraphCutRecursive(subpartB, minimumSeaSize, maximumCutSize);
РЕДАКТИРОВАТЬ : Кстати, вот что алгоритм будет делать с вашим примером с минимальным размером моря около 40, с максимальным размером разреза 1, если все веса ребер равны 1:
Играя с параметрами, вы можете получить разные результаты. Например, максимальный размер разреза, равный 3, приведет к тому, что из основных морей будет вырезано гораздо больше заливов, а море № 1 разделится пополам с севера на юг. Минимальный размер моря 20 приведет к тому, что центральное море также будет разделено пополам.
Быстрый и грязный способ идентифицировать отдельный, но связанный водоем - это сжать все водоемы и посмотреть, не появятся ли пробелы.
В приведенном выше примере я думаю, что удаление всех водяных плиток, к которым подключено 2 или менее водяных плиток (помечено красным), даст вам желаемый результат плюс некоторый краевой шум. После того, как вы пометили тела, вы можете «перелить» воду в ее первоначальное состояние и вернуть удаленные плитки для теперь уже отдельных тел.
Опять же, это быстрое и грязное решение, оно может быть недостаточно хорошим для более поздних этапов производства, но этого будет достаточно, чтобы «заставить это работать сейчас» и перейти к какой-то другой функции.
источник
Вот полный алгоритм, который, я думаю, должен дать хорошие результаты.
Выполните морфологическую эрозию на акватории, то есть сделайте копию карты, на которой каждая плитка считается водой, только если она и все ее соседи (или большая область, если у вас реки шире, чем одна плитка) являются водой , Это приведет к тому, что все реки полностью исчезнут.
(При этом вода в левой части вашего внутреннего моря будет считаться реками. Если это проблема, вы можете использовать другое правило, например, предложенное в ответе одного вринека ; следующие шаги будут работать до тех пор, пока вы есть какой-то шаг «удалить реки» здесь.)
Найдите подключенные водные компоненты разрушенной карты и присвойте каждому уникальный ярлык. (Я предполагаю, что вы уже знаете, как это сделать.) Теперь это обозначает все, кроме рек и прибрежных вод (где эрозия имела влияние).
Для каждой плитки воды на исходной карте найдите метки, присутствующие на соседних плитах воды на эродированной карте, а затем:
(Обратите внимание, что для этого шага вы должны хранить отдельные сетки меток (или иметь два поля меток в одной структуре) для эродированной карты (из которой вы читаете) и оригинала (в которую вы пишете), иначе будет итерация. ошибки, зависящие от заказа.)
Если вы хотите также уникально маркировать отдельные реки, то после описанных выше шагов найдите все оставшиеся подключенные компоненты немеченой воды и пометьте их.
источник
Следуя идее Вринека, как насчет выращивания земли (или сокращения воды), чтобы части, к которым вы изначально были подключены, были отсоединены после выращивания земли?
Это можно сделать так:
Определите, насколько вы хотите вырастить землю: 1 гекс? 2 гекса? Это значение
nПосетите все наземные узлы и установите все их соседи на глубину
nдля приземления узлов (запишите в копию, чтобы не получить бесконечный цикл)Снова запустите исходный алгоритм залива, чтобы определить, что теперь подключено, а что нет.
источник
У вас есть приблизительное представление о том, где находится залив? Если это так, вы можете изменить заливку, чтобы отслеживать количество соседних, но неисследованных ячеек (вместе со списком посещенных ячеек). Начинается с 6 на шестнадцатеричной карте, и всякий раз, когда это значение падает ниже определенной точки, вы знаете, что попали в «открытие».
источник