Re: [cairo] Hit detect surface?

[Bill Spitzak <spitzak d2 com>]

Leon Woestenberg wrote:
> Hello all,
>
> Bill Spitzak wrote:
>
> > To find the nearest, you must draw several times, with smaller and 
> > smaller squares, until either you reach a minimum size, or only one 
> > object is detected (or it goes to zero, in which case you use the 
> > previous pass). (actually now that I think about it, it may be more 
> > efficient to start at the minimum size and go up until you hit 
> > something.) 
>
> Can a 'binary search' algorithm be even more speedy in this regard?
>
> test a middle sized square, if hit detected halve the square size, else 
> double square size, repeat and rinse.

Yes, that's a great idea!

In a very common case it could quit after one iteration. If only one 
object is hit, it knows that is it, no need to check larger or smaller 
sizes.

Also it would allow much finer iterations, by skipping useless ones and 
narrowing down to where it might find a single hit. (my code can easily 
pick a further object, provided it is less than the delta in tested 
distances further away than the nearest object. Binary search would 
allow the delta to be much smaller).

Untested pseudo-code:

Object* hit_object = 0;
const double DELTA = .1; // minimum delta-distance we will get right
double a = DELTA;
double b = 10; // maximum size
while (a+DELTA < b) {
  double c = (a+b)/2;
  int n = hit_detect_circle_of_radius(c);
  if (!n) {
    a = c;
  } else if (n==1) {
    hit_object = only_object_that_was_hit;
    break;
  } else {
    hit_object = best_object_that_was_hit;
    b = c;
  }
}
return hit_object;