Оптимальный Поисковик Путей

Краткое описание

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

Возможности алгоритма

Наша библиотека предоставляет возможность построения наиболее оптимального маршрута между двумя точками на карте. Она обладает следующими основными функциями:

Поиск оптимального пути на карте, учитывая тропы и препятствия: Мы принимаем во внимание не только дороги, но и внедорожные пути, такие как тропы, пешеходные дорожки и препятствия, которые могут повлиять на выбор оптимального пути.
Поиск оптимального пути только по дорогам: Если вам нужно найти маршрут исключительно по дорогам, мы предоставляем эту возможность. Это полезно, например, для транспортных средств, которым разрешено передвигаться только по дорогам.
Установка различных скоростей для дорог: Мы можем назначать разные скорости разным дорогам. Например, более высокие скорости могут быть установлены для основных автомагистралей и более низкие скорости для узких переулков.
Установка прямоугольных препятствий: Вы можете определить прямоугольные препятствия на карте, которые необходимо учитывать при построении оптимального пути. Это полезно, когда есть известные препятствия, такие как здания или озера (их приближение).
Ограничение радиуса поиска для дорог: Вы можете ограничить радиус поиска для дорог, чтобы сократить время поиска и сосредоточиться только на определенной области.
Контроль производительности и точности: Мы предоставляем возможность контролировать производительность и точность алгоритма. Вы можете настроить его для достижения желаемого баланса между скоростью поиска и точностью построения маршрута.

Далее мы предоставим более подробное описание каждой из этих функций и рассмотрим примеры их применения.

Подход к решению

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

В нашей реализации мы использовали модифицированный алгоритм Ли. У нас есть сетка ячеек на плоскости. От начальной точки волна распространяется в 8 направлениях (включая диагонали) к соседним ячейкам, вычисляя время, необходимое для достижения каждой из них. Соседняя ячейка может содержать препятствие или дорогу. Дороги могут иметь разные коэффициенты скорости. Таким образом, мы “маркируем” нашу сетку временем, необходимым для достижения каждой ячейки от начальной ячейки в пределах определенного радиуса или до достижения конечной точки. Если мы достигнем конечной точки, мы построим обратный путь, используя нашу сетку.

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

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

Демо-проект на GitHub

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

Пример состоит из следующих шагов:

Создание списка информации о дорогах (RoadInfo), который включает информацию об участке дороги (Segment) и скорости движения (Velocity).
Добавление быстрых дорог в список.
Добавление медленных кольцевых дорог в список.
Создание генератора слоев путей (WayLayerGenerator) и добавление дорог в генератор.
Поиск нескольких путей от начальной точки (startPoint) к конечным точкам (goalPoint01, goalPoint02, goalPoint03) с использованием указанного радиуса (radius).
Подготовка слоя дорог (roadsLayer) для отображения на карте и добавление объектов дорог.
Подготовка слоя путей (wayLayer) для отображения на карте и создание геометрических объектов для каждого найденного пути.
Отображение карты с использованием функции ShowMap, сохранение карты по указанному пути.

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

Параметры поиска

Поиск пути выполняется с использованием класса WayLayerGenerator, расположенного в пространстве имен Aspose.Gis.GeoTools.WayAnalyzer.

Класс WayLayerGenerator имеет метод FindTheWay для поиска пути от начальной точки к целевой. Чтобы создать экземпляр класса WayLayerGenerator, мы передаем WayOptions в качестве параметров (все параметры необязательны):

StartPoint: Начальная точка
GoalPoint: Целевая точка
Radius: Радиус поиска
Scale: Масштаб сетки
IsMoveOnlyRoad: Указывать ли поиск пути только по дорогам

Заметной особенностью здесь является параметр Scale. Если он указан в конструкторе, мы фиксируем постоянный масштаб для последующих поисков. Если параметр Scale не установлен, но StartPoint и GoalPoint установлены, мы вычисляем масштаб как расстояние между начальной и конечной точками, деленное на 100. Во всех остальных случаях значение по умолчанию Scale равно 1. Для опытных пользователей лучше установить Scale или установить StartPoint и GoalPoint напрямую для наиболее эффективного представления дорог и препятствий в сетке (особенно если их много).

Чтобы использовать метод FindTheWay, нам нужно указать начальную и конечную точки. Мы также можем установить радиус поиска (расстояние, на которое распространяется волна). По умолчанию радиус рассчитывается как расстояние между начальной и конечной точками, умноженное на 3. Начальные и конечные точки могут быть близки или очень далеки друг от друга, поэтому, исходя из расстояния между ними, мы вычисляем масштаб нашей сетки. Если текущий масштаб не соответствует предыдущему, мы пересчитываем сетку. Масштаб можно зафиксировать с помощью параметра Scale. В этом случае он не вычисляется и сетка не пересчитывается.

Прежде чем начать поиск, нам нужно определить карту дорог и препятствий, используя соответствующие методы AddRoad и AddBlock класса WayLayerGenerator.

Для метода AddRoad нам нужно указать:

startPoint: Начальная точка дороги
endPoint: Конечная точка дороги
velocity: Скорость движения по дороге

Для метода AddBlock нам нужно указать:

x: X-координата верхнего левого угла блока
y: Y-координата верхнего левого угла блока
sizeX: Размер по оси X
sizeY: Размер по оси Y

Эти методы позволяют нам определить карту дорог и препятствий перед началом процесса поиска пути.

Примеры кода

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

Пример 1: Поиск пути между начальной и конечной точками.

WayOptions mapGeneratorOptions = new WayOptions();
var generator = new WayLayerGenerator(mapGeneratorOptions);
Point startPoint = new Point(5, 7);
Point goalPoint = new Point(15, 13);
var resultWay = generator.FindTheWay(startPoint, goalPoint);

Пример 2: Установка параметра Scale и наличие отрицательных координат для точки.

WayOptions mapGeneratorOptions = new WayOptions(1);
var generator = new WayLayerGenerator(mapGeneratorOptions);
Point startPoint = new Point(-50, -70);
Point goalPoint = new Point(150, 130);
var resultWay = generator.FindTheWay(startPoint, goalPoint);

Пример 3: Установка параметра IsMoveOnlyRoad и радиуса поиска.

WayOptions mapGeneratorOptions = new WayOptions();
mapGeneratorOptions.IsMoveOnlyRoad = true;
var generator = new WayLayerGenerator(mapGeneratorOptions);
generator.AddRoad(new Point(100, 100), new Point(140, 150), 10);
generator.AddRoad(new Point(140, 150), new Point(190, 100), 10);
Point startPoint = new Point(100, 100);
Point goalPoint = new Point(190, 100);
var resultWay = generator.FindTheWay(startPoint, goalPoint, 100);

Пример 4: Установка параметра Scale для более быстрого поиска.

WayOptions mapGeneratorOptions = new WayOptions(10);
var generator = new WayLayerGenerator(mapGeneratorOptions);
Point startPoint = new Point(50, 70);
Point goalPoint = new Point(1650, 1300);
var resultWay = generator.FindTheWay(startPoint, goalPoint, 2500);

Пример 5: Пример множественного поиска.

WayOptions mapGeneratorOptions = new WayOptions();
var generator = new WayLayerGenerator(mapGeneratorOptions);
generator.AddBlock(200, 1700, 1500, 100, 0);
generator.AddBlock(1700, 200, 100, 1600, 0);
generator.AddBlock(200, 200, 1500, 100, 0);
generator.AddRoad(new Point(1000, 1150), new Point(200, 600), 10);
generator.AddRoad(new Point(50, 450), new Point(150, 1850), 10);

Point startPoint = new Point(1000, 1000);
Point goalPoint = new Point(1900, 1000);
var resultWay = generator.FindTheWay(startPoint, goalPoint, 3500);

Point startPoint = new Point(50, 50);
Point goalPoint = new Point(70, 70);
var resultWay = generator.FindTheWay(startPoint, goalPoint);

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

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