Функциональное расстояние

Хотя эвклидово расстояние полезно, нашу способность двигаться по прямой часто ограничивают препятствия или сложная местность. Например, мы можем быть ограничены либо использованием сетей, таких как авто- и железные дороги, либо потому, что местность слишком пересеченная, образуяфрикционную поверхность (friction surface), либо из-за ограждений, окружающих промежуточное пространство, которые действуют какбарьеры(barriers) на нашем пути*. Фрикционные поверхности — это области, которые замедляют наше продвижение, увеличивая время достижения заданной точки по сравнению с поверхностью без сопротивления (Рисунок 8.4). Барьеры бывают двух типов (Рисунок 8.5):абсолютные (absolute), движение через которые невозможно (скалы, огражденная территория, озеро и т.д.), и условные (relative), которые идентичны фрикционным поверхностям, но занимают лишь небольшие участки покрытия. Примерами условных барьеров могут быть холмистая местность, мелкие реки, преодолимые внедорожными машинами, или участки леса, которые тормозят, но не останавливают полностью движение стада животных.

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

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

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

* Автор недостаточно ясно проводит различие типов поверхностей. Поверхность может быть изотропной, т.е. с одинаковыми свойствами независимо от направления движения по ней, и анизотропной (при этом на ней не обязательно должны быть барьеры). Фрикционная поверхность создает сопротивление, при этом она может быть и изотропной. — прим. перев.

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

Рисунок 8.5. Условные и абсолютные барьеры. Условные барьеры (а) имеют определенную стоимость их преодоления. Абсолютные барьеры (b) либо полностью останавливают движение, либо отклоняют его к какой-нибудь доступной проходимой точке.

Условный барьер может быть не только тонкой линией, но и площадным объектом. Конкретное значение импеданса может быть связано как с фактом полного прохождения такой области, так и с фактом проникновения внутрь нее на единичное расстояние. В первом случае обычно говорят о барьере, а во втором - о распределенном импедансе, о райнировании территории по величине затрат на передвижение, о поверхности, представляющей функцию затрат. Возможен также предельный случай, когда значение импеданса будет разным в каждой ячейке растра. И даже более того - значение импеданса даже в одной ячейке может быть различным при передвижении через нее по разным направлениям. Например, оно может зависеть от направления ветра или от ориентации снежных застругов в тундре.

Абсолютный барьер можно представить себе как некоторое продолжение идеи условного барьера. Для линейного объекта мы просто присвоить ему значение импеданса, непреодолимое в рамках решаемой задачи. На Рисунке 8.6Ь ячейкам барьера приписано значение импеданса 1000, которое считается непреодолимым, и, следовательно делает барьер абсолютным. В других случаях этого значения может оказаться недостаточно, поэтому вы должны сами решать, какое значение использовать для вашей конкретной задачи.

Рисунок 8.6. Импеданс. Нарастающие значения стоимости передвижения при встрече с условным барьером (а) и абсолютным барьером (b).

Хотя сама идея присвоения значений импеданса — проста, использование ее часто вызывает трудности. Каково сопротивление леса для стада оленей, движущегося через него? Насколько больше бензина тратит автомобиль на подъеме в 15% по сравнению с горизонтальным движением? Насколько дольше крупное млекопитающее переплывает реку шириной 100 метров по сравнению с переходом по мосту такой же длины? Это вполне реальные вопросы, которые должны получать ответы перед тем, как мы создадим наши барьеры и фрикционные поверхности. Чаще всего конкретного ответа не просто нет, а он еще и зависит от таких трудноопределимых параметров, как подвижность оленей, КПД автомобиля или плавательных способностей зебр. Другими словами, чаще всего у нас нет точных значений сопротивления. Обычно мы прибегаем к употреблению порядковой ранжирующей системы для присваивания величин импеданса, основываясь на сравнении относительной трудности движения по каждой встречающейся фрикционной поверхности или через барьеры. Это не всегда легко, а результаты не так точны, как нам хотелось бы. В установке этих величин рекомендуется действовать с осторожностью, убедившись, что использованная система достаточно обоснована, и что сравнения допустимы. Прежде всего, результаты анализа расстояний с использованием барьеров и фрикционных поверхностей должны рассматриваться с определенной критичностью, особенно если эти результаты используются для принятия каких-либо решений.

Перед тем, как приступить к растровым подходам для неэвклидовых и функциональных расстояний, мы должны рассмотреть две дополнительные характеристики расстояний. Расстояние может рассматриваться не только как эвклидово или неэвклидово, изотропное или функциональное, но также и какинкрементное, или нарастающее расстояние (incremental or cumulative distance). Инкрементное расстояние складывается из длин этапов пройденного пути. Каждый последующий этап добавляется просто как мера длины, наподобие того, как это делалось с изотропной поверхностью. Другими словами, инкрементное расстояние - это кратчайший путь между двумя точками без учета сопротивления в пути. Если инкрементное расстояние измеряется по всей поверхности, то в результате мы получаем поверхность кратчайших расстояний (shortest path surface), если же этот метод ограничивается линиями или дугами (или линейными группами ячеек растра), то мы имеем дело слиниями кратчайших расстояний, а не с поверхностью.

Целью определения функционального расстояния на поверхности с сопротивлением (например, топографической) является поискмаршрута наименьшей стоимости (least-cost distance), или кратчайшего расстояния между двумя точками покрытия*. Аналогично мы можем построить и поверхность наименьшей стоимости для перемещения из одной точки во все другие точки покрытия. Рассмотрим два этих случая по отдельности.

Допустим, что мы имеем дело с реальной топографической поверхностью, и стоимость связана с изменением значения высоты от ячейки к ячейке. Мы могли бы поместить каплю воды на вершину нашей поверхности и проследить ее движение, которое будет путем наименьшего сопротивления. Между прочим, многие программы используют в качестве команд такие слова как "drain" (сток) или "stream" (поток, река). Для создания маршрута наименьшей стоимости (в противоположность кратчайшему маршруту) на растре размером 5х5 мы начинаем с верхней ячейки и ищем среди восьми соседей ячейку с наименьшим значением импеданса (в данном случае - с наименьшим значением высоты). Эта ячейка помечается флажком и становится начальной точкой для следующей итерации. Процесс

* В реальных задачах обычно учитываются стоимостные показатели нескольких покрытий, которые с помощью весовой функции сводятся к некоторому общему стоимостному покрытию. О построении таких поверхностей см. пример в Главе 13. — прим. перев.

продолжается, пока не будет достигнута наименьшая высота покрытия. Таким образом, из отмеченных ячеек мы получаем маршрут от вершины холма к подножию, который требует наименьшее количество усилий (Рисунок 8.7а). Более реалистичная версия такого поиска приведена на Рисунке 8.7b.

Рисунок 8.7. Маршрут наименьшей стоимости. Определение маршрута наименьшей стоимости требует сравнения начальной ячейки с ее непосредственными соседями: а) пример с футбольным мячом; b) то же в случае реки, текущей по склону холма.

Хотя одного маршрута наименьшей стоимости часто достаточно, может оказаться полезным просмотреть все возможные маршруты из определенного места с учетом стоимости передвижения по фрикционной поверхности. Посмотрите на Рисунок 8.8.

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

Рисунок 8.8. Нарастающее расстояние. Поверхность нарастающей стоимости:

а) фрикционное покрытие, b) вычисленные значения. Отметьте, что диагональные ячейки используют значение 1.414 в качестве расстояния вместо 1 для горизонтальных и вертикальных. Выделены ячейки со значением импеданса 3. Для накопления расстояния предыдущее значение складывается с вычисленным.

Процесс начинается в ячейке (0,0). Для каждой соседней ячейки расстояние считается инкрементами по полшага умножением каждой занятой ячейки растра (включая начальную) на ее значение сопротивления и на значение ее ширины (1 для горизонтальных и вертикальных ячеек и 1.414 - для диагональных). Поскольку мы движемся из середины начальной ячейки к середине следующей, мы умножаем каждую на 0.5, чтобы показать инкремент в полшага. Таким образом, формула для каждого шага на половину ячейки растра такова [Berry, 1993]: 0.5 (расстояние по сетке х коэффициент трения).

Затем мы должны прибавить это к накопленной величине сопротивления. Так, для движения из ячейки (6,6) к ячейкам (5,5), (4,4) и (5,6) вычисления таковы:

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

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

Однако, если мы не можем двигаться по прямой, т.е. имеется некоторое препятствие, вынуждающее нас отклоняться от прямой, то мы можем обобщить эту формулу в неэвклидову форму:

где степень 2 заменяется на k (соответственно корень будет не второй, а k-й степени), - некоторое из диапазона возможных значений [McGrew and Monroe,1993].

Нетрудно заметить, что подстановка k = 2 превращает эту формулу в предшествующую формулу для расстояния по прямой.

Рисунок 8.9. Измерение расстояния в векторной модели данных. Два способа определения неэвклидова расстояния, каждый является модификацией формулы теоремы Пифагора, причем в формуле меняется только параметр k.

Допустим, например, что мы ищем расстояние между двумя точками в Манхэттене, где десятки высоких зданий и кварталы ограничивают наше движение отрезками под прямым углом друг к другу. В этом случае мы имеем значительные ограничения движения, и переменная k принимает значение 1, а формула расстояния принимает вид:

Как видите, любое расстояние в векторной БД может быть определено простым изменением параметра/: в соответствии с имеющимися условиями (Рисунок 8.9). Значение k = 1.5 соответствует случаю где-то между манхэттенским и эвклидовым расстоянием. Даже фрикционные поверхности могут оцениваться с помощью этой формулы. Например, k = 0.6 позволяет нам найти кратчайшее расстояние вокруг некоторого барьера, такого как озеро.

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