tags:

views:

42

answers:

1
+1  Q: 

Data structure in python for 2d range counting queries

Hi, I need a data structure for doing 2d range counting queries (i.e. how many points are in a given rectangle).

I think my best bet is range tree (it can count in log^2, or even log after some optimizations). Does it sound like a good choice? Does anybody know about a python implementation or will I have to write one myself?

+1  A: 

See scipy.spatial.KDTree for one implementation.

There's also a less generic (but occasionally more useful, particularly with regards to what you have in mind) implementation using shapelib's quadtree. See this blog and the corresponding package in PyPi.

There are probably other implementations, too, but those are the two that I've used...

Joe Kington  2010-06-17 00:23:48
I didn't use it because I thought kdtree is O(sqrt(n)). I was talking about a different data structure (range tree) which is O(log^2(n)). However, it seems they are using a really cool optimization for multiple queries, and the article (http://www.cs.cmu.edu/~agray/nips-final.ps) mentions exactly what I'm trying to to do as an application for the method (fast kernel density estimation). So I'll give it a try. Thanks!
Dani  2010-06-17 15:37:47

related questions

Programmatically talking to a Serial Port in OS X or Linux
Best ways to teach a beginner to program?
Calling a Function From a String With the Function's Name in Python
An executable Python app
Text Editor For Linux (Besides Vi)?
What Hosting Service is best for Django applications?
File size differences after copying a file to a server vía FTP
Python: what is the difference between (1,2,3) and [1,2,3], and when should I use each?
Python: What OS am I running on?
How do I make a menu in python that does not require the user to press (enter) to make a selection?
How do you express binary literals in Python?
What is the most efficient graph data structure in Python?
Adding a Method to an Existing Object
How to learn Python: Good Example Code?
How do I use Python's itertools.groupby()?
Python and MySQL
Class views in Django
Is there an IDE that provides code completion for Python
Using 'in' to match an attribute of Python objects in an array
cx_Oracle - what is the best way to iterate over a result set?
cx_Oracle - How do I access Oracle from Python?
Continuous Integration System for a Python Codebase
Get a preview jpeg of a pdf on windows?
How can I find the full path to a font from its display name on a Mac?
XML Processing in Python