Zostałem o to zapytany w teście wywiadu. Na teście dobrze sobie radziłem, ale nie wiedziałem wystarczająco dużo, aby odpowiedzieć na to pytanie. Jestem ciekawy, jakich struktur danych mogę użyć do szybkiego zapytania danych.
Zasadniczo chodzi o to, że odcinki dróg (linie składające się z punktów) przechowywane są w jakiejś strukturze danych. Należy szybko sprawdzić, które odcinki drogi (lub punkty) znajdują się w pewnej odległości od punktu (promienia).
Odpowiedzi:
Typowym sposobem przechowywania danych geograficznych jest struktura danych przestrzennych, taka jak drzewo R (lub niektóre warianty, takie jak drzewo R +, drzewo R * itp.) W ten sposób typy danych geograficznych są zwykle implementowane w systemie GIS RDBMS. (Wiem, że zarówno SQL Server 2008 Microsoft, jak i PostGIS używają drzew R dla typów geograficznych.) Spełniają wszystkie podstawowe wymagania, które opisałeś, i trywialnie obsługują skrzyżowanie, lokalizację, odległość i inne typy zapytań.
W zależności od rodzaju danych można również znaleźć takie rzeczy, jak drzewa kD, drzewa czworokątne, ósemki, hierarchie objętości granicznych (w tym drzewa pól granicznych wyrównanych do osi) itp. Jest to w rzeczywistości znacznie bardziej powszechne w grach 3D, ponieważ rozmiar i kształt obiektu jest bardziej odpowiedni dla zapytań o skrzyżowanie. Są rzadziej używane do GIS niż R-drzewa.
źródło
Różne rodzaje operacji na danych mapy będą wymagały różnych formatów pamięci dla uzyskania optymalnych wyników. Rozważmy na przykład następujące trzy zadania:
Różnice w wymaganiach są na tyle duże, że o ile nie będzie konieczne uwzględnienie zmian „na żywo” na mapie, prawdopodobnie lepiej byłoby przechowywać trzy oddzielne kopie danych - każda zoptymalizowana do jednego z powyższych zadań - niż próbować wymyślić format, który dobrze poradzi sobie ze wszystkimi trzema zadaniami.
źródło