Shapely

Ciao, sono Alex di DEV STORIES DOT EU. Shapely, episodio 1 di 8. Probabilmente sei abituato a trattare le geometrie delle mappe come semplici liste di coordinate, usate principalmente per disegnare forme sullo schermo. Ma quando devi calcolare se una traccia GPS attraversa un confine specifico, la semplice logica di disegno non basta più. Per fare una vera analisi spaziale matematica, ti serve lo Spatial Data Model. Innanzitutto, dobbiamo chiarire una fonte comune di confusione riguardo a questo modello. Shapely opera rigorosamente su un piano cartesiano bidimensionale piatto. Puoi fornire le coordinate X, Y e Z quando crei le tue geometrie. Shapely ne farà il parse e salverà persino quel valore Z in memoria. Ma ignora completamente la coordinata Z durante qualsiasi analisi spaziale. Se chiedi la distanza tra due punti, Shapely calcola la distanza 2D piatta. Non calcola volumi 3D o distanze 3D. È una libreria puramente planare. Ecco il punto chiave. Shapely si basa sulla teoria matematica degli insiemi di punti. Non vede una forma solo come la manciata di vertici che hai digitato nel tuo codice. Al contrario, tratta ogni geometria come un insieme rigoroso che contiene un numero infinito di punti. Secondo questo modello, ogni geometria divide l'intero piano 2D in tre parti distinte. L'interior è la sostanza vera e propria della forma. Il boundary è il bordo che incornicia la forma. L'exterior è il resto del piano infinito che non fa parte della forma. Prova a modellare un parco cittadino per vedere come si applicano questi tre concetti. Inizi con una fontana, rappresentata come una geometria Point. Un Point è zero-dimensionale. Rappresenta una singola posizione esatta sul piano. Dato che non ha lunghezza o area, il suo interior è costituito solamente da quella specifica coordinata. Un Point non ha alcun boundary. Ogni altra coordinata sull'intero piano cartesiano costituisce il suo exterior. Poi, aggiungi un sentiero pedonale che porta alla fontana. Questo viene modellato come una LineString. Una LineString è una geometria unidimensionale definita da una sequenza ordinata di vertici di coordinate. Anche se le passi solo una coordinata di inizio e una di fine, Shapely interpreta la LineString come l'insieme infinito di punti che formano il percorso continuo tra di esse. L'interior è l'intera lunghezza continua del percorso. Il boundary è costituito esattamente da due punti: la prima coordinata di inizio e l'ultima coordinata di fine. Infine, modelli l'impronta del parco stesso usando un Polygon. Un Polygon è una geometria bidimensionale con un'area misurabile. Lo definisci usando un anello chiuso di coordinate, il che significa che il primo e l'ultimo punto sono identici. Questo anello esterno forma il boundary del Polygon. L'interior è l'insieme infinito di punti racchiusi all'interno di quel boundary. I Polygon possono anche contenere dei buchi, come ad esempio una zona di conservazione protetta all'interno del parco. Il bordo di quel buco funge semplicemente da boundary interno, separando nettamente l'interior valido del parco dallo spazio exterior vuoto all'interno del buco. Shapely non vede la tua geometria come un wireframe vuoto di coordinate; la vede come una regione continua di spazio divisa matematicamente in interior, boundary ed exterior. Se trovi utili questi episodi e vuoi supportare lo show, cerca DevStoriesEU su Patreon. Questo è tutto per questa volta. Grazie per l'ascolto e continua a sviluppare!

Ciao, sono Alex di DEV STORIES DOT EU. Shapely, episodio 2 di 8. Stai elaborando un batch di coordinate spaziali. Scrivi un loop per trasformare ogni coppia di coordinate in una shape, una alla volta. Funziona, ma quando il tuo dataset cresce fino a milioni di punti, la tua applicazione si blocca completamente. Il problema è l'overhead di Python, e la soluzione richiede di bypassare completamente la creazione standard degli oggetti. Questo episodio parla di Geometry Creation e Serialization. Creare le shape è il punto di partenza logico. Se hai a che fare con una singola posizione, istanziare una geometria è semplice. Importi la singola classe Point e le passi un valore X e Y. È facile da leggere, ma è lento. Ecco il punto chiave. Shapely fornisce funzioni universali vettorializzate che operano direttamente sugli array NumPy. Invece di usare la singola classe Point in un loop Python, usi la funzione plurale shapely dot points. Le passi un array bidimensionale di coordinate, e l'intera iterazione viene spinta giù al livello C, che è altamente ottimizzato. Il risultato è un array di oggetti geometry restituito in una frazione del tempo. Questo vale su tutta la linea, con funzioni plurali disponibili per line string, polygon e linear ring. Mettiamo che tu stia costruendo un routing tool e debba caricare un dataset di mille punti di consegna. I dati arrivano come un array di payload GeoJSON. Questo ci porta alla serialization. Devi fare il parsing di quelle stringhe in veri e propri oggetti geometry in memoria. Potresti essere tentato di usare il parsing JSON standard ed estrarre le coordinate manualmente per costruire le tue shape. Non farlo. Shapely ha funzioni di input e output integrate per i tre principali formati spaziali: Well-Known Text, Well-Known Binary e GeoJSON. Come per la geometry creation, anche queste funzioni di parsing sono vettorializzate. Prendi il tuo intero array di mille stringhe GeoJSON e lo passi direttamente alla funzione shapely dot from geojson. Fa il parsing dell'intero batch in una volta sola e restituisce un array di geometrie ad alte performance. Se i tuoi dati fossero in formato testo, useresti shapely dot from wkt. Se fossero in formato binario, useresti shapely dot from wkb. Questo copre gli input. E per gli output? Una volta finito di processare i tuoi punti di consegna, devi salvarli o inviarli a un database. Inverti il processo usando le funzioni di export. Se stai facendo debug e hai bisogno di leggere le coordinate con i tuoi occhi, usi shapely dot to wkt. Il Well-Known Text ti dà una stringa human-readable, che esplicita il tipo di geometria seguito dalle coordinate. Tuttavia, il parsing del testo è costoso e occupa spazio. Se stai inviando questi dati a un database spaziale, o li stai salvando per dopo, dovresti usare shapely dot to wkb. Il Well-Known Binary è la rappresentazione in raw byte della geometria. È significativamente più piccolo, evita la perdita di precisione dovuta alla conversione da floating-point a stringa, ed è molto più veloce da leggere e scrivere per le macchine. Passi il tuo array di geometrie a shapely dot to wkb, e ottieni un array di byte string pronte per lo storage. Ogni volta che sposti dati spaziali dentro o fuori dalla tua applicazione, ricorda che i loop Python sono il nemico. L'abitudine più importante per le performance è dare in pasto array completi alle funzioni plurali di Shapely, lasciando che la libreria C sottostante faccia il lavoro pesante in un singolo passaggio. Grazie per l'ascolto, happy coding a tutti!

Ciao, sono Alex di DEV STORIES DOT EU. Shapely, episodio 3 di 8. La distanza standard ti dice quanto due linee si avvicinano tra loro. Ma se vuoi conoscere la distanza massima assoluta a cui si allontanano, la distanza standard è completamente inutile. Per rispondere a questa domanda, devi capire Measurement e Properties. Ogni oggetto geometry in Shapely ha degli attributi built-in che ne descrivono le dimensioni fisiche. I più basilari sono area, length e bounds. La property area ti dà lo spazio bidimensionale coperto da una forma. Per un poligono, questo è un numero positivo. Per punti e linee, l'area è esattamente zero. La property length restituisce l'estensione unidimensionale di una geometry. Per una linea, è la distanza dall'inizio alla fine lungo il percorso. La property bounds fornisce i limiti esatti delle coordinate della tua forma. Restituisce una tuple di quattro numeri che rappresenta la X minima, la Y minima, la X massima e la Y massima. Questo è il tuo bounding box. Considera uno scenario in cui hai due tracce GPS di corridori, entrambe rappresentate come LineString. Leggi la property length per vedere la distanza totale percorsa da ciascuna persona. Leggi la property bounds per definire l'esatta viewport rettangolare necessaria per visualizzare entrambi i loro percorsi su uno schermo. La matematica diventa più pesante quando devi misurare lo spazio tra quelle due tracce. La misurazione della distanza standard restituisce il gap più corto in assoluto tra due geometry. Scansiona la traccia A, scansiona la traccia B e trova la singola coppia di punti più vicina. Se i due corridori si sono incrociati a un incrocio a metà della loro corsa, la distanza standard tra le loro tracce è zero. Ecco il punto chiave. Le persone spesso confondono la distanza standard con la distanza di Hausdorff. La distanza standard trova i punti più vicini. La distanza di Hausdorff trova la distanza massima tra i punti più vicini. Pensa alla distanza di Hausdorff come alla misurazione della deriva massima. Rappresenta il gap più lungo che saresti costretto ad attraversare se qualcuno ti mettesse nel punto peggiore possibile su una traccia e ti dicesse di camminare fino al punto più vicino sull'altra traccia. Se i nostri due corridori sono partiti dallo stesso posto, si sono separati di due miglia a metà del loro allenamento e hanno finito nello stesso posto, la distanza standard è zero. La distanza di Hausdorff è di due miglia. Definisce la separazione nel caso peggiore lungo l'intera lunghezza delle due geometry. C'è un'altra funzione di misurazione chiamata minimum clearance. Questa non confronta due oggetti diversi. Misura la stabilità strutturale di una singola geometry. La minimum clearance calcola la distanza più piccola di cui qualsiasi node può spostarsi prima che la geometry collassi in uno stato non valido, come una linea che si sovrappone a se stessa. Se la tua geometry ha una minimum clearance minuscola, le coordinate sono schiacciate strettamente insieme. Un leggero errore di arrotondamento durante un database export potrebbe rompere completamente la forma. Se vuoi semplificare i dati dei corridori per risparmiare sulle dimensioni del file, controllare la minimum clearance ti dice esattamente di quanto puoi spostare i punti prima che la geometry si rovini. Sapere quanto due forme si avvicinano gestisce le collisioni di base. Conoscere il limite massimo assoluto della loro separazione detta quanto tu capisca veramente la relazione spaziale tra di loro. Grazie per aver passato qualche minuto con me. Alla prossima, stammi bene.

Ciao, sono Alex di DEV STORIES DOT EU. Shapely, episodio 4 di 8. Stai progettando il tracciato di una nuova linea della metropolitana vicino a una zona umida protetta. Devi sapere se il binario attraversa l'acqua in linea retta o se la costeggia soltanto. Come fa il computer a capirlo matematicamente? Utilizza un'ingegnosa matrice tre per tre per rispondere alla domanda. Questo ci porta agli spatial predicate e al Dimensionally Extended nine-Intersection Model, o DE-9IM. Gli spatial predicate sono funzioni binarie. Confrontano due geometrie e restituiscono esattamente una cosa: True o False. Non creano nuove forme. Non calcolano le aree di sovrapposizione. Rispondono semplicemente a domande da sì o no sulle relazioni topologiche. Dietro le quinte, Shapely valuta queste relazioni usando il DE-9IM. Ogni geometria ha tre parti: un interior, un boundary e un exterior. Il DE-9IM è una matrice che testa le intersezioni tra queste tre parti della prima geometria e le tre parti della seconda geometria. Tre parti per tre parti ti danno nove possibili intersezioni. A seconda di quali di queste intersezioni diano come risultato un insieme vuoto, un punto, una linea o un'area, Shapely determina la relazione esatta. Applichiamo questo concetto alla linea della metropolitana e alla zona umida. Lo spatial predicate più ampio è intersects. Se il tracciato condivide un punto, una linea o un'area con la zona umida, intersects restituisce True. È il catch-all di base. Se intersects è False, le due geometrie sono completamente separate nello spazio. Ma spesso hai bisogno di maggiore precisione. Vuoi sapere se la linea della metropolitana attraversa effettivamente la zona umida. Per questo, usi crosses. Una linea attraversa un poligono se il suo interior interseca l'interior del poligono, ma la linea si estende anche all'exterior del poligono. La matrice DE-9IM controlla che l'intersezione dei loro interior sia una linea, e che l'interior della linea intersechi anche l'exterior del poligono. Se entrambe le condizioni sono vere, crosses restituisce True. E se il tracciato corresse esattamente lungo il confine della zona umida senza entrare in acqua? È qui che entra in gioco touches. Due geometrie si toccano se condividono almeno un punto, ma i loro interior non si intersecano affatto. Interagiscono solo i loro boundary. Se il tracciato devia anche solo di un millimetro nell'interior della zona umida, touches diventa False. Ora considera una stazione della metropolitana costruita interamente all'interno della zona umida. Qui, controlli il containment. Spesso si confondono contains e within, ma sono semplicemente operazioni inverse l'una dell'altra. Se la zona umida contains la stazione, allora la stazione è within la zona umida. Geometricamente, significa che l'interior e il boundary della stazione sono interamente racchiusi dall'interior della zona umida. Nessuna parte della stazione interseca l'exterior della zona umida. Puoi scrivere il tuo codice controllando se la zona umida contains la stazione, o controllando se la stazione è within la zona umida. Il risultato è esattamente lo stesso. Ecco il punto chiave. Non devi memorizzare la matrice delle nove intersezioni per tracciare la tua metropolitana, ma sapere che esiste spiega perché questi controlli binari sono così affidabili. Ogni spatial predicate non è altro che un pattern specifico di flag True e False in quella matrice matematica sottostante. Grazie per essere stato con noi. Spero tu abbia imparato qualcosa di nuovo.

Ciao, sono Alex di DEV STORIES DOT EU. Shapely, episodio 5 di 8. I diagrammi di Venn non servono solo per insiemi logici o query di database. Puoi usare gli stessi identici principi matematici per suddividere fisicamente la geografia del mondo reale. Per farlo, ti servono le operazioni della teoria degli insiemi. In Shapely, ogni geometria è essenzialmente un insieme infinito di punti su un piano bidimensionale. Dato che sono insiemi, puoi manipolarli usando la classica teoria degli insiemi. Innanzitutto, dobbiamo chiarire una fonte comune di confusione. I predicati spaziali, come verificare se due forme si toccano o si incrociano, valutano una condizione e restituiscono un semplice True o False. Le operazioni della teoria degli insiemi fanno qualcosa di completamente diverso. Restituiscono oggetti geometrici completamente nuovi. Prendono due forme in input, analizzano i loro punti di sovrapposizione e costruiscono una terza forma completamente nuova come output. Considera uno scenario concreto. Hai due dataset di poligoni. Uno rappresenta una vecchia mappa delle zone alluvionali. L'altro è un modello di rischio alluvionale aggiornato di recente. Devi calcolare l'area esatta in cui questi due modelli coincidono. Per questo, usi il metodo intersection. Chiami intersection sulla prima geometria e passi la seconda geometria come argomento. Shapely analizza la sovrapposizione spaziale e restituisce un nuovo poligono contenente solo i punti presenti sia nella vecchia che nella nuova mappa. Se le due forme non si sovrappongono affatto, restituisce una empty geometry. Ora, e se avessi bisogno di trovare solo le nuove aree a rischio? Sono i quartieri che erano sicuri nella vecchia mappa, ma che ora si trovano nella zona a rischio alluvione aggiornata. Qui, usi il metodo difference. Prendi la geometria del nuovo modello di alluvione e chiami difference, passando la geometria della vecchia mappa. Questo restituisce una forma contenente tutti i punti del nuovo modello, escludendo esplicitamente tutti i punti che erano già presenti nel vecchio. L'ordine qui è fondamentale. Se lo inverti e chiami difference sulla vecchia mappa, passando il nuovo modello, ottieni un risultato completamente diverso. Ottieni le aree che non sono più considerate a rischio. È semplicemente una sottrazione spaziale. A volte non vuoi confrontare le forme, vuoi solo combinarle. Se i servizi di emergenza hanno bisogno di una mappa generale di tutte le aree che sono mai state segnalate come a rischio alluvione, usi il metodo union. Chiami union su una forma, passi l'altra, e Shapely le unisce. Se le forme si sovrappongono, i confini interni si dissolvono. L'output è una singola geometria continua che rappresenta tutti i punti di entrambe le forme originali. Infine, c'è il metodo symmetric difference. Pensalo come l'equivalente spaziale di un'operazione di exclusive OR. Restituisce una nuova geometria contenente punti che sono presenti nella vecchia mappa o nella nuova mappa, ma assolutamente non in entrambe. Nel nostro scenario di alluvione, questa singola operazione ti fornisce esattamente le aree di disaccordo tra i due modelli. Restituisce in output le zone di rischio appena aggiunte insieme alle zone di rischio appena rimosse, svuotando completamente le aree in cui i modelli concordano. Ecco il punto chiave. Quando smetti di pensare ai confini spaziali come a concetti geografici complessi e inizi a trattarli come semplici insiemi matematici, calcolare sovrapposizioni ed esclusioni complesse diventa un processo prevedibile e completamente standard. Questo è tutto per questo episodio. Grazie per l'ascolto e continua a costruire!

Ciao, sono Alex di DEV STORIES DOT EU. Shapely, episodio 6 di 8. Un semplice punto matematico ha un'area pari a zero. È semplicemente una posizione. Ma cosa succede se hai bisogno di rappresentare il raggio di un'esplosione attorno a quella posizione? Puoi trasformare istantaneamente quel punto a zero dimensioni in un poligono enorme e preciso. Questo è il potere delle operazioni costruttive, in particolare buffer e hull. Le operazioni costruttive prendono una geometria esistente e ne costruiscono una nuova, diversa, basandosi sulle sue proprietà spaziali. Puoi immaginarle come dei wrapper di sicurezza attorno ai tuoi dati spaziali. L'operazione costruttiva più utilizzata è il buffer. Passi un valore di distanza alla funzione buffer e Shapely restituisce un poligono che rappresenta tutti i punti entro quella distanza esatta dalla tua geometria originale. Se hai una linea che rappresenta il percorso di una fuoriuscita di sostanze chimiche lungo un'autostrada e devi stabilire una zona di sicurezza di 50 metri, chiami buffer sulla geometria di quella linea con una distanza di 50. L'output è un nuovo poligono che traccia l'intero percorso, espandendosi verso l'esterno di esattamente 50 metri in ogni direzione. Ecco il punto chiave. I buffer non si limitano ad espandersi. Possono anche restringersi. Se passi una distanza positiva, la geometria si espande. Se applichi una distanza negativa a un poligono, la geometria si contrae. Un buffer negativo tira i confini verso l'interno. Questo è incredibilmente utile per individuare il nucleo interno sicuro di una zona, isolando l'area che si trova a una distanza precisa dai bordi pericolosi. A volte non hai bisogno di un buffer esatto attorno a forme complesse. Ti servono solo i limiti assoluti dei tuoi dati. Chiamare la proprietà envelope ti dà esattamente questo. Restituisce il bounding box, ovvero il rettangolo più piccolo e perfettamente dritto che racchiude completamente la tua geometria. È matematicamente leggero da calcolare e perfetto per uno spatial indexing veloce. Ma cosa succede quando i tuoi dati non sono una forma solida, ma una collezione sparsa di punti? Se hai decine di campioni di terreno contaminato e devi tracciare un unico confine continuo attorno all'area interessata, hai bisogno di un hull. Shapely ti offre due modi principali per farlo. Il convex hull calcola il poligono convesso più piccolo che contiene tutte le tue geometrie. Puoi immaginarlo come un elastico teso attorno a una tavola piena di pioli. L'elastico si stringe attorno ai pioli più esterni. Essendo convesso, il confine non rientra mai verso l'interno. Non ci sono angoli interni superiori a 180 gradi. Sebbene il convex hull sia affidabile, spesso include una grande quantità di spazio vuoto se i tuoi punti formano una mezzaluna o un cluster irregolare. Se hai bisogno di un adattamento più stretto, usi un concave hull. Invece di un elastico rigido, un concave hull agisce come una pellicola termoretraibile. Permette al confine di rientrare verso l'interno per seguire l'impronta effettiva dei tuoi dati. Controlli quanto strettamente avvolge regolando un parametro che limita la lunghezza massima consentita dei bordi del confine. Limiti più stretti costringono il confine a piegarsi negli spazi tra i punti, dandoti una mappa altamente accurata e realistica di quel terreno contaminato. La differenza tra questi tool sta in quanto aderiscono strettamente ai tuoi dati. L'envelope ti dà un box largo e veloce, il convex hull si tende strettamente sui punti esterni estremi, il concave hull avvolge la forma esatta come una pellicola, e il buffer applica un padding rigoroso ai bordi per una distanza definita. Se vuoi aiutare a far continuare questi episodi, puoi supportare lo show cercando DevStoriesEU su Patreon. Questo è tutto per questo episodio. Grazie per l'ascolto, e continua a costruire!

Ciao, sono Alex di DEV STORIES DOT EU. Shapely, episodio 7 di 8. Prova a renderizzare una linea costiera da un milione di punti su una web map, e farai crashare rapidamente il browser dell'utente. Hai bisogno di un modo per ridurre il footprint di quei dati all'uno per cento della loro dimensione originale, facendoli sembrare completamente identici. Questo richiede delle operazioni costruttive avanzate. Il tool principale per questa pulizia dei dati è la funzione simplify. Chi ascolta a volte pensa che semplificare una forma significhi solo saltare un punto ogni due o tre in un array. Farlo distrugge la geometria. Crea linee che si auto-intersecano, fa collassare le piccole isole e rovina la struttura topologica. La funzione simplify di Shapely valuta la geometria effettiva. Le passi la tua linea costiera complessa e un valore di tolleranza. La funzione rimuove i vertici che non deviano dalla forma principale per più di quella tolleranza. Cosa fondamentale, Shapely ti dà un flag per preservare la topologia. Quando è abilitato, l'algoritmo controlla attivamente se rimuovere un punto farà sì che un poligono si intersechi con se stesso o si divida in parti non valide. Garantisce che la tua linea costiera altamente compressa rimanga matematicamente valida. Una volta che semplifichi un base layer pesante, spesso hai bisogno che altri layer si allineino perfettamente ad esso. Mettiamo che tu abbia lotti di terreno o confini di proprietà che finiscono esattamente sull'acqua. Dato che hai appena semplificato la linea costiera, i suoi bordi si sono leggermente spostati. Questo crea microscopiche sovrapposizioni o spazi vuoti, conosciuti come sliver. Puoi sistemarlo usando la funzione snap. Fornisci la geometria del tuo confine di proprietà, la geometria della linea costiera e una distanza di tolleranza rigorosa. Snap guarda i vertici della prima forma. Se un vertice si trova entro la distanza di tolleranza da un vertice o da un segmento della seconda forma, viene tirato direttamente su di esso. I punti fuori dalla tolleranza restano esattamente dove sono. Questo crea un incastro perfetto e a tenuta stagna tra le geometrie adiacenti, senza distorcere il resto della forma. Questo copre la pulizia delle forme esistenti. L'altra faccia delle operazioni costruttive è dividere lo spazio vuoto usando i punti. Se prendi i vertici di una geometria, puoi passarli alla funzione delaunay triangles. Questo connette quei punti per formare una mesh continua di triangoli che non si sovrappongono. La logica disegna specificamente questi triangoli per massimizzare gli angoli interni più piccoli. Questo previene triangoli lunghi e a forma di ago, creando una mesh bilanciata utilissima per il rendering del terreno. Se vuoi solo il contorno di queste connessioni invece delle forme piene, puoi impostare un flag per farti restituire solo gli edge delle linee. Strettamente correlata è la funzione voronoi polygons. Mentre Delaunay connette i punti, Voronoi traccia i confini tra di loro. Fornisci una geometria, e Shapely usa i suoi vertici per dividere l'area circostante in regioni poligonali completamente distinte. Qualsiasi posizione all'interno di uno specifico poligono di Voronoi è più vicina al suo punto generatore centrale rispetto a qualsiasi altro punto dell'intero set. Se stai analizzando una dispersione di hub di consegna, i poligoni di Voronoi mappano all'istante l'esatta zona di copertura per ogni hub basandosi sulla pura prossimità. Proprio come per Delaunay, puoi istruire la funzione a restituire solo gli edge di confine se non ti servono poligoni pieni. Ecco il concetto chiave. I dati spaziali del mondo reale sono densi, disconnessi e raramente si allineano alla perfezione. Le operazioni costruttive come simplify, snap e voronoi ti danno i tool per imporre un ordine matematico, rendendo i dati abbastanza leggeri da renderizzare e abbastanza precisi da analizzare. Grazie per aver passato qualche minuto con me. Alla prossima, stammi bene.

Ciao, sono Alex di DEV STORIES DOT EU. Shapely, episodio 8 di 8. Confrontare un singolo punto con un milione di poligoni richiede un tempo di calcolo enorme, eppure alcune applicazioni lo fanno in millisecondi. Non calcolano ogni singola distanza. Filtrano il novantanove percento dei dati prima di eseguire una singola equazione matematica. Questa è l'indicizzazione spaziale ad alte prestazioni con STRtree. Mettiamo che tu voglia trovare la caffetteria più vicina alle coordinate GPS attuali di un utente, tra diecimila posizioni. Se calcolassi la distanza esatta per ogni singola caffetteria, il tuo sistema si bloccherebbe. Invece, l'indicizzazione spaziale usa un R-tree. Pensa a un R-tree come a un sistema di cartelle gerarchico per lo spazio bidimensionale. Disegna un semplice rettangolo, chiamato bounding box o envelope, attorno a gruppi di geometrie vicine. Poi disegna box più grandi attorno a questi box. Verificare se due semplici rettangoli si sovrappongono è un'operazione computazionalmente leggera. In Shapely, l'implementazione specifica è l'STRtree, che sta per Sort-Tile-Recursive. Ne crei uno passando un array di geometrie al costruttore. Dietro le quinte, questo esegue il bulk-load dell'indice. L'albero viene costruito una sola volta ed è immutabile. Non puoi aggiungere o rimuovere elementi dopo la sua creazione. Devi preparare l'intero dataset in anticipo. Una volta che l'albero esiste, ci fai una ricerca usando il metodo query. Passi una geometria di input e il metodo restituisce un array NumPy di indici interi. Questi indici mappano direttamente alla sequenza originale di geometrie che hai usato per costruire l'albero. Se passi in input più geometrie contemporaneamente, query restituisce un array bidimensionale, che accoppia gli indici dei tuoi input con gli indici corrispondenti nell'albero. Ecco il punto chiave. L'indice base di un STRtree controlla solo i bounding box, non le geometrie esatte. Se fai una query su un poligono complesso, l'albero usa l'envelope quadrato di quel poligono per trovare le corrispondenze. Questo ti dà una lista ristretta di candidati che contiene dei falsi positivi. Per ottenere una risposta esatta, Shapely ti permette di passare un predicato spaziale, come intersects o contains, direttamente nel metodo query come argomento. L'albero prima usa i bounding box, che sono leggeri, per trovare i candidati, poi valuta automaticamente il tuo predicato esatto su quella lista ristretta. Questo fa sì che il lavoro matematico pesante rimanga nel codice C compilato. Oltre alle sovrapposizioni, l'STRtree eccelle nella prossimità. Tornando al nostro scenario della caffetteria, non hai bisogno di controllare gli envelope manualmente. Usi il metodo query nearest. Passi il punto GPS del tuo utente, e l'albero attraversa i suoi box gerarchici per trovare la geometria in assoluto più vicina, senza fare misurazioni su tutte le diecimila. Restituisce immediatamente l'indice della caffetteria più vicina. Puoi anche specificare un parametro per restituire un array dei top N nearest neighbors, oppure impostare una soglia di distanza massima per limitare del tutto il raggio di ricerca. C'è anche un metodo nearest distinto, che confronta due alberi separati tra loro per trovare le coppie di geometrie più vicine. Le operazioni geometriche vere e proprie sono sempre la parte più costosa dell'analisi spaziale. L'STRtree agisce come un filtro implacabile. Ti impedisce di sprecare cicli di CPU su geometrie che non sono per niente vicine tra loro, fornendoti una lista ristretta e gestibile, in modo che i tuoi controlli matematici esatti vengano eseguiti solo quando è assolutamente necessario. Questo conclude la nostra serie su Shapely. Ti incoraggio vivamente a esplorare la documentazione ufficiale e a provare questi concetti di indicizzazione con mano sui tuoi dataset. Se hai workflow o tool che vorresti venissero trattati nelle prossime serie, visita devstories dot eu e lasciaci un suggerimento. Grazie per averci ascoltato. Alla prossima!