Дороги
Перемещение по дорогам вообще значительно быстрее, чем через окружающую их местность. Мы используем модификатор, чтобы изменить издержки для граней между ячейками, которые соединены дорогой более низкой стоимости.
Новая стоимость вычислена так же как и основная стоимость грани. Надежней принять, что тип дороги тот же самый и в источнике и в адресате так, чтобы ecostmod = le/v, где v - скорость, с которой мы можем двигаться по заданному типу дороги.Как мы определим, соединяет ли дорога две ячейки? Ясно, что векторный характер данных представления дороги противоречит нашему способу представления графа, которым были представлены данные местности. Давайте начнем с 'растрезации' данных вектора дороги, то есть трансляции дороги в растровый формат, соответствующий сетке ячеек. Мы будем хранить один растр пути в 'пикселе', соответствующем каждой ячейке. Растеризация может быть выполнена разными способами (например см. [CLAR90] или [FOLE90]). В основном имеются два преобладающих способа: доминирующий пиксел (тонкая линия) растеризации, или пересеченный пиксел (толстая линия) растеризации. Различие и общие принципы должны быть ясны из рисунка 7 и 8 соответственно. Черные линии представляют вектор дороги на рисунках, квадраты представляют растровые пикселы, и серые пикселы - растрезацию дороги. Действительно важная вещь здесь это то, что связность сохраняется, то есть не должно быть никаких 'промежутков' при растрезации дороги.
Рисунок 7 - Доминирующий пиксел растра - тонкие линии
Рисунок 8 - Пересеченный пиксел растра - толстые линии
Возьмем грань, если источник и адресат (на грани) оба принадлежат растеризованной дороге, мы интерпретируем это как то, что имеется дорога, соединяющая их, и мы затем 'активизируем' модификатор пути. Как можно заметить на рисунках, растеризация 'тонкой линией' имеет намного лучше 'направленные' характеристики, так что это ясно привилегированный тип. Под направленными характеристиками, я обозначаю наличие свойства у 'граней дороги' направления в приблизительно том же самом направлении как первоначальный вектор дороги. Они, таким образом составляют однозначный путь, когда доминирующая растеризация пиксела используется, но не для пересеченной растеризации пиксела, Это иллюстрируются тонкими строками, представляющими 'интерпретируемые' грани дороги на рисунках 7 и 8. 5.1.2.3