Ваш ход мыслей правильный. Так и придётся делать. Пересечение геометрий стандартная геометрическая операция, есть во многих пространственных библиотеках (ST_Intersection). Ну и потом - выездов из городов всего несколько штук, можно заранее подготовить это выходы.