Я ищу предложения по идеальной базе данных или структуре данных для хранения карты. По сути, , карта состоит из "путей", которые похожи на дороги, пути и т. д. Пути содержат узлы (которые имеют координаты широты и долготы, а иногда и высота.)
Любая такая база данных или структура:
должна иметь возможность быстро определять местонахождение всех узлов в ограничивающей рамке (миллисекунды)
опционально, не должна значительно замедляться при большом количестве узлов находятся в ограничивающей рамке по сравнению с небольшим количеством узлов, или, если ограничивающая рамка большая
, должна иметь возможность находить узлы, которые соединяются напрямую: например, узел, который соединяет два пути
, может быть доступен только для чтения
должен быть компактным (чтобы не тратить лишнее место) - я хочу разместить карту Великобритании менее чем на 1 ГБ. У меня есть спутниковая навигатор, которая делает это с примерно 800 МБ места на SD-карте.
Сначала я думал о четырехугольных деревьях для хранения путей. Но быстрая реализация сложна, и они не работают для отдельных узлов; все узлы помещаются в наименьший возможный bbox.
(I ' m намеренно использует ту же терминологию Open Street Map, потому что я планирую использовать эти данные.)