Algorithm Help - hit test for small objects

Question

When implementing a selection algorithm in a processing sketch I cycle through each object in the scene and check to see if it is within a few pixel range of where the mouse clicked. There are lots of objects and they are very small.

As you can imagine once the scene gets filled with objects this becomes really burdensome. Are there easy ways to speed up this search? Can I easily I make this search binary? The objects in my scene are points so polygon hit-testing algorithms don't seem like the right solution.

Answer 1

Divide the scene into buckets, either into N x-buckets and M y-buckets, or into N*M x*y buckets. In the former case, the buckets are stored in two arrays (an x-array and a y-array); in the latter case, the buckets are stored in an array of arrays (the outer arrays indexes the x-coordinates, the inner arrays index the y-coordinates). In either case, the buckets store references to all of the points within the area indexed by the bucket; for example, the point (8, 12) would be in the x-bucket [5, 10] and the y-bucket [10, 15], or else it would be in the x*y bucket ([5, 10], [10, 15]).

When looking up a point, either look up the appropriate x and y buckets, or else simply look up the appropriate x*y buckets. In the former case, take intersection(union(x-buckets), union(y-buckets)). You may need to look up multiple buckets depending on the hit radius, for example if you're looking up the x-coordinate 9 with radius 2 then you'd need both the [5, 10] and [10, 15] buckets.

Using separate x and y buckets takes up less space (N + M buckets instead of N*M buckets) and makes the indexing easier (two separate arrays vs. one nested array), while the x*y buckets make for faster lookups since you won't need to take any set intersections.

The smaller your buckets, the more space the data structure will take up, but the fewer false positives you'll retrieve. Ideally, if you have sufficient memory, then the buckets will cover the same interval as the hit radius.

Answer 2

Maybe if you sort the arrays by one axis, lets say x you can speed things by returning early, I got this example from thomas.diewald at processing forum in this question. It may suits your need. Here only the part of the test ( you can look at the comlete code in the link above). There is an ArrayList of point which has x and y fields. Take a look

note that he is using a label for returning.

Arrays.sort(points);

  __FIND_NEIGHBORS__:
  for (int i = 0; i < num_points; i++) {
    Point pi = points[i];

    for (int j = i+1; j < num_points; j++) {
      Point pj = points[j];

      // 1. check in x
      float dx = pj.pos.x-pi.pos.x; // always positive -> points are sorted
      if( dx > max_dist ){
        continue __FIND_NEIGHBORS__; // ... no more points within max_dist.
      }

      // 2. check in y
      float dy = Math.abs(pj.pos.y-pi.pos.y); // not always positive
      if( dy > max_dist ){
        continue;
      }  

      // 3. check, could also just draw the line here (Manhattan distance)
      if ((dx*dx+dy*dy) < max_dist_sq) { 
        drawLine(pi, pj);
        connections++;
      }
    }
  }