Търсач на оптимален път

Резюме

Търсенето на най-краткия път в пътна мрежа е процес на анализ, насочен към определяне на най-ефективния начин за пътуване между точки на картата. Този инструмент може да бъде полезен за създаване на оптимални маршрути с множество спирки или измерване на разстоянието и времето за пътуване между различни местоположения. С всяко обаждане нашата технология може да намира оптимални маршрути за един или няколко автомобила. Например, тя може да помогне на шофьорите да намират оптималните маршрути за доставка на стоки или да определи оптималното разстояние от дома до работата за различни пътници.

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

Нашата библиотека предоставя възможността за изграждане на най-оптималния маршрут между две точки на картата. Тя има следните основни характеристики:

  1. Търсене на оптимален път на картата, като се вземат предвид пътеки и препятствия: Ние отчитаме не само пътищата, но и офроуд пътеките, като пътеки, пешеходни алеи и препятствия, които могат да повлияят на избора на оптималния път.

  2. Търсене на оптимален път само по пътища: Ако трябва да намерите маршрут изключително по пътищата, ние предоставяме тази възможност. Това е полезно, например, за превозни средства, които са ограничени да се движат само по пътищата.

  3. Задаване на различни скорости за пътища: Ние имаме способността да присвояваме различни скорости на различните пътища. Например, по-високи скорости могат да бъдат зададени за основни магистрали и по-ниски скорости за тесни алеи.

  4. Задаване на правоъгълни препятствия: Можете да дефинирате правоъгълни препятствия на картата, които трябва да бъдат взети предвид при изграждането на оптималния път. Това е полезно, когато има известни препятствия като сгради или езера (тяхното приближение).

  5. Ограничаване на радиуса на търсене за пътища: Можете да ограничите радиуса на търсене за пътища, за да намалите времето за търсене и да се фокусирате само върху определена област.

  6. Контрол на производителността и точността: Ние предоставяме възможност за контрол на производителността и точността на алгоритъма. Можете да го настроите фино, за да постигнете желаното равновесие между скоростта на търсене и точността на изграждане на маршрута.

След това ще предоставим по-подробно описание на всяка от тези функции и ще разгледаме примери за техните приложения.

Подход към решението

Въпреки че намирането на път е нетривиална задача, има няколко добри и надеждни алгоритми, които са признати в общността за разработка.

В нашата реализация използвахме модифициран алгоритъм на Лий. Имаме мрежа от клетки върху равнина. От началната точка се разпространява вълна в 8 посоки (включително диагонали) към съседни клетки, изчислявайки времето, необходимо за достигане до всяка от тях. Съседна клетка може да съдържа препятствие или път. Пътищата могат да имат различни коефициенти на скоростта. По този начин „маркираме“ нашата мрежа с времето, необходимо за достигане до всяка клетка от началната клетка в рамките на определен радиус или до достигане на крайната точка. Ако достигнем крайната точка, изграждаме обратен път, използвайки нашата мрежа.

За да се определи оптималният маршрут по пътната мрежа, трябва да се предприемат няколко стъпки. Първо, трябва да дефинирате пътищата и да посочите скоростта на движение по всеки от тях. Трябва също така да вземете предвид наличието на изкуствени и естествени препятствия, които могат да повлияят на преминаването през пътя. След това трябва да определите началните и крайните точки на търсенето. Веднъж щом тези предварителни стъпки са изпълнени, можете да преминете към действителното намиране на път. Резултатът ще бъде път, представен например като списък от координати на точки.

Важно е да се отбележи, че оптималният път може да зависи от избрания вид транспорт, тъй като скоростта на движение и наборът от препятствия могат да варират. Следователно, различни набори от пътища и препятствия трябва да бъдат използвани за всеки тип транспорт при търсене на оптимален път.

Демо проект в GitHub

За да разберете по-добре функционалността на нашата библиотека, нека разгледаме пример за нейната употреба. Този код илюстрира как да настроите пътища и препятствия в алгоритъма за намиране на път и да намерите оптималния маршрут.

Примерът се състои от следните стъпки:

  1. Създаване на списък с информация за пътя (RoadInfo), който включва информация за сегмента на пътя (Segment) и скоростта на движение (Velocity).
  2. Добавяне на бързи пътища към списъка.
  3. Добавяне на бавни пръстеновидни пътища към списъка.
  4. Създаване на генератор на слоеве от пътища (WayLayerGenerator) и добавяне на пътища към генератора.
  5. Търсене на множество пътища от началната точка (startPoint) до крайните точки (goalPoint01, goalPoint02, goalPoint03), използвайки посочения радиус (radius).
  6. Подготовка на слой с пътища (roadsLayer) за показване на картата и добавяне на пътни обекти.
  7. Подготовка на слой от пътища (wayLayer) за показване на картата и създаване на геометрични обекти за всеки намерен път.
  8. Показване на картата с помощта на функцията 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);

Тези примери за код изграждат и показват пътища на картата за определени точки, използвайки информация за пътя и генератор на слоеве от пътища.

В обобщение, търсачът на оптимален път е мощен инструмент за анализ на пътни мрежи и определяне на най-ефективните маршрути между точки на картата. Той взема предвид различни фактори като видове пътища, препятствия и различни скорости, за да изчисли оптималния път. С възможността за търсене на пътища както по пътищата, така и офроуд пътеките, както и контрол на радиуса на търсене и регулиране на производителността и точността, този алгоритъм предоставя универсално решение за оптимизация на маршрута. Като се вземат предвид различните видове транспорт и се коригират съответно наборите от пътища и препятствия, той може да бъде използван в различни сценарии като планиране на доставки или оптимизация на пътуването до работа.