Поиск населенных пунктов на маршруте (алгор., php)

Есть маршрут между несколькими городами.

(строится с помощью гугл и яндекс карт). - соответственно есть координаты шагов по маршруту.

есть база городов с координатами (+ грубый прямоугольник границ города из геокодера).

необходимо реализовать на php быстрый(при десятках тысяч городов) алгоритм который найдет через какие города пройдет указанный маршрут.

Присылайте цены и сроки и если делали что либо подобное, тоже укажите.

Если имеете другое решение задачи - пишите, обсудим.