Idealna struktura danych do przechowywania danych map?

12

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).

algorithms data-structures

— Keyo
źródło

Aby naprawdę dowiedzieć się więcej, przeczytałbym na: cgal.org , a następnie spojrzałem na te projekty: cgal.org/projects.html#gis , znajdź ten, który jest podobny do tego, czego chcesz, a następnie przestudiuj użycie interfejsu API i na koniec makijaż API.

— Job

16

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.

— greyfade
źródło

0

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:

Podając punkt, znajdź drogę najbliższą tego punktu
Biorąc pod uwagę obszar geograficzny o określonej wielkości, znajdź wszystkie drogi, które znajdują się w tym obszarze.
Przy dwóch drogach znajdź najkrótszą trasę między nimi.

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.

— supercat
źródło