Qual è il modo più efficace per trovare un insieme di posizioni entro un raggio di un certo punto?

Naviga le tue risposte
3

Immagina un set di dati di tutti i ristoranti negli Stati Uniti (simile a Yelp, ecc.), come faresti a restituire una serie di ristoranti all'interno di un certo intervallo di un particolare codice postale. (Supponendo che tu abbia già una funzione, distanceBetweenZipCodes, che calcola la distanza per te.)

Il metodo forza bruta sarebbe 

For each restaurant in restaurantsInUSA
  if(distanceBetweenZipCodes(restaurant.zipcode, user.zipcode) < walkingDistance)
    save restaurant

Tuttavia, sembra abbastanza inefficiente includere i ristoranti di New York nella ricerca se l'utente si trova in California. Ma è possibile che un ristorante si trovi vicino a una linea di stato, quindi segmentare i dati per stato sarebbe problematico. Si ottiene lo stesso problema se si tenta di segmentare per contee, città o altri confini amministrativi.

Quale sarebbe il modo più appropriato per segmentare i dati per evitare di dover controllare ogni record per tutte le ricerche?

    
posta takinola 26.05.2015 - 19:36
fonte

3 risposte

6

Hai scoperto la necessità di indicizzazione spaziale . R-trees sono probabilmente l'approccio più comune. L'idea di base è una struttura ad albero con rettangoli rettangolari calcolati su tutti i figli di un dato nodo. In questo modo la ricerca di una regione o di un punto può attraversare l'albero, potando qualsiasi parte dell'albero (la maggior parte di esso) in cui il riquadro di delimitazione non è una corrispondenza.

Questo è implementato in varie librerie, compresi i database SQL PostgreSQL e SQLite (con modulo) e la libreria C ++ boost :: geometry.

    
risposta data 26.05.2015 - 20:14
fonte
0

Calcola le distanze tra i codici postali una volta e memorizzale nella cache. Mantieni la lista dei ristoranti in ordine di distanza all'utente. Enumerando i ristoranti a partire dalla distanza più piccola è possibile rilevare il punto in cui i ristoranti escono da un raggio di azione a piedi - a quel punto puoi ignorare il resto e interrompere il ciclo.

    
risposta data 27.05.2015 - 21:26
fonte
0

Un quadtree (o octree in 3 dimensioni) è anche un bene per l'indicizzazione spaziale.

    
risposta data 28.05.2015 - 06:21
fonte

Leggi altre domande sui tag

Quali caratteristiche ha il software facilmente modificabile da altri sviluppatori 6+ mesi dopo il rilascio iniziale? [chiuso] Devo fornire il codice sorgente per le dipendenze GPL?