trovare case nel raggio

9

Durante un'intervista mi è stato chiesto quanto segue: Un'applicazione immobiliare che elenca tutte le case attualmente sul mercato (cioè in vendita) entro una determinata distanza (ad esempio, l'utente vuole trovare tutte le case entro 20 miglia), come progettereste la vostra applicazione (sia la struttura dei dati che l'alogiritmo) per costruire questo tipo di servizio?
Qualche idea? Come lo implementeresti? Gli ho detto che non lo sapevo perché non ho mai fatto nulla di geo-correlato prima.

    
posta paul smith 06.06.2012 - 09:40
fonte

4 risposte

6

Probabilmente sono dopo una risposta che menziona indicizzazione spaziale , molto probabilmente selezionando un database che fornisce l'indicizzazione spaziale fuori dalla scatola , ma potresti anche ottenere alcuni punti menzionando che può essere implementato nell'applicazione stessa se necessario ad es. implementando un R-Tree (potrebbe essere utile se la selezione del DB è risolta per altri motivi? ma ti dimostra anche sapere come funzionano i database spaziali). L'indicizzazione spaziale ti permetterà di ottenere rapidamente un sottoinsieme di posizioni che si adattano all'interno di una casella di ricerca, puoi perfezionarlo ulteriormente calcolando la distanza effettiva (se necessario, il rettangolo da solo potrebbe essere abbastanza buono ovviamente) per ciascuno di essi per dare una ricerca vera cerchio / ellisse

Dato che le distanze sono probabilmente pari o inferiori a 20M, probabilmente stai bene assumendo una terra piatta per calcolare la distanza, anche se inizierai a vedere errori evidenti verso la fine del 20M, se sono necessari intervalli molto più ampi dovresti iniziare a guardare migliori modelli di distanza per il globo es Distanza Haversine

ci sono naturalmente anche una miriade di altri dettagli che potrebbero essere discussi, ad es. Progettazione dell'interfaccia utente, schema DB che potrebbero essere argomenti interi a sé stanti

    
risposta data 06.06.2012 - 09:58
fonte
8

Ogni volta che ti trovi di fronte a una domanda come questa e semplicemente non hai esperienza nel dominio del problema, è bene fare un paio di cose.

Prima riconosce che non hai competenze specifiche in questo dominio problematico.

Secondo , spiega come andresti a risolvere il problema.

Although I don't have specific experience when working with geographical search I am confident there are well documented algorithms and existing technologies to solve the problem. I would explore these to gain knowledge of common solutions that are available to me and make a choice about implementation based on the requirements of the project.

Terzo , Riduci sempre i problemi come questo ai componenti di base. Sai che le posizioni su una mappa sono distribuite su 2 dimensioni. Sai che se ti viene assegnata una coordinata arbitraria, le coordinate di ogni distanza da un'altra coordinata vengono calcolate formando un triangolo e risolvendo la lunghezza sconosciuta. Spero anche tu sappia che se ti viene chiesto di trovare tutte le coordinate all'interno di un riquadro di delimitazione, puoi farlo semplicemente calcolando le estensioni della scatola che vuoi trovare e usando il semplice maggiore, minore della logica lungo entrambi gli assi.

Ultimo , non ho mai assunto uno sviluppatore che sembrava rinunciare alle domande. Se faccio una domanda e la persona dice "Non so" e non tenta nemmeno di pensarci verbalmente mi dà l'impressione che non contribuiranno alle sessioni di brainstorming - che è fondamentale per le organizzazioni che scrivono software .

    
risposta data 06.06.2012 - 19:29
fonte
4

Questo è probabilmente ovvio, ma per molte applicazioni la soluzione lenta del povero può andare bene.

Avere una tabella in un database relazionale che memorizza latitudine e longitudine. Query per tutte le posizioni che hanno una latitudine entro 20 miglia e una longitudine entro 20 miglia. Questo ti dà un rettangolo di delimitazione della dimensione del più piccolo rettangolo di delimitazione che contiene il raggio che vuoi veramente cercare (e ignora anche la curvatura della terra).

Quindi prendi il set che viene restituito (da una query utilizzando gli indici) e filtralo usando un calcolo accurato della distanza.

Quindi, prestazioni non efficienti, ma molto efficienti nel tempo per svilupparsi. Per molte applicazioni che potrebbero essere una scelta migliore.

    
risposta data 06.06.2012 - 19:23
fonte
2

Probabilmente il modo più semplice è utilizzare un quadrifoglio per memorizzare le posizioni delle tue case, assumendo che siano distribuite in un paesaggio 2D . La ricerca dovrebbe essere abbastanza semplice.

Se utilizzi un RDBMS abilitato GIS per archiviare i tuoi contenuti, non devi preoccuparti di questo. Vedi questa domanda per alcune informazioni sulle prestazioni dei giocatori principali .

    
risposta data 06.06.2012 - 09:58
fonte

Leggi altre domande sui tag