Поиск кратчайшего маршрута с обходом препятствий

Алгоритм

1. По заданным параметрам (сторона квадрата, отступ от начала координат) произвольным образом генерируются точки, они же - окружности
2. Строятся все возможные, не пересекающие другие окружности и границы, касательные к и между окружностями
3. У каждой окружности точки касания соединяются дугами
4. Из дуг, касательных и их длин составляется взвешенный граф
5. С помощью алгоритма Дейкстры ищется кратчайший маршрут
6. Происходит отрисовка сцены

Подробности реализации

Прога написана на Python 3.6.4 с использованием pygame для отрисовки и NetworkX для работы с графами (да, я поленился писать свой велосипед).

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

Что готово

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

... ... ...

о, готово

Чего нет

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

Как запустить

Понадобится

• Python 3
• Pygame
• NetworkX
• NumPy

Опционально:

• nxpd (для отрисовки графа картинкой)
• colored_traceback (разукрашенный вывод ошибок, а то скучно)

Полная версия в requirements.txt

Запуск

Если у вас Linux, то, в принципе, после установки зависимостей командой

pip3 install <requirement>

можно запустить программу командой make. По крайней мере, у меня работает.

Если у вас не Linux, то тут я должен признаться, что мне лень проверять работу на других системах, но, если надо, я попробую что-то с этим сделать.

Что где

• src/

  • main.py - тут происходит отрисовка, вызов функций и тут задаются параметры
  • generator.py - тут генерируются координаты точек
  • classes.py - тут описание классов
  • calculations.py - тут всякие побочные _вычисления _типа расстояний и проверок на пересечения
  • tangent.py - тут ищутся касательные
  • graph.py - тут просто из кусочков сращивается граф

• png/

  • fig.png - это просто картинка из данного Readme

• gens/

  • gens/circlelist.gen - этот файлик появляется и обновляется при каждом запуске, сюда складываются координаты точек. Просто почитать.

---

Is this it?