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

Ваш вопрос можно интерпретировать двояко.

<сильный>1. Я хочу найти кратчайший путь, разрывая нити, выбирая путь(и) с наименьшим количеством ребер

Вы можете сделать это, добавив небольшое число ε к весу каждого ребра графа. Число должно удовлетворять ε < 1/numberOfEdges. Это увеличит длину каждого пути на ребра * ε, что означает, что более короткие пути будут предпочтительнее. Это работает даже с ребрами отрицательного веса. Будьте осторожны с неточностями с плавающей запятой.

<сильный>2. Я хочу найти путь с наименьшим количеством поворотов, разбивая ничьи, выбирая тот или иные пути с кратчайшим путем

Вы можете сделать это, добавив некоторое большое число E к весу каждого ребра на графе. Число должно удовлетворять E > sumOfAllEdgeWeights. Это гарантирует, что будут рассматриваться только пути с наименьшим возможным числом ребер. Это не работает с ребрами с отрицательным весом. Будьте осторожны с целочисленными переполнениями.

Если цель:

1) Минимизируйте количество ребер.

2) Минимизируйте расстояние.

В этом порядке вы можете попробовать следующее:

1) Проведите линию от начала до конца.

2) Рассчитайте каждый объект, с которым сталкивается ваша линия.

3) Для каждого из этих объектов вычислите обе точки, перпендикулярные объекту, которые позволят вам разделить путь на два сегмента пути. Вы можете сделать это для прямоугольников, разделив линию на два сегмента: для сегмента A посмотрите, через какой из четырех углов он может пройти, для сегмента B посмотрите, через какой из четырех углов он может пройти, и попробуйте все комбинации, пока не найдете два, которые дают наименьшее смещение. Для кругов я забыл, как это сделать, но есть только одно решение с обеих сторон, где два сегмента пути находятся на одном уровне с кругом, поэтому вы можете сделать это с помощью тригонометрии или чего-то еще (я попытаюсь понять это :))

Для обоих новых путей вызовите 4) в режиме рекурсивного ветвления.

4) Для обоих сгенерированных сегментов линии повторяйте расчет до тех пор, пока не останется столкновений. Как и в случае с A*, вы должны сначала вычислить пути, которые кажутся лучшими (с наименьшим количеством оставшихся столкновений, или сначала сделайте самый мелкий путь, если это слишком сложно).

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

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

РЕДАКТИРОВАТЬ

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

-Сторона A: идет от начала линии (или конца линии) xs,ys до центра круга xc,yc, длина = a

-Сторона B: идет от центра xc,yc куда-то по окружности, поэтому длина = r

-Сторона C: идет от конечной точки стороны B до xs,ys (гипотенуза)

Угол, образованный A и B, является прямым углом, и мы знаем длину A и B, поэтому мы можем вычислить длину C как sqrt (A ^ 2 + B ^ 2)

Наконец, мы знаем, что длина C = длина / грех (угол (от B до C)) = длина / грех B (угол (от A до C)), что означает, что мы можем выполнить тригонометрию, чтобы найти угол от A до C и угол B к С.

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