Как работают инструменты стоимостного расстояния

Все инструменты стоимостного расстояния используют, по сути, тот же алгоритм для вычисления выходных данных. Основное различие определяется по первичным выходным данным каждого инструмента.

Вычисление стоимостного расстояния

Инструмент Стоимостное расстояние (Cost Distance) создает выходной растр, в котором каждой ячейке присваивается суммарная стоимость до ближайшей ячейки источника. Алгоритм использует представление ячейки по типу «узел/связь», используемому в теории графов. При представлении ячейки по принципу «узел/связь» центр каждой ячейки рассматривается как узел, и каждый узел может быть соединен несколькими связями со смежными узлами.

Каждой связи поставлено в соответствие сопротивление перемещению. Сопротивление определяется, исходя из стоимости, присвоенной ячейкам на каждом конце связи (стоимость берется с поверхности стоимости), и направления движения через ячейку.

Стоимость, присвоенная каждой ячейке, представляет стоимость движения через ячейку по поверхности стоимости, выраженную на единицу расстояния. Конечное значение на ячейке - это размер ячейки, умноженный на значение стоимости. Например, если растр стоимости имеет размер ячейки 30, а определенная ячейка имеет значение стоимости 10, конечная стоимость этой ячейки равна 300 единиц.

Стоимости перемещения узлов

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

Стоимость смежных узлов

При перемещении из ячейки в одну из четырех соседних ячеек, имеющих с ячейкой общее ребро, стоимость движения по этим связям в соседний узел будет равна среднему из стоимости перемещения через ячейки 1 и 2:

 a1 = (cost1 + cost2) / 2

• где:

  cost1 - Стоимость ячейки 1

  cost2 - Стоимость ячейки 2

  a1 - Общая стоимость связи из ячейки 1 до ячейки 2

Накопление перпендикулярной стоимости

Суммарная стоимость определяется по следующей формуле:

 accum_cost = a1 + (cost2 + cost3) / 2

• где:

  cost2 - Стоимость ячейки 2

  cost3 - Стоимость ячейки 3

  a2 - Стоимость перемещения из ячейки 2 в ячейку 3

  accum_cost - Суммарная стоимость перемещения из ячейки 3 в ячейку 1

Стоимость диагонального узла

Если перемещение происходит по диагонали, стоимость перемещения по связи - 1,414214 (или квадратный корень из 2), умноженная на стоимость ячейки 1 плюс стоимость ячейки 2 и деленная на 2:

 a1 = 1.414214 (cost3 + cost2) / 2

При определении совокупной стоимости для диагонального перемещения будет использована следующая формула:

 accum_cost = a1 + 1.414214(cost2 + cost3) / 2

Список ячеек с накоплением стоимости

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

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

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

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

Опять же, выбирается активная ячейка в списке с наименьшей стоимостью, расширяется окрестность, вычисляются новые стоимости, и новые ячейки стоимости добавляются в активный список.

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

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

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

В приведенном ниже примере ячейка в строке 3, столбце 1 (выделена), имеет суммарную стоимость 11,0, если она была помещена в активный список, чтобы достигнуть источник наверху растра. Однако, поскольку нижний источник расширен до этого местоположения, ячейки имеют доступ к пути с самой дешевой суммарной стоимостью для достижения источника. Значение для местоположения было обновлено в активном списке и распределено в выходные данные из-за этой меньшей суммарной стоимости.

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

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

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

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

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

Выходные значения стоимостного расстояния