13

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.

Sethcran
  • 153
  • 1
  • 5
  • See also this [answer](http://stackoverflow.com/questions/3340402/how-to-find-out-whether-an-affine-transformed-rectangle-contains-a-certain-point/3340763#3340763). – trashgod May 30 '11 at 18:40
  • How many rectangles? Do rectangles change frequently? Any performance requirements for adding / removing rectangles? – meriton May 30 '11 at 18:45
  • @meriton - Rectangles will not be changed but only added and removed, and because this is running on a server, it will need to handle at least a couple insertions per second without hurting performance of the server, although on average it may only be called once a minute. – Sethcran May 30 '11 at 18:48
  • @trashgod - I need to be able to search the space efficiently though, not just determine if the shape is contained or not, that's already trivial, but exhaustively searching through a list of thousands or more shapes to see if any contains it isn't efficient. – Sethcran May 30 '11 at 18:51
  • Can you be more specific than thousands or more? 10000? 100000? 1000000? – meriton May 30 '11 at 18:52
  • @meriton - I'd expect probably along the lines of 1-10k regions in the space at a given time. – Sethcran May 30 '11 at 18:54

3 Answers3

11

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.

Yet Another Geek
  • 4,251
  • 1
  • 28
  • 40
  • Definitely the best solution of those thus far presented. – Sethcran May 30 '11 at 18:59
  • 2
    It's answers like these that remind me why I love this site -- I keep learning something new every day! – Hovercraft Full Of Eels May 30 '11 at 19:56
  • But the question is not if a point is within a particular region, but which regions newly or no longer contain the point. I fail to see how a quad tree helps with that? – meriton May 30 '11 at 19:57
  • @meriton - " I need to determine when he enters one of these regions from only the coordinates of the player" - I can use the tree to determine when the player enters a region, and combined with a location cache, it will do exactly what I am looking for. – Sethcran May 30 '11 at 20:09
  • The broken link [there](http://algs4.cs.princeton.edu/92search/QuadTree.java.html), should point to [Algorithms, 4th Ed](http://algs4.cs.princeton.edu/home/). See also the [OpenMap API](http://openmap.bbn.com/). – trashgod May 30 '11 at 22:28
  • The OpenMap API one is pretty slow, we had to optimize it ourselves when we used it. A simple optimization is to use ArrayList instead of vector. – Yet Another Geek May 31 '11 at 11:45
  • 1
    There is an [MIT Licensed implementation of QuadTree on GitHub](https://github.com/varunpant/Quadtree). – chrisjleu Apr 05 '17 at 06:25
1

In the one-dimensional case, a suitable data structure is the interval tree.

To solve the two-dimensional cast, you can either use an interval tree to quickly find those rectangles that contain the point in at least one dimension, and check the second dimension for each of them (which might already be fast enough), or use the generalizations to many dimensions the Wikipedia article sketches briefly (though I must admit that I did not understand that generalization on the first read).

Assuming the player moves slowly (i.e. the number of region enter or leave events is small compared to the number of regions) the following approach might be more efficient: Keep a search tree of the x-coordinates where rectangles begin or end, and an a similar tree for the y-coordinates. If a player enters or leaves a region, he must have crossed the x or y coordinate of a boundary point. That is, you would do a range query on the x search tree for the range [old_x, new_x], and check each of these rectangles. Do the same for the y-direction (not reporting duplicates).

meriton
  • 68,356
  • 14
  • 108
  • 175
0

To implement coordinates you can use Point2D in a class that implements the functionality you're looking for:

http://download.oracle.com/javase/6/docs/api/java/awt/geom/Point2D.html

trashgod
  • 203,806
  • 29
  • 246
  • 1,045
james_bond
  • 6,778
  • 3
  • 28
  • 34