Come sapere, con buone prestazioni, su quali aree è presente un determinato punto? [duplicare]

Question

Come sapere, con buone prestazioni, su quali aree è presente un determinato punto? [duplicare]

#1 da (0 voti)

2

Sono interessato a costruire un prototipo che abbia bisogno di questo tipo di cose:

Punto A (xa, ya) con un raggio di 500 metri.
Punto B (xb, yb) con un raggio di 700 metri.
Punto C (xc, yc) con un raggio di 1200 metri.
Punto D (xd, yd) con un raggio di 200 metri.
La persona 123 si trova in un certo punto.

Domanda : quali sono i punti 123? Ad esempio, la persona si trova all'interno delle aree A, B e D, ma non su C.

Tutti i punti sono coordinate geografiche, cioè lat / long. Voglio capire quali sono i migliori algoritmi e strategie per implementare un buon indice. La mia idea attuale (non ancora implementata) è:

The hole map is divided in quadrants, small as (for example) 50~100 > meters. When a point is marked, all quadrants inside their area will > be marked as well. Then, when I search using "Person 123", I'll just > find its quadrant and retrieve all points marked into it.

Fondamentalmente costruirò un enorme albero di prefissi basato su geohashes di tutti i punti (+ 10k punti). Il problema è che, per un singolo punto, ci saranno numerose voci all'interno dell'albero (anche se sarebbe meglio per la ricerca, penso). Nota Mi manca la comprensione formale degli indici spaziali.

programming-practices performance algorithms

posta Lucas Sampaio 17.12.2013 - 18:18

fonte

1 risposta

Leggi altre domande sui tag programming-practices performance algorithms

Licenza per la (ri) distribuzione di fonti gratuite, ma nessuna distribuzione di eseguibili modificati Linee guida di architettura per una "web-app a pagina singola"

score 0 · Answer 1

Sebbene il Quadtree suggerito nei commenti sia la soluzione canonica, potresti riuscire a farla franca con il disegno che proponi tu stesso, tranne per il fatto che memorizzerei i punti in un dizionario basato su Hashtable. Il dizionario è bello in quanto costa solo spazio proporzionale con la quantità di Punti di interesse. Non hai bisogno di recuperare la memoria per il deserto del Sahara vuoto.

Definisci semplicemente uno schema di numerazione per i tuoi quadranti, e il numero del quadrante è quindi la chiave per la tabella hash. Per ogni quadrante si archivia una lista di POI nella tabella hash. Ciascuno dei tuoi punti di interesse otterrà una voce nell'elenco di POI in ciascuno dei quadranti che tocca.

Se riduci un po 'la risoluzione della tua griglia, questo ridurrà ulteriormente l'utilizzo della memoria, ma dovrai eseguire un'iterazione di più punti, soprattutto se sono vicini. Penso che la tua griglia attuale sia troppo densa dato che ogni colpo tocca circa 100 quadranti. mi sforzerò per una cifra inferiore a 10, in media.