Sicuramente con le estensioni spatial della quasi totalità degli rdbms in circolazione, l’utilizzo dei QuadTree e di sistemi proprietari per il posizionamento e l’interrogazione spaziale di insiemi di coordinate e oggetti, potrebbe risultare obsoleto. In realtà ci sono ancora tantissimi casi e campi di applicazione in cui risultano fondamentali, come lo sviluppo di applicazioni pda, giochi, e tutti quei casi in cui non sia possibile utilizzare un database sql.
Essendomi trovato nell’ultimo caso descritto per motivi di lavoro e forte dell’esperienza nello sviluppo di prototipi di videogames acquisita per hobby negli anni passati, ho adottato questa soluzione per un applicazione web in cui era fondamentale fare delle query spaziali su un insieme di punti (descritti da longitudine e latitudine), per geolocalizzare dei punti di interesse intorno alla mia posizione entro un certo raggio, presi da dei file xml.
Per facilità e velocità mi sono basato sull’articolo scritto da Michael Coyle su CodeProject.com:
http://www.codeproject.com/KB/recipes/QuadTree.aspx
Un QuadTree è un modo di ripartire lo spazio e facilitare le query su sistemi 2D, molto utilizzato nei GIS in generale, o nella gestione della posizione degli oggetti nei videogames.
Il QuadTree è apppunto un albero formato da quadrati. Lo spazio viene ripartito in regioni quadrate suddivise in 4 quadranti ,partendo dalla regione che contiene tutto fino al livello minimo da noi definito, in maniera ricorsiva. Quindi ogni quadrante viene poi ulteriormente suddiviso.
Per eseguire delle query su un quadtree basta poi effettuare il traversing dell’albero ed eseguire delle semplici intersezioni per capire quali oggetti sono posizionati all’interno di una determinata regione (che è l’input della ricerca).
Questo permette di eseguire ricerche molto veloci su insiemi statici di coordinate. Ovviamente è un albero statico, che nell’algoritmo cosi come proposto non permette un dinamismo nella gestione delle regioni I(in quanto andrebbe ricalcolata la struttura ad ogni modifica), ma è molto semplice da realizzare, ed il punto di partenza fondamentale è conoscere i confini dell’area che andremo a gestire..
Nel mio caso dovendo rappresentare dei punti di interesse sparsi sul suolo italiano, ho acquisito il punto centrale dell’italia e calcolato un quadrato che la contenesse tutta, e poi ho trasformato le coordinate geografiche in coordinate 2d, utilizzando gli stessi algoritmi di google maps, quindi con il fattore di zoom e tutto il resto.
Questa è la funzione che ho usato per la conversione di coordinate geografiche in coordinate schermo (x,y):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | public static PointF Geographical2Screen(Position position) { //converte le coordinate in pixel float x; float y; double xD = (position.Longitude - mapLongitude) / resolution; double yD = Math.Log(Math.Tan(Math.PI * (0.25 + position.Latitude / 360))) * u180dPiResolution; x = Convert.ToSingle(xD + viewWidthHalf); y = Convert.ToSingle((y0 - yD) + viewHeightHalf); return new PointF(x, y); } |
dove per costanti ho usato, ipotizzando di inscrivere tutta l’area in un quadrato di 1024 pixel per 1024 pixel e usato un fattore di zoom che mi permettesse di mantenere tutta la mappa d’italia in questo quadrato .
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | public static float WIDTH = 1024F; public static float HEIGHT = WIDTH; public static float CENTERMAP = WIDTH /2; public static float TOTALPIXEL = WIDTH; public static int zoom = 6; public static double resolution = 360.0 / (Math.Pow(2,zoom) * 256); public static double u180dPiResolution = 40.7436654315252 * Math.Pow(2, zoom); public static double mapLatitude = 41.8719400F; public static double mapLongitude = 12.5673800F; public static double y0 = Math.Log(Math.Tan(Math.PI * (0.25 + mapLatitude / 360))) * u180dPiResolution; public static float viewWidthHalf = WIDTH / 2.0f; public static float viewHeightHalf = HEIGHT / 2.0f; |
Fatto questo, ho costruito il mio quadtree a partire dal nodo principale:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | public class QuadTree { QuadTreeNode m_root; RectangleF m_rectangle; //solo per funzionalita di paint public delegate void QTAction(QuadTreeNode obj); public QuadTree(RectangleF rectangle) { m_rectangle = rectangle; m_root = new QuadTreeNode(m_rectangle); } public int Count { get { return m_root.Count; } } public void Insert(IQuadPoint item) { m_root.Insert(item); } public ListQuery(RectangleF area) { return m_root.Query(area); } public void ForEach(QTAction action) { m_root.ForEach(action); } } |
Il delegato QTAction viene usato per poter rappresentare ad esempio tramite delle paint i nodi e i quad nel viewer.(un callback per il traversing, e per ogni elemento, disegno..)
il punto definito come risultato e’ un interfaccia da me cosi definita e che serve a markare gli oggetti che avranno la possibilità di essere inseriti nella struttura (per i fini della ricerca l’importante che l’oggetto da trovare abbia una posizione X,Y)
1 2 3 4 | public interface IQuadPoint { PointF Point { get; } } |
Fatto questo passo alla definizione del nodo del quad, dove risiede l’implementazione ricorsiva della ricerca:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 | public class QuadTreeNode { //area occupata da questo nodo RectangleF m_bounds; //contenuto del nodo List m_contents = new List(); //figli di questo nodo List m_nodes = new List(4); static int maxElements = 50; static int minSize = 10; public QuadTreeNode(RectangleF bounds) { m_bounds = bounds; } //test se vuoto public bool IsEmpty { get { return (m_bounds.IsEmpty || m_nodes.Count == 0) && m_contents.Count==0; } } //confini del nodo public RectangleF Bounds { get { return m_bounds; } } //contenuto del nodo public List Contents { get { return m_contents; } } //count degli item del nodo e dei subNodi public int Count { get { int count = 0; foreach (QuadTreeNode node in m_nodes) count += node.Count; count += this.Contents.Count; return count; } } //ritorna il contenuto globale di questo nodo(questo + subNodi) public List FullContents { get { List results = new List(); foreach (QuadTreeNode node in m_nodes) results.AddRange(node.FullContents); results.AddRange(this.Contents); return results; } } //ritorna gli item all'interno di una certa area public List Query(RectangleF queryArea) { List results = new List(); foreach (IQuadPoint item in this.Contents) { if (queryArea.Contains(item.Point)) results.Add(item); } foreach (QuadTreeNode node in m_nodes) { if (node.IsEmpty) continue; //se un subNodo contiente completamente la query area.. prendi tutto e esci if (node.Bounds.Contains(queryArea)) { results.AddRange(node.Query(queryArea)); break; } //se l'area contiene il subnodo, lo importa tutto e continua if (queryArea.Contains(node.Bounds)) { results.AddRange(node.FullContents); continue; } //se il subnodo interseziona l'area di ricerca, allora inoltra la query ai suoi subNodi if (node.Bounds.IntersectsWith(queryArea)) { results.AddRange(node.Query(queryArea)); } } return results; } //inserisce un item public void Insert(IQuadPoint item) { if (!m_bounds.Contains(item.Point)) { //System.Diagnostics.Debug.Print("punto non compreso nel nodo:"); // System.Diagnostics.Debug.Print("--->"+item.Point); return; } //se c'e' capienza e non ho generato le foglie if (this.Contents.Count < maxElements && m_nodes.Count ==0) { //inserisco in questo this.Contents.Add(item); return; } else { //genera i subtree if (m_nodes.Count == 0) { CreateSubNodes(); if (m_nodes.Count > 0) { //ridistribuisco sui figli foreach (IQuadPoint punto in Contents) { foreach (QuadTreeNode node in m_nodes) { if (node.Bounds.Contains(punto.Point)) { node.Insert(punto); break; } } } Contents.Clear(); } else { //forza inserimento in questo nodo indipendentemente dalla size: this.Contents.Add(item); } } //per ogni subnodo fa l'add ricorsivo fino ad arrivare al quad piu piccolo foreach (QuadTreeNode node in m_nodes) { if (node.Bounds.Contains(item.Point)) { node.Insert(item); return; } } } } //solo in caso di paint public void ForEach(QuadTree.QTAction action) { action(this); // draw the child quads foreach (QuadTreeNode node in this.m_nodes) node.ForEach(action); } //Crea i subNodi private void CreateSubNodes() { // the smallest subnode has an area if ((m_bounds.Height * m_bounds.Width) return; float halfWidth = (m_bounds.Width / 2f); float halfHeight = (m_bounds.Height / 2f); m_nodes.Add(new QuadTreeNode(new RectangleF(m_bounds.Location, new SizeF(halfWidth, halfHeight)))); m_nodes.Add(new QuadTreeNode(new RectangleF(new PointF(m_bounds.Left, m_bounds.Top + halfHeight), new SizeF(halfWidth, halfHeight)))); m_nodes.Add(new QuadTreeNode(new RectangleF(new PointF(m_bounds.Left + halfWidth, m_bounds.Top), new SizeF(halfWidth, halfHeight)))); m_nodes.Add(new QuadTreeNode(new RectangleF(new PointF(m_bounds.Left + halfWidth, m_bounds.Top + halfHeight), new SizeF(halfWidth, halfHeight)))); } } |
Fatto cio è possibile usare il QuadTree e inserire i nostri oggetti.
Seguendo il progetto di Michael Coyle, ho realizzato un piccolo viewer per controllare il risultato e fare delle query di prova , il sistema è molto veloce in fase di inserimento (40000 punti inseriti in un secondo comprensivo di generazione di tutti i quad), e tempi di risposta in caso di interrogazione molto bassi, sotto il millisecondo.
Ovviamente per interrogare il quad, bisogna trasformare le coordinate geografiche in coordinate 2d piane.
Le formule di intersezione sono eseguite utilizzando le System.Drawing, beneficiando cosi della velocità delle librerie grafiche di windows.
