Trova tutti i cerchi che coprono un punto

I was hoping there would be some kind of database optimization

I database con estensioni spaziali / geospaziali consentono di archiviare oggetti spaziali e operazioni di query veloci come "è il punto in una determinata area", supportati dai cosiddetti indici spaziali. L'insieme esatto di funzioni e la sintassi differiscono da DBMS a DBMS, ma non conosco un database che supporti direttamente oggetti circolari di diverso raggio. Ma se il tuo database spaziale supporta poligoni (che è piuttosto standard), puoi utilizzarlo per il tuo problema:

• per ogni cerchio, memorizza (in aggiunta al centro e al raggio) un poligono che racchiude il cerchio (per molti scopi pratici, il riquadro che lo racchiude è abbastanza buono).

• usa una query spaziale per ottenere tutte le cerchie in cui il punto specificato (x, y) è contenuto nel quadrato correlato. Se nel tuo database ci sono molte cerchie, questo potrebbe ridurre il numero di cerchi per un punto (x, y) a un importo molto inferiore

• per il set di risultati (si spera piccolo), prova manualmente la condizione "cerchio interno" scorrendo le cerchie

In effetti, devi verificare se beneficia di questa ottimizzazione in combinazione con i tuoi dati reali e se il sovraccarico aggiuntivo di memorizzazione dei poligoni che racchiudono è davvero la pena.

Vuoi trovare facilmente le cose in uno spazio bidimensionale. Questo è simile al problema più comune di trovare le cose in uno uno spazio dimensionale; la soluzione è quella di ordinare i dati e quindi trovare le cose in esso in O (log n) ora tramite ricerca binaria.

Non puoi fare esattamente la stessa cosa per i dati bidimensionali perché l'ordine non è lo stesso per le due dimensioni (un punto che è piuttosto piccolo per una dimensione potrebbe essere molto grande per l'altra). Ma ci sono molte generalizzazioni di ordinamento / indicizzazione che tuttavia ti faranno risparmiare un sacco di tempo nella pratica. La domanda è già stata posta su stackoverflow, qui .

I database hanno un tipo di indice speciale per questo tipo di ricerche basate su caselle di delimitazione minima, chiamate r-tree. Supponiamo di avere 1M posti definiti da x / y nel nostro database e vogliamo trovare tutti i punti in raggio dalla nostra posizione prima di tutto dobbiamo costruire MBR contenente il cerchio di ricerca (punto centrale in questo stesso punto e bordi 2r), dati di ricerca e nel passaggio successivo elimina i risultati posizionati negli angoli MBR utilizzando la semplice formula x*x+y*y < r*r . L'albero ad albero R-albero ha anche molte delle implementazioni in memoria per diverse lingue. Se vuoi risolvere il problema geografico, sarebbe un po 'più complesso dato che abbiamo il meridiano, la linea di cambio data e calcoli della distanza più complicati (grande cerchio).