14

Are there any good implementations of spatial indexes in Haskell such as R-tree, kd-tree, etc...

mentics
  • 6,852
  • 5
  • 39
  • 93

3 Answers3

9

The only implementations I'm aware of are the spacepart package, which seems to be incomplete and abandoned, and the KdTree package, which as you might guess has no ambitions beyond providing a kd-tree type.

This is something that's been on my TODO list for a while, since there have been several occasions where I wanted a spatial index data structure, but didn't want one badly enough to stop everything and write a decent implementation on the spot.

C. A. McCann
  • 76,893
  • 19
  • 209
  • 302
  • 1
    The gloss package has quadtrees too -- no idea about their quality: http://hackage.haskell.org/package/gloss-1.1.0.0 – sclv Sep 01 '11 at 14:45
  • @sclv: Cool, didn't know that. Wouldn't necessarily want to depend on gloss just for a quadtree, but perhaps the author could be persuaded to extract it as a separate package. – C. A. McCann Sep 01 '11 at 16:19
  • It's Ben Lippmeier, so I assume A) that he knows what he's doing w.r.t. performance, whether or not he's really worked on it and B) he'd be very open to pulling it out as a package. – sclv Sep 01 '11 at 17:22
3

The Glome Raytracer uses a bounding interval hierarchy.

It well modularized too, so you'll probably want to start with GlomeTrace and GlomeVec.

I'm doing collision testing via point/volume queries and ray intersections. It seems to perform very well.

Thomas
  • 514
  • 3
  • 10
  • I should point out that I've had trouble using some of the features in the Glome API... Inside/Outside tests don't work quite as I'd expect. – Thomas Oct 04 '11 at 03:18
1

there is a RTree package on Hackage. It is tested, but it's not as sophisticated as the containers package.

Sebastian Wagner
  • 2,308
  • 2
  • 25
  • 32