Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have a list in Python 2.7 of about 10000 point co-ordinates, like

[(168, 245), (59, 52), (61, 250), ... (205, 69), (185, 75)]

Is there a faster way to search for all the points in a bounding box, instead of just iterating over the entire list each time and checking if the co-ord is inside the 4 sides??
I'm using this "algoritm" to see if any point, which is randomly moving, has come inside the stationary bounding box..(if it helps)

share|improve this question
    
How do you get these coordinates? Do they come one-by-one or all at once? And what language are you using? –  superM Mar 13 '13 at 14:33
    
@superM As tagged Python is my language. 2.7 to be exact. The co-ordinates are random... It's a list in python, so I can iterate and get one point at a time, but that is too slow for my purpose.. –  Schoolboy Mar 13 '13 at 14:38
    
It depends if your list is sorted or not. –  Simon Mar 13 '13 at 14:39
    
@Simon It's not sorted, how does that matter?? –  Schoolboy Mar 13 '13 at 14:41
    
are you able to put them into another data structure? –  jk. Mar 13 '13 at 14:41
show 4 more comments

5 Answers

up vote 11 down vote accepted

If the points are constantly moving, then it's impossible to do better than O(n), because you have to check each point every time it moves. You have some code somewhere that moves the points, just add the bounds check into that code. Keeping a list sorted, or updating a quadtree or something would only be more efficient if the point positions were not changing frequently and instead you were checking several different bounding boxes, like searching for points on a map, for example.

If the points are moving according to a preset pattern, like in a straight line at a constant velocity, then you can change your algorithm to only do the bounds check when the direction or speed is changed. For example, if you are moving one pixel per second, and the bounding box is 10 pixels away, you know you don't have to check that point for another 10 seconds. 100 points is a pretty small number though, and at that small of a scale, the overhead from the extra complexity may not outweigh the extra iterations of the simpler algorithm.

Also, that small of a scale makes me wonder if you're sure the bounds checking is your bottleneck. A modern computer should be easily able to bounds check 100 points in under 10 microseconds. Have you actually measured it?

share|improve this answer
4  
+1 all algorithms are fast for small enough n –  jk. Mar 13 '13 at 15:27
    
+1 The edit adding "is constantly moving" really changed the question... –  bunglestink Mar 13 '13 at 17:32
2  
I know, @bunglestink. It's interesting in our field how many "insignificant" details turn out to be critical. –  Karl Bielefeldt Mar 13 '13 at 17:40
add comment

If possible I'd use a different data structure, one that is designed for spatial indexing. e.g. a quadtree (there are many others though)

This should allow (assuming non-degenerate data) to find a closest point in typicaly O(log n) comparisons. You could also use a spatial DB to do this for you .

edit: quadtrees really help when your points are (relatively) static to your search box, your edit suggests you have the opposite problem in which case you may not be able to do better than O(n) i.e. you probably dont want to construct a quadtree every time the points move unless you are going to be checking many bounding boxes for each move

share|improve this answer
    
Is there anything like Quadtrees in Python?? –  Schoolboy Mar 13 '13 at 14:51
2  
@Schoolboy if not, you can implement your own Quadtree in Python. It's a typical task as well as being a well-defined data structure which you can get plenty of documentation on. –  Jimmy Hoffa Mar 13 '13 at 14:52
    
there seems to be a pygame library that implements one and a few SO questions about implementing them (found via google), I doubt there is one in the standard library though, Spatial indexing is seen as a niche use –  jk. Mar 13 '13 at 14:53
1  
+1, I was about to recommend a similar path. Depending on other constraints and how crucial this is, you could probably develop a very specialized data structure to get the lookup time close to O(1). Some info that would be helpful to optimize... can points repeat? are they over a set range? are they all integer values? –  bunglestink Mar 13 '13 at 14:58
1  
@Schoolboy: First hit on Google: pypi.python.org/pypi/Quadtree. It's a C module, so if it works it'll be blazingly fast. –  Martijn Pieters Mar 13 '13 at 15:23
add comment

As stated by you, there is no way of being faster than O(n). Every point in the list might be a hit, so you have to scan the entire list.

It would be possible to arrange the list such that you can terminate the search early if you can prove that none of the following points will be in the desired bounding box. For instance, by sorting the point by their X coordinates, you can stop searching when the value becomes higher than your upper boundary. Depending on what kind of point lists you get, other schemes may be more efficient.

share|improve this answer
    
So in short, the answer is No, unless ... What other schemes? I'm using this "algoritm" to see if any point, which is constantly moving, has come inside the stationary bounding box..(if that shall help) –  Schoolboy Mar 13 '13 at 14:49
    
As Killian says, if you can keep the list in sorted order, you can halt iteration early. Sorting is roughly O(n log n), but a sorted insert is only O(log n). Keeping your points in a quadtree in the first place would be even better. –  Useless Mar 13 '13 at 14:52
4  
The point is the algorithm and the data structure are tightly coupled. If you want a better algorithm, you need a better data structure too (counting a sorted list as a different structure because it's more constrained). Using a list with no additional constraint, iterating over the whole thing is all you can do. –  Useless Mar 13 '13 at 15:00
add comment

What does "constantly moving" mean?

For example, if these points represent particles moving with a constant velocity and only affected by hard-sphere collision with other particles and with the wall, then it's possible to compute the time to intersection of each particle with the bounding box, and the compute the time for next collision. The time for next intersection can be kept in a priority queue, and when an intersection or collision occurs, you need only compute, in O(n) time, the next intersection of that particle/those particles with every other particle.

The mechanics of this are outlined in http://introcs.cs.princeton.edu/java/assignments/collisions.html , and summarized by Karl Bielefeldt earlier.

If the movement is random, but the changes are small and bounded then there's an upper limit on how far things can move. Use that as a bound. For example, if the max speed is 0.1 units per evaluation and your bounding box is the cell (10,10)-(11,11) then you can easily determine the particles within, say, 10 units of that cell, and know that there's no way any other particle can reach that cell for 100 evaluations.

If the coordinates change drastically each and every time, then the O(n) linear search is the best solution because any data structure (quadtree, hash grid, etc) takes at least O(n) time to set up, if only because it needs to visit each point.

share|improve this answer
    
There's an edit.. –  Schoolboy Mar 20 '13 at 13:32
    
Thanks. "randomly moving" is not enough of a clarification. How is it random? I outlined an optimization you can do with "randomly moving" points, if there's an upper bound on the motion. To repeat, if there's no upper bound then there's nothing better than a linear search. At that point it's just a matter of optimizing your Python code, which you haven't shown. –  Andrew Dalke Mar 20 '13 at 13:55
add comment

Instead of representing the pixels in an array like this:
(168,245),(59,52),(61,250), ..
you can represent them in a hash like this:
{168_245}=1,
{59_52}=1,
{61_250}=1,
..

This way you only need to iterate over your bounding coordinates and check if given pixel is in the hash.

The smaller the bounding box and the larger the pixel quantity that needs to be checked, the more efficient this algorithm becomes.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.