Eu estou tentando determinar uma maneira rápida de armazenar um conjunto de objetos, cada um com um valor de coordenadas xey, de modo que eu possa recuperar rapidamente todos os objetos dentro de um determinado retângulo ou círculo. Para pequenos conjuntos de objetos (~ 100), a abordagem ingênua de simplesmente armazená-los em uma lista e iterá-los é relativamente rápida. No entanto, para grupos muito maiores, é esperado que seja lento. Eu tentei armazená-los em um par de TreeMaps também, um classificado na coordenada xe um classificado na coordenada y, usando este código:

xSubset = objectsByX.subSet( minX, maxX );
ySubset = objectsByY.subSet( minY, maxY );
result.addAll( xSubset );
result.retainAll( ySubset );

Isso também funciona, e é mais rápido para conjuntos maiores de objetos, mas ainda é mais lento do que eu gostaria. Parte do problema também é que esses objetos se movimentam e precisam ser inseridos novamente nesse armazenamento, o que significa removê-los e adicioná-los novamente às árvores / listas. Não posso deixar de pensar que deve haver soluções melhores por aí. Estou implementando isso em Java, se faz alguma diferença, embora eu espere que qualquer solução seja mais na forma de um padrão / algoritmo útil.