On Sep 30, 2004, at 10:15 AM, Martin Tschofen wrote:
The main canvas get's the mouse down and passes it on to my controller.
My controller iterates through every object asking it if the click was
within it. The object (usually a shape that's a subclass of my base
object)
responds back if it was it.
Does that answer your question?
Yes; now I answer yours. A way to improve selection speed would be to
keep a list of the objects that allows for faster searching, as others
have pointed out. If these objects are rectangular, or can at least be
covered by rectangles, then it's possible to implement what I believe
would be a faster algorithm.
Consider first the one-dimensional case, which I'll represent
abstractly as follows. Given a collection of intervals [a(i), b(i)],
not necessarily disjoint, and a point p, decide in which interval(s) p
lies. We'll create two lists of the intervals; sort the first list by
left endpoint, and the second list by right endpoint. Now do a binary
search to determine the greatest left endpoint a(I) satisfying a(I) <=
p, and a second binary search to determine the least right endpoint
a(J) satisfying p <= a(J). This part of the algorithm has running time
O(log(N)); in fact, it's actually bounded by 2*(log_2(N) + 1).
The result is two sets of intervals that can possibly contain p; then
you compute the intersection of the two sets. You could do this by
stuffing the sets into dictionaries and comparing, or by building
bitmaps, which should use less memory. In either case, the running
time of this step is a linear function of the sum of the sizes of the
sets. The worst case would be a collection of equal intervals; i.e. {
[a, b], [a, b], [a, b], ...}.
To handle the two-dimensional case, we decompose it into
one-dimensional cases. Build a list of horizontal intervals and list
of vertical intervals, then apply the algorithm above to each.
Now, the worst one-dimensional case can certainly occur; consider a
collection of rectangles all having the same top and bottom. To avoid
it, do the binary search for each list. It's possible that the result
will be a single possible rectangle. And, in general, you're unlikely
to get a large set of possible rectangles unless you have a bunch of
nested rectangles of the same size.
Charles Yeomans
_______________________________________________
Unsubscribe or switch delivery mode:
<http://www.realsoftware.com/support/listmanager/>
Search the archives of this list here:
<http://www.realsoftware.com/listarchives/lists.html>
|