What is a good data structure for storing and searching 2d spatial coordinates in Java
I am currently writing a plugin for a game where one feature includes the ability to set areas defined by 2 two dimensional coordinates ( The upper left and lower right areas of a rectangle). These regions are then to be stored, and will have various other data associated with each region. As the player is moving about the world, I need to determine when he enters one of these regions from only the coordinates of the player, and the method of doing so must be efficient, as this will end up being called hundreds of times per second.
Are there any data structures that can efficiently support this kind of search, and if so, where can I find documentation on it, to either find a java implementation to use, or if necessary, implement it myself?
I also want to note, I found a few tree structures that only seemed to support bulk-loading, but I must be able to add and remove values from this structure in real time.
Answer
A good datastructure for determining collision in a part of space is the quad-tree datastructure. The quad-tree recursively divides a space according to the number of elements in a given area. Thus it can do a search if coordinates are inside a region in logarithmic time.
EDIT: I have found an implementation here but no license information is given.