Итак, я создаю приложение GPS. У меня есть коллекция объектов Road, каждый из которых содержит начальную и конечную точки (плюс другие промежуточные точки, где дорога изгибается). Я реализовал алгоритм Дейкстры для нахождения кратчайшего пути (где дороги являются узлами на графике), но прежде чем я смогу его запустить, мне нужно определить, какие дороги соседствуют (соединяются) друг с другом, чтобы создать ребра.
Простым (?) Способом было бы перебрать каждую дорогу и в рамках вложенного цикла посмотреть, начинаются ли / заканчиваются ли другие дороги в той же точке. Но это кажется неэффективным, будучи O (N ^ 2). Одна из идей заключалась в том, чтобы предварительно разделить дороги на регионы (то есть в Великобритании будет NW, NE, E, SE, SW и т. Д.), А затем искать только соседей в одном регионе, сокращая пространство поиска.
Ищите совета у опытных программистов, как бы вы решили эту проблему?
Это не домашнее задание, после того, как я недавно закончил, я работаю над этим как над домашним животным, чтобы получить некоторый практический опыт и немного добавить резюме.
Редактировать: я должен добавить только дороги, когда-либо соединяющиеся в начальной / конечной точках