CODEWITHSUNDEEP
data-structuresocamlfunctional-programming
LiKao
LiKao

Reputation: 10658

Data structure for spatial data

I am looking for a good functional data structure to store spatial (point) data. The data structure should allow simple epsilon queries for points already present. Also I need to modify the data quite often. This means points can move and should be able to be updated in the data structure. This can probably be handled using a normal delete/add, but a real move might be faster.

For now I am thinking about using quad/oct-trees (or higher), since the move part should be quite easy to do. However quad-trees are known to be worse as far as balancing is concerned. KD-Trees might be another choice, but the update seems quite nasty. Also most spacial data structure implementations I can find are only procedural and I am using a functional language.

Upvotes: 11

Views: 840

Answers (4)

axel22
axel22

Reputation: 32335

This old paper by Overmars and van Leeuwen describes the pseudo quadtree - a quadtree which can also balance itself as insertions and deletions progress. The amortized cost of insertions and deletions is something like O(log^d(n)) and can even be traded against the amount of balancing done (you can read more about this in the paper).

Upvotes: 4

cynddl
cynddl

Reputation: 121

R-Trees and R*-Trees are also another solution, easy to implement.

See https://github.com/mariusaeriksen/ocaml-rtree (in OCaml) for an example.

I used them in an evacuation simulation, the update step is not so slow as that.

Upvotes: 3

Don Stewart
Don Stewart

Reputation: 137947

KD-trees or Quad/Oct trees are reasonable choices.

Examples in Haskell:

Both are pretty simple to encode as purely functional data structures.

Upvotes: 3

Johannes Hoff
Johannes Hoff

Reputation: 3901

Depending on how you are using it and quickly the points move, you might also consider sweep and prune. Basically, you keep the points sorted in one dimension (say x). If points change places very seldom, running insertion sort for every simulation step will actually be very quick.

(I think your two suggestions are already quite good, by the way)

Upvotes: 4

Related Questions