znajdowanie domów w promieniu

Podczas wywiadu poproszono mnie o następujące informacje: Aplikacja nieruchomości, która zawiera listę wszystkich domów, które są obecnie na rynku (tj. Na sprzedaż) w określonej odległości (np. Użytkownik chce znaleźć wszystkie domy w odległości 20 mil), jak zaprojektowałbyś swoją aplikację (zarówno strukturę danych, jak i alogirithm), aby zbudować ten rodzaj usługi?

Jakieś pomysły? Jak byś to wdrożył? Powiedziałem mu, że nie wiem, ponieważ nigdy wcześniej nie robiłem żadnych rzeczy związanych z geo.

Są prawdopodobnie po odpowiedzi na temat indeksowania przestrzennego , najprawdopodobniej poprzez wybranie bazy danych, która zapewnia indeksowanie przestrzenne po wyjęciu z pudełka , ale możesz również uzyskać kilka punktów, wspominając, że można je zaimplementować w samej aplikacji, jeśli to konieczne, np. Poprzez wdrożenie R -Drzewo (może być przydatne, jeśli wybór DB jest ustalony z innych powodów? Ale pokazuje również, jak wiesz, jak działają przestrzenne bazy danych). Indeksowanie przestrzenne pozwoli ci szybko uzyskać podzbiór lokalizacji, które mieszczą się w polu wyszukiwania, możesz to uściślić, obliczając rzeczywistą odległość (w razie potrzeby sam prostokąt może być wystarczająco dobry) dla każdego z nich, aby zapewnić prawdziwe wyszukiwanie okrąg / elipsa

Biorąc pod uwagę, że odległości wynoszą prawdopodobnie 20 M lub mniej, prawdopodobnie jesteś w porządku, zakładając, że płaska ziemia oblicza odległość, chociaż zaczniesz widzieć zauważalne błędy w kierunku końca 20 M, jeśli dokładnie potrzebne są znacznie większe odległości, musisz również zacząć szukać lepszych modeli odległości dla świata, np. odległość Haversine

istnieją również niezliczone inne szczegóły, które można omówić, np. projektowanie interfejsu użytkownika, schemat DB, które mogą stanowić całe tematy same w sobie

Ilekroć masz takie pytanie i po prostu nie masz doświadczenia w dziedzinie problemów, dobrze jest zrobić kilka rzeczy.

Po pierwsze, potwierdź, że nie masz specjalistycznej wiedzy w tej dziedzinie problemów.

Po drugie , wyjaśnij, jak byś rozwiązał problem.

Chociaż nie mam specjalnego doświadczenia w pracy z wyszukiwaniem geograficznym, jestem pewien, że istnieją dobrze udokumentowane algorytmy i istniejące technologie rozwiązania problemu. Zbadałbym je, aby uzyskać wiedzę na temat popularnych rozwiązań, które są dla mnie dostępne, i dokonać wyboru wdrożenia w oparciu o wymagania projektu.

Po trzecie , zawsze ograniczaj takie problemy do ich podstawowych komponentów. Wiesz, że lokalizacje na mapie są rozmieszczone w dwóch wymiarach. Wiesz, że jeśli otrzymasz dowolną współrzędną x, y odległość do każdej współrzędnej od innej współrzędnej jest obliczana przez utworzenie trójkąta i rozwiązanie dla nieznanej długości. Mamy nadzieję, że wiesz również, że jeśli zostaniesz poproszony o znalezienie wszystkich współrzędnych w obwiedni, możesz to zrobić, po prostu obliczając zakres tego pola i używając prostej większej niż, mniejszej niż logika wzdłuż obu osi.

Wreszcie , nigdy nie zatrudniłem programisty, który wydawał się rezygnować z pytań. Jeśli zadam pytanie, a osoba powie „nie wiem”, a nawet nie spróbuje go przemówić werbalnie, mam wrażenie, że nie wezmą udziału w sesjach burzy mózgów - co jest niezwykle ważne w organizacjach tworzących oprogramowanie .

Jest to prawdopodobnie oczywiste, ale dla wielu aplikacji powolne rozwiązanie biedaka może być w porządku.

Mieć tabelę w relacyjnej bazie danych, która przechowuje szerokość i długość geograficzną. Zapytanie dla wszystkich lokalizacji, które mają szerokość geograficzną w odległości 20 mil i długość geograficzną w odległości 20 mil. Daje to prostokąt ograniczający rozmiar najmniejszego prostokąta ograniczającego, który zawiera promień, który naprawdę chcesz wyszukać (i ignoruje również krzywiznę ziemi).

Następnie bierzesz zestaw, który jest zwracany (przez zapytanie za pomocą indeksów), i filtrujesz go, używając dokładnego obliczenia odległości.

Tak więc, nie wydajna wydajność, ale bardzo wydajna w czasie do rozwoju. W przypadku wielu aplikacji może to być lepszy wybór.

Prawdopodobnie najłatwiejszym sposobem jest użycie kwadratu do przechowywania lokalizacji domów, przy założeniu, że są rozmieszczone w krajobrazie 2D. Wyszukiwanie powinno być dość proste.

Jeśli używasz RDBMS z obsługą GIS do przechowywania swoich rzeczy, naprawdę nie musisz się tym martwić. Zobacz to pytanie, aby uzyskać informacje na temat wyników głównych graczy.