Re: [cairo] Hit detect surface?

[Behdad Esfahbod <behdad cs toronto edu>]

On Wed, 1 Mar 2006, Bill Spitzak wrote:

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

Doesn't the distance_to_stroke/fill solve this already?  You just
find the nearest object and that tells you exactly what's the
maximum radius of a circle that hits only one object?

behdad

> 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;
>
> _______________________________________________
> cairo mailing list
> cairo cairographics org
> http://cairographics.org/cgi-bin/mailman/listinfo/cairo
>
>

--behdad
http://behdad.org/

"Commandment Three says Do Not Kill, Amendment Two says Blood Will Spill"
	-- Dan Bern, "New American Language"