What datastructure is a good choice for objects in a map-editor?

Question

I am planning to implement a map-editor. But I don't really know what data structure is a good choice for storing the map-object in. When the user pans (scrolls) the map, there will be much looking up of what objects are in the visible area, usually by having a min_x, min_y and max_x, max_y coordinate pair.

I have read that R-trees are good for this type of use, but they seem to be complicated to implement.

So far I have just used a linked list that I have to loop through very often; it's not optimal, but it works. Are there any better choice of data structures?

Answer 1

R-trees are indeed a great choice. Depending on your platform you might be able to find working implementations so you don't have to go through the pain.

A simpler alternative is to use Quadtrees (which are a special case of R-trees, thus simpler) that may be suitable enough for your use case.

Answer 2

R-Trees if your data is sparse (which it very likely is). If you have dense data you can store a tile-based system, a 2-D array or jagged array (array of arrays). I would avoid linked lists but it depends on what you are trying to accomplish.

Answer 3

Take a look at the implementation of "com.vividsolutions.jts.index.strtree.STRtree" in JTS.

"A query-only R-tree created using the Sort-Tile-Recursive (STR) algorithm"

Answer 4

Another option, rather than worrying about this kind of implementation yourself, is to use a spatial database: PostGIS is a common, open source one. The database will take care of the quad-tree access for you, allowing you to simply store geometries in a database, and have the database handle the geographic indexes for you.

• Jon Bringhurst: On that same line, there's a hibernate plugin for serializing JTS objects to postgres with minimal fuss.
• Jonas: Thanks, but I'm not looking for a persistent database, I am looking for a datastructure in memory for keeping track of the objects.

Answer 5

Depending on your needs and data as other posters have touched on it is best to use different methods. If you need a robust and fast application you are best to not use just one data structure but to rather support multiple data structures for different data sets. If you are having trouble understanding how to create an R-tree index and your data isn't crazy large a combination of a shallow quad-tree followed up with simple MBR checks may be an easy good enough solution. For a collection with relatively few items a simple loop can outperform parsing a tree/linked list, so even though a quad-tree is not the best fit for most data it can get you pretty close to that magical number where standard looping can be fast enough to be usable. Also note that using a linked list structure vs. using a sizable array will iterate slower, especially if your software is ever compiled for hardware directly, such as with JIT compilation. But if you can do it... R-tree is the way to go most of the time.