Newsgroup: it.comp.java
Titolo: Quadtree e rimozione oggetti

Ciao a tutti. Avrei bisogno di una classe che mi permetta di eseguire 
veloci interrogazioni su dei dati spaziali. In particolare, ho un set di 
triangoli i cui lati non si intersecano se non eventualmente nei 
vertici. Tali triangoli possono poi essere partizionati in altri 
triangoli più piccoli. Dato un punto vorrei estrarre il triangolo più 
interno che contiene tale punto. Fondamentalmente dei triangoli più 
grandi (già partizionati) non mi interessa nulla, sarebbe quindi 
preferibile che potessero essere eliminati dal set.
Sto usando la libreria JTS (
www.vividsolutions.com
) e la classe che 
farebbe per me sarebbe la Quadtree 
(
http://www.jump-project.org/docs/jts/1.1/api/com/vividsolutions/jts/index/quadtree/Quadtree.html
). 
Il problema è che tale classe non prevede la rimozione di oggetti, 
pertanto in una query mi verrebbero restituiti tutti i triangoli, anche 
quelli già partizionati.
Una soluzione potrebbe essere quella di usare il Quadtree e 
successivamente una Hashtable dove memorizzare i soli triangoli "buoni", 
essendo possibile la rimozione di oggetti dalla Hashtable, ma 
sinceramente preferirei usare un unico oggetto.
Sapete consigliarmi qualcosa?
Grazie anticipato.
P.S. se non si era capito, sto eseguendo una triangolazione :)

raynor@localhost ha scritto:

La documentazione della classe Quadtree sembra un po' povera. Poiché ci 
sono decine di tipi di quadtree, e data la mancanza di indizi, non è 
possibile capire il costo computazionale delle operazioni offerte. 
D'altra parte, se hai deciso di ricorrere a una struttura dati 
multidimensionale, devi evidentemente aver bisogno di fare range query 
(altrimenti il quadtree sarebbe inutilmente oneroso! se hai bisogno solo 
di fare point location ci sono altre strutture dati....).
Un limite che sembra evidenziarsi è nella insert:
public void insert(Envelope itemEnv,
                    Object item)
dove un Envelope è sostanzialmente un rettangolo isotetico, che sembra 
essere usato come bounding box (BB) dell'oggetto spaziale item, 
presumibilmente un triangolino. Poiché stai parlando di una 
triangolazione è praticamente sicuro che dovrai gestire BB che si 
sovrappongono, il che è mal digerito da un quadtree che non sia 
espressamente progettato a tale scopo.
Una soluzione molto semplice consiste nell'effettuare la marcatura 
logica (di cancellazione) delle info gestite (a tale scopo basterà 
aggiungere una variabile di istanza booleana). I limiti di questo 
approccio sono:
- all'aumentare delle cancellazioni non corrisponde un costo ridotto di 
esecuzione della query
- lo spazio utilizzato è sovraottimale
Conseguenza: al crescere della dimensione dell'input i costi di 
esecuzione diventeranno eccessivamente gravosi.
Non sono a conoscenza di classi Java pronte per te, specialmente perché 
non hai chiarito quali sono le operazioni che devi poter svolgere sulla 
triangolazione, la loro frequenza e la dimensione della stessa.
Implementare ex-novo un quadtree non è eccessivamente gravoso, purché si 
conosca la problematica. In particolare potresti scegliere quello che 
meglio si presta ad eseguire le operazioni che ti occorrono. Un ottimo 
punto di partenza è costituito dalla coppia di libri di Samet:
@Book{Samet+1990a,
   author =       "Hanan Samet",
   title =        "The Design and Analysis of Spatial Data Structures",
   publisher =    "Addison-Wesley",
   address =      "Reading, Massachusetts, U.S.A.",
   edition =      "reprinted with corrections",
   month =        apr,
   year =         "1990",
   series =       "Series in Computer Science",
   serieseditor = "Michael A. Harrison",
   ISBN =         "0-201-50255-0",
   pages =        "i--xvii,~1--493",
   library =      "Uni of Melbourne, Engineering Library - 005.73 SAME",
}
@Book{Samet+1990b,
   author =       "Hanan Samet",
   title =        "Applications of Spatial Data Structures: Computer
                  Graphics, Image Processing, and {GIS}",
   publisher =    "Addison-Wesley",
   year =         "1990",
   series =       "Series in Computer Science",
   ISBN =         "0-201-50300-X",
   library =      "Uni of Melbourne, Engineering Library - 006 SAME",
}
Spero ti possa essere un po' utile.
Fabrizio