# Re: [cairo] Hit detect surface?

• From: Bill Spitzak <spitzak d2 com>
• To: Leon Woestenberg <leonw mailcan com>
• Cc: cairo cairographics org, Sven Herzberg <herzi gnome-de org>, gtk-devel-list gnome org, "Gustavo J. A. M. Carneiro" <gjc inescporto pt>
• Subject: Re: [cairo] Hit detect surface?
• Date: Wed, 01 Mar 2006 16:08:01 -0800

```

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;
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;

```