Re: [cairo] Hit detect surface?

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;
  } else {
    hit_object = best_object_that_was_hit;
    b = c;
return hit_object;

[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]