quad trees
Quad trees and kd trees (also R trees in databases) are a type of data structure that programmers use to organize data of two dimensions or higher. For me they've always had a kind of mystique about them, mostly due to a personal lack of application for the technique. Vinny suggested they would speed up finding points with the mouse (picking) and not take long to build, so I decided to implement them for Mused. Each time a new database query comes in we build a tree of the results. Then, each time the mouse moves we issue a tree query to see which sounds might be positioned under it.
Implementing the trees themselves was done in between flights from Philly to Canada, and did not take long at all. However, I was having glitches with my picking algorithm, such that it could not access some of the points showing up on the screen. To figure out what was wrong, I wrote some unit tests and some visualizations, which were pretty. After two days debugging, consider me thoroughly demystified.
The fault turned out to be in my search algorithm. Some bounding boxes were very thin in terms of the screen coordinates, so waving the mouse would end up searching boxes around it but not the box containing the point of interest. The solution I came up with was to inflate the child nodes by the query size and try each of the branches that could possibly contain the point of interest. This way each of the bounding boxes contains nonzero amount of screen real estate at comparison time and is thus active.
This was the little guy I for which I was searching. Just a little guitar and string hit from the Christopher Cross ballad Sailing. It was painting on the screen but not lighting up when the mouse went over with. Now that it's working, mousing over the sample brings a certain delayed satisfaction.