Регион устанавливает от границ

Question

У меня есть карта высот, представленная двумерным массивом с плавающей точкой.

Существуют области этой карты, ребра которых я содержал в одном векторе, который содержит список краевых ячеек (идентифицированных по их x и y координатам).

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

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

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

Есть какие-нибудь мысли о том, как это сделать?

Answer 1

Ричард,

Это классическая проблема с маркировкой подключенных компонентов, не так ли?

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

Если вы не хотите предоставлять дополнительное хранилище для этого бита, вы, вероятно, можете «украсть» его из значений с плавающей запятой.Например, если все отметки положительны, вы можете присвоить знаковый бит для этой цели (и сбросить его позже);легко сделать в Си, отображая битовое поле над плавающей точкой.